(data structure)
Definition: A specialized Patricia tree whose internal nodes store only an integer, k, which is the length of the common prefix of the strings in the children. Equivalently, the strings first differ in the (k+1)st character.
Generalization (I am a kind of ...)
Patricia tree.
Aggregate parent (I am a part of or used in ...)
blind sort.
Note: Used in a specialized algorithm, described in Engineering a Lightweight Suffix Array Construction Algorithm, to build suffix arrays.
The name comes from reTRIEval and is pronounced, "tree." See the historical note at trie.
Author: PEB
Defined in the following, but called a Patricia tree
Paolo Ferragina and Roberto Grossi, The string B-tree: a new data structure for string search in external memory and its applications, Journal of the ACM, 46(2): 236 - 280, (March 1999).
Called "blind trie" in
Giovanni Manzini and Paolo Ferragina, Engineering a Lightweight Suffix Array Construction Algorithm, Algorithmica, 40(1):33-50, (Jun 2004).
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 14 August 2008.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black, "blind trie", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 14 August 2008. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/blindTrie.html