Optimal indexes for sparse bit vectors

DOI10.1007/S00453-013-9767-2zbMATH Open1307.68031arXiv1108.2157OpenAlexW1965268455MaRDI QIDQ472491FDOQ472491

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

Publication date: 19 November 2014

Published in: Algorithmica (Search for Journal in Brave)

Abstract: We consider the problem of supporting Rank() and Select() operations on a bit vector of length m with n 1 bits. The problem is considered in the succinct index model, where the bit vector is stored in "read-only" memory and an additional data structure, called the index, is created during pre-processing to help answer the above queries. We give asymptotically optimal density-sensitive trade-offs, involving both m and n, that relate the size of the index to the number of accesses to the bit vector (and processing time) needed to answer the above queries. The results are particularly interesting for the case where n = o(m).

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

Recommendations

• Index structures for fast similarity search for binary vectors
• Optimal-Time Dictionary-Compressed Indexes
• Space-efficient construction of compressed indexes in deterministic linear time
• An optimal storage format for sparse matrices
• Algorithms and Computation
• Deterministic construction of sparse binary matrices via incremental integer optimization
• Optimally sparse data representations

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (18)

• Adaptive succinctness
• Lower bounds on the size of selection and rank indexes
• High-order entropy compressed bit vectors with rank/select
• Adaptive succinctness
• A Survey of Data Structures in the Bitprobe Model
• Rank and select operations on a word
• Everywhere-Tight Information Cost Tradeoffs for Augmented Index
• More haste, less waste: lowering the redundancy in fully indexable dictionaries
• Optimal lower bounds for rank and select indexes
• Compressed Prefix Sums
• Canonical density control
• Low-weight halfspaces for sparse boolean vectors
• Optimal Lower Bounds for Rank and Select Indexes
• Compressed persistent index for efficient rank/select queries
• Approximate query processing over static sets and sliding windows
• Approximate query processing over static sets and sliding windows
• Index Vector Elimination – Making Index Vectors Affordable
• Entropy-bounded representation of point grids

This page was built for publication: Optimal indexes for sparse bit vectors

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