m-Bonsai: a practical compact dynamic trie

DOI10.1142/S0129054118430025MaRDI QIDQ5384619zbMATH OpenOpenAlexWikidataFDO

Authors Andreas Poyias, Simon J. Puglisi, Rajeev Raman

Publication date 24 June 2019

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1704.05682

zbMATH Keywords

cardinal treecompact hashingdigital search treedynamic triesuccinct data structurestrie

Mathematics Subject Classification ID

Data structures (68P05)

Abstract: 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 $sigma$, the information-theoretic lower bound is $nlogsigma+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 $Mlogsigma+O(MloglogM)$ (which is asymptotically non-optimal for smaller $sigma$ or if $nllM$) and a lack of support for deletions. It supports traversal and update operations in $O(1/epsilon)$ expected time (based on assumptions about the behaviour of hash functions), where $epsilon=(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 $$ bits in expectation, and supports traversal and update operations in $$ expected time and $$ amortized expected time, for any user-specified parameter $$ (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.

Recommendations

• Fast compressed tries through path decompositions
• Algorithms for trie compaction
• Fast Compressed Tries through Path Decompositions
• Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing
• Improved behaviour of tries by adaptive branching

Cites work

• A uniform paradigm to succinctly encode various families of trees
• Algorithm design and applications
• An experimental study of compression methods for dynamic tries
• Compact dynamic rewritable (CDRW) arrays
• Compact Hash Tables Using Bidirectional Linear Probing
• CRAM: compressed random access memory
• scientific article; zbMATH DE number 1033192 (Why is no real title available?)
• scientific article; zbMATH DE number 2038723 (Why is no real title available?)
• scientific article; zbMATH DE number 1830754 (Why is no real title available?)
• Linked dynamic tries with applications to LZ-compression in sublinear time and space
• Low redundancy in static dictionaries with constant query time
• Representing dynamic binary trees succinctly
• Representing trees of higher degree
• STACS 2012. 29th international symposium on theoretical aspects of computer science, Paris, France, February 29th -- March 3rd, 2012
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Succinct dynamic cardinal trees
• Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets
• Universal classes of hash functions
• Universal codeword sets and representations of the integers
• Universal Succinct Representations of Trees?

Cited in

(5)

• Fast and simple compact hashing via bucketing
• Engineering practical Lempel-Ziv tries
• LZ78 compression in low main memory space
• Dynamic Path-decomposed Tries
• Compressed string dictionaries via data-aware subtrie compaction

This page was built for publication: m-Bonsai: a practical compact dynamic trie

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384619)