Dynamic Path-decomposed Tries
From MaRDI portal
Abstract: A keyword dictionary is an associative array whose keys are strings. Recent applications handling massive keyword dictionaries in main memory have a need for a space-efficient implementation. When limited to static applications, there are a number of highly-compressed keyword dictionaries based on the advancements of practical succinct data structures. However, as most succinct data structures are only efficient in the static case, it is still difficult to implement a keyword dictionary that is space efficient and dynamic. In this article, we propose such a keyword dictionary. Our main idea is to embrace the path decomposition technique, which was proposed for constructing cache-friendly tries. To store the path-decomposed trie in small memory, we design data structures based on recent compact hash trie representations. Experiments on real-world datasets reveal that our dynamic keyword dictionary needs up to 68% less space than the existing smallest ones, while achieving a relevant space-time tradeoff.
Recommendations
Cites work
- scientific article; zbMATH DE number 3738962 (Why is no real title available?)
- scientific article; zbMATH DE number 1052006 (Why is no real title available?)
- scientific article; zbMATH DE number 6472611 (Why is no real title available?)
- A framework of dynamic data structures for string processing
- Compact Hash Tables Using Bidirectional Linear Probing
- Compact dynamic rewritable (CDRW) arrays
- Compression of individual sequences via variable-rate coding
- Fast and simple compact hashing via bucketing
- Fast compressed tries through path decompositions
- LZ78 compression in low main memory space
- LZD factorization: simple and practical online grammar compression with variable-to-fixed encoding
- Lempel-Ziv-78 compressed string dictionaries
- Linked dynamic tries with applications to LZ-compression in sublinear time and space
- Masking Dilithium. Efficient implementation and side-channel evaluation
- On two LZ78-style grammars: compression bounds and compressed-space computation
- Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing
- Practical evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch tries
- Practical implementation of space-efficient dynamic keyword dictionaries
- Succinct dynamic cardinal trees
- m-Bonsai: a practical compact dynamic trie
Cited in
(7)- Compressed string dictionaries via data-aware subtrie compaction
- Fast Compressed Tries through Path Decompositions
- Engineering practical Lempel-Ziv tries
- c-trie++: a dynamic trie tailored for fast prefix searches
- Practical implementation of space-efficient dynamic keyword dictionaries
- Fast and simple compact hashing via bucketing
- Fast compressed tries through path decompositions
This page was built for publication: Dynamic Path-decomposed Tries
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6039927)
