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