2017/04/19 by Poyias, Andreas, Puglisi, Simon J., Raman, Rajeev · 1 citation
#Data Structures and Algorithms (cs.DS) #E.1 #E.2 #E.4 #F.2.2 #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1704.05682
We consider the problem of implementing a space-efficient dynamic trie, with an emphasis on good practical performance. For a trie with n nodes with an alphabet of size σ, the information-theoretic lower bound is n log σ+ O(n) bits. The Bonsai data structure is a compact trie proposed by Darragh et al. (Softw., Pract. Exper. 23(3), 1993, p. 277-291). Its disadvantages include the user having to specify an upper bound M on the trie size in advance (which cannot be changed easily after initalization), a space usage of M log σ+ O(M log log M) (which is asymptotically non-optimal for smaller σ or if n ≪ M) and a lack of support for deletions. It supports traversal and update operations in O(1/ε) expected time (based on assumptions about the behaviour of hash functions), where ε= (M-n)/M and has excellent speed performance in practice. We propose an alternative, m-Bonsai, that addresses the above problems, obtaining a trie that uses (1+β) n (log σ+ O(1)) bits in expectation, and supports traversal and update operations in O(1/β) expected time and O(1/β2) amortized expected time, for any user-specified parameter β> 0 (again based on assumptions about the behaviour of hash functions). We give an implementation of m-Bonsai which uses considerably less memory and is slightly faster than the original Bonsai.