Definition: A variant of a trie in which leaf nodes are buckets which hold up to k strings. Usually implies fixed sized buckets.
Generalization (I am a kind of ...)
Specialization (... is a kind of me.)
Note: Combining terminal strings can greatly shorten branches. For instance, "extraordinarily", "extraordinariness", and "extraordinary" can be stored in one bucket at the end of a short branch distinguishing them from extran... and extrap... rather than a long branch for the common substring ...ordinar...
The name comes from reTRIEval and is pronounced, "tree." See the historical note at trie.
Edward H. Sussenguth, Jr., Use of Tree Structures for Processing Files, CACM, 6(5):272-279, May 1963.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 1 August 2008.
HTML page formatted Mon Nov 18 10:44:09 2013.
Cite this as:
Paul E. Black, "bucket trie", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 1 August 2008. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/bucketTrie.html