HAT-trie: A Cache-conscious Trie-based Data Structure for StringsNikolas Askitis Ranjan SinhaSchool of Computer Science and Information Technology,
RMIT University, Melbourne 3001, Australia.
Email: {naskitis,rsinha}@cs.rmit.edu.auAbstractTries are the fastest tree-based data structures for
managing strings in-memory, but are space-intensive.
The burst-trie is almost as fast but reduces space by
collapsing trie-chains into buckets. This is not how-
ever, a cache-conscious approach and can lead t
