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 ...)
Aggregate parent (I am a part of or used in ...)
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.
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 E. Black.
Entry modified 14 August 2008.
HTML page formatted Fri Mar 25 16:20:34 2011.
Cite this as:
Paul E. Black, "blind trie", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 14 August 2008. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/blindTrie.html