Australian Computer Society
Tries 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 to poor performance on current processors. In this paper, the authors introduce the HAT-trie, a cache-conscious trie-based data structure that is formed by carefully combining existing components. They evaluate performance using several real-world datasets and against other high-performance data structures.