Squeezing succinct data structures into entropy bounds

DOI10.1145/1109557.1109693MaRDI QIDQ3581568zbMATH OpenOpenAlexFDO

Authors 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)

Cited in

(33)

• 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
• Succinct oblivious RAM
• 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
• Entropy lower bounds for dictionary compression
• 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
• Space-efficient construction of Lempel-Ziv compressed text indexes
• scientific article; zbMATH DE number 7765406 (Why is no real title available?)
• Random access in persistent strings and segment selection
• Adaptive succinctness
• Lempel-Ziv factorization powered by space efficient suffix trees
• Locally computing edge orientations
• 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

This page was built for publication: Squeezing succinct data structures into entropy bounds

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