HAT-Trie: A Cache-Conscious Trie-Based Data Structure For Strings

Askitis, N. and Sinha, R.

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, we introduce the HAT-trie, a cache-conscious trie-based data structure that is formed by carefully combining existing components. We evaluate performance using several real-world datasets and against other high- performance data structures. We show strong im- provements in both time and space; in most cases ap- proaching that of the cache-conscious hash table. Our HAT-trie is shown to be the most efficient trie-based data structure for managing variable-length strings in-memory while maintaining sort order.

Cite as: Askitis, N. and Sinha, R. (2007). HAT-Trie: A Cache-Conscious Trie-Based Data Structure For Strings. In Proc. Thirtieth Australasian Computer Science Conference (ACSC2007), Ballarat Australia. CRPIT, 62. Dobbie, G., Ed. ACS. 97-105.

(from crpit.com) (local if available)