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 3 September 2019.
HTML page formatted Fri Sep 6 15:26:10 2019.
Cite this as:
Paul E. Black, "bucket trie", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 3 September 2019. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/bucketTrie.html