Squeezing succinct data structures into entropy bounds

DOI10.1145/1109557.1109693zbMath1192.68188MaRDI 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

68P05: Data structures

Related Items

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