Squeezing succinct data structures into entropy bounds

DOI10.1145/1109557.1109693zbMath1192.68188OpenAlexW4230281099MaRDI QIDQ3581568

Kunihiko Sadakane, Roberto Grossi

Publication date: 16 August 2010

Published in: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Data structures (68P05)

Related Items

Succinct indices for path minimum, with applications, Unnamed Item, Can we locally compute sparse connected subgraphs?, A simple storage scheme for strings achieving entropy bounds, The function-inversion problem: barriers and opportunities, On compressing and indexing repetitive sequences, Engineering Practical Lempel-Ziv Tries, Ultra-succinct representation of ordered trees with applications, Stronger Lempel-Ziv based compressed text indexing, Random access in persistent strings and segment selection, Unnamed Item, Block trees, Efficient fully-compressed sequence representations, Optimal indexes for sparse bit vectors, LZ78 Compression in Low Main Memory Space, Compressed data structures: Dictionaries and data-aware measures, Rank and select revisited and extended, LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations, Dynamic relative compression, dynamic partial sums, and substring concatenation, LRM-trees: compressed indices, adaptive sorting, and compressed permutations, Space-efficient construction of Lempel-Ziv compressed text indexes, Opportunistic data structures for range queries, Unnamed Item, Wee LCP, Lempel-Ziv factorization powered by space efficient suffix trees, Dynamic rank/select structures with applications to run-length encoded texts, Rank/select on dynamic compressed sequences and applications, Compressed Dynamic Tries with Applications to LZ-Compression in Sublinear Time and Space, Random Access to High-Order Entropy Compressed Text, Linked dynamic tries with applications to LZ-compression in sublinear time and space, Adaptive succinctness