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 24 August 2017.
HTML page formatted Fri Feb 23 10:06:07 2018.
Cite this as:
Paul E. Black, "bucket trie", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 24 August 2017. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/bucketTrie.html