(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 24 August 2017.
HTML page formatted Wed Mar 13 12:42:45 2019.
Cite this as:
Paul E. Black, "blind trie", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 24 August 2017. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/blindTrie.html