Optimal indexes for sparse bit vectors
From MaRDI portal
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).
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
Cites work
- scientific article; zbMATH DE number 2079421 (Why is no real title available?)
- A cryptanalytic time-memory trade-off
- A simple storage scheme for strings achieving entropy bounds
- Cell-probe lower bounds for succinct partial sums
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
- Compressed data structures: Dictionaries and data-aware measures
- Compressing and indexing labeled trees, with applications
- Efficient Storage and Retrieval by Content and Address of Static Files
- Engineering the LOUDS Succinct Tree Representation
- Indexing compressed text
- Lower bounds on the size of selection and rank indexes
- On the Size of Succinct Indices
- Optimal lower bounds for rank and select indexes
- Practical entropy-compressed rank/select dictionary
- Squeezing succinct data structures into entropy bounds
- Statistical Encoding of Succinct Data Structures
- Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets
- Succinct indexes for strings, binary relations and multilabeled trees
- Succinct ordinal trees with level-ancestor queries
- The cell probe complexity of succinct data structures
- Time-space trade-offs for predecessor search
Cited in
(18)- Index Vector Elimination – Making Index Vectors Affordable
- Lower bounds on the size of selection and rank indexes
- Adaptive succinctness
- 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
- 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)
