NIST

bucket trie

(data structure)

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 ...)
trie.

Specialization (... is a kind of me.)
elastic-bucket trie.

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.

Author: PEB

More information

Edward H. Sussenguth, Jr., Use of Tree Structures for Processing Files, CACM, 6(5):272-279, May 1963.


Go to the Dictionary of Algorithms and Data Structures home page.

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