Portal de Periódicos da CAPES

Improved Practical Compact Dynamic Tries

2015; Springer Science+Business Media; Linguagem: Inglês

10.1007/978-3-319-23826-5_31

1611-3349

Andreas Poyias, Rajeev Raman,

Advanced Data Storage Technologies

We consider the problem of implementing a dynamic trie with an emphasis on good practical performance. For a trie with n nodes with an alphabet of size $$\sigma $$ , the information-theoretic lower bound is $$n \log \sigma + O(n)$$ bits. The Bonsai data structure [1] supports trie operations in O(1) expected time (based on assumptions about the behaviour of hash functions). While its practical speed performance is excellent, its space usage of $$(1+\epsilon ) n (\log \sigma + O(\log \log n))$$ bits, where $$\epsilon $$ is any constant $$> 0$$ , is not asymptotically optimal. We propose an alternative, m-Bonsai, that uses $$(1 + \epsilon ) n (\log \sigma + O(1))$$ bits in expectation, and supports operations in O(1) expected time (again based on assumptions about the behaviour of hash functions). We give a heuristic implementation of m-Bonsai which uses considerably less memory and is slightly faster than the original Bonsai.