Optimal indexes for sparse bit vectors

DOI10.1007/s00453-013-9767-2zbMath1307.68031arXiv1108.2157OpenAlexW1965268455MaRDI QIDQ472491

S. Srinivasa Rao, Alexander Golynski, Alessio Orlandi, Rajeev Raman

Publication date: 19 November 2014

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1108.2157

zbMATH Keywords

redundancysuccinct data structuresrank and selectbit-vectorsinformation-theoretic lower boundsystematic encoding

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05)

Related Items

Entropy-bounded representation of point grids, Approximate query processing over static sets and sliding windows, Unnamed Item, A Survey of Data Structures in the Bitprobe Model, Adaptive succinctness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simple storage scheme for strings achieving entropy bounds
• The cell probe complexity of succinct data structures
• Compressed data structures: Dictionaries and data-aware measures
• Optimal lower bounds for rank and select indexes
• Time-space trade-offs for predecessor search
• Succinct ordinal trees with level-ancestor queries
• Succinct indexes for strings, binary relations and multilabeled trees
• Compressing and indexing labeled trees, with applications
• On the Size of Succinct Indices
• Indexing compressed text
• Squeezing succinct data structures into entropy bounds
• A cryptanalytic time-memory trade-off
• Efficient Storage and Retrieval by Content and Address of Static Files
• Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisets
• Practical Entropy-Compressed Rank/Select Dictionary
• Statistical Encoding of Succinct Data Structures
• Engineering the LOUDS Succinct Tree Representation
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching