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