A Survey of Data Structures in the Bitprobe Model
From MaRDI portal
Publication:2848981
DOI10.1007/978-3-642-40273-9_19zbMath1395.68103OpenAlexW152712179MaRDI QIDQ2848981
S. Srinivasa Rao, Venkatesh Raman, Patrick K. Nicholson
Publication date: 13 September 2013
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-40273-9_19
Related Items (7)
On the bitprobe complexity of two probe adaptive schemes ⋮ Lower bounds for restricted schemes in the two-adaptive bitprobe model ⋮ Revisiting explicit adaptive two-probe schemes ⋮ Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity ⋮ Determining membership with 2 simultaneous queries ⋮ Two improved schemes in the bitprobe model ⋮ Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved bounds for dictionary look-up with one error
- Optimal indexes for sparse bit vectors
- Two skew-binary numeral systems and one application
- Partial match retrieval in implicit data structures
- Integer representation and counting in the bit probe model
- A tradeoff between search and update time for the implicit dictionary problem
- Hardness vs randomness
- Storing information with extractors.
- The cell probe complexity of succinct data structures
- On dynamic bit-probe complexity
- Optimal lower bounds for rank and select indexes
- Low Redundancy in Static Dictionaries with Constant Query Time
- Changing base without losing space
- Improved Explicit Data Structures in the Bitprobe Model
- Optimal dynamic vertical ray shooting in rectilinear planar subdivisions
- Integer Representations towards Efficient Counting in the Bit Probe Model
- Are Bitvectors Optimal?
- Improved Methods For Generating Quasi-gray Codes
- On dynamic range reporting in one dimension
- Data Structures for Storing Small Sets in the Bitprobe Model
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- Should Tables Be Sorted?
- The Complexity of Maintaining an Array and Computing Its Partial Sums
- The Complexity of Some Simple Retrieval Problems
- A data structure for manipulating priority queues
- Membership in Constant Time and Almost-Minimum Space
- Dictionary Look-Up with One Error
- A Survey of Combinatorial Gray Codes
- Dynamic word problems
- A linear lower bound on index size for text retrieval
- Network Applications of Bloom Filters: A Survey
- Purely Functional Data Structures
- Bit-Probe Lower Bounds for Succinct Data Structures
- On the cell probe complexity of membership and perfect hashing
- Deterministic methods to find primes
- Space/time trade-offs in hash coding with allowable errors
This page was built for publication: A Survey of Data Structures in the Bitprobe Model