Fast Compressed Tries through Path Decompositions

DOI10.1145/2656332zbMath1347.68101OpenAlexW2000568570MaRDI QIDQ2828185

Roberto Grossi, Giuseppe Ottaviano

Publication date: 24 October 2016

Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2656332

zbMATH Keywords

triessuccinct data structuresmonotone perfect hash functionsstring dictionaries

Mathematics Subject Classification ID

Data structures (68P05)

Related Items

c-trie++: a dynamic trie tailored for fast prefix searches, Dynamic Path-decomposed Tries, On the correctness of a lock-free compression-based elastic mechanism for a hash trie design, Compressed string dictionaries via data-aware subtrie compaction, Practical Implementation of Space-Efficient Dynamic Keyword Dictionaries, Lempel-Ziv-78 compressed string dictionaries, Top tree compression of tries, Faster compressed quadtrees, Random Access to High-Order Entropy Compressed Text

Uses Software

• UbiCrawler
• GitHub
• SDSL
• libcds
• succinct
• Sux4J

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Ultra-succinct representation of ordered trees with applications
• Representing trees of higher degree
• A data structure for dynamic trees
• Succinct Representation of Balanced Parentheses and Static Trees
• Succinct Representations of Binary Trees for Range Minimum Queries
• The string B-tree
• Compressing and indexing labeled trees, with applications
• Extended Compact Web Graph Representations
• Cache-oblivious string dictionaries
• Universal codeword sets and representations of the integers
• Efficient Storage and Retrieval by Content and Address of Static Files
• Compact dictionaries for variable-length keys and data with applications
• Practical Entropy-Compressed Rank/Select Dictionary
• Succinct Trees in Practice
• Theory and practice of monotone minimal perfect hashing
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching