A Survey of Data Structures in the Bitprobe Model

DOI10.1007/978-3-642-40273-9_19MaRDI QIDQ2848981zbMATH OpenOpenAlexFDO

Authors Patrick K. Nicholson, Venkatesh Raman, S. Srinivasa Rao

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

Mathematics Subject Classification ID

Data structures (68P05)

Recommendations

• Improved explicit data structures in the bitprobe model
• Data structures for storing small sets in the bitprobe model
• Bit-probe lower bounds for succinct data structures
• Bit-probe lower bounds for succinct data structures
• Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes
• scientific article; zbMATH DE number 2147454
• scientific article; zbMATH DE number 88934
• scientific article; zbMATH DE number 1412401
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Advanced data structures. Theory and applications

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 512871 (Why is no real title available?)
• scientific article; zbMATH DE number 2176112 (Why is no real title available?)
• scientific article; zbMATH DE number 1830754 (Why is no real title available?)
• scientific article; zbMATH DE number 1875423 (Why is no real title available?)
• scientific article; zbMATH DE number 3314813 (Why is no real title available?)
• A Survey of Combinatorial Gray Codes
• A data structure for manipulating priority queues
• A linear lower bound on index size for text retrieval
• A tradeoff between search and update time for the implicit dictionary problem
• An optimal bloom filter replacement
• Are Bitvectors Optimal?
• Bit-probe lower bounds for succinct data structures
• Changing base without losing space
• Data structures for storing small sets in the bitprobe model
• Deterministic methods to find primes
• Dictionary Look-Up with One Error
• Dynamic word problems
• Hardness vs randomness
• Improved bounds for dictionary look-up with one error
• Improved explicit data structures in the bitprobe model
• Improved methods for generating quasi-Gray codes
• Integer representation and counting in the bit probe model
• Integer representations towards efficient counting in the bit probe model
• Low redundancy in static dictionaries with constant query time
• Membership in Constant Time and Almost-Minimum Space
• Network Applications of Bloom Filters: A Survey
• On dynamic bit-probe complexity
• On dynamic range reporting in one dimension
• On the cell probe complexity of membership and perfect hashing
• Optimal dynamic vertical ray shooting in rectilinear planar subdivisions
• Optimal indexes for sparse bit vectors
• Optimal lower bounds for rank and select indexes
• Partial match retrieval in implicit data structures
• Purely Functional Data Structures
• Should Tables Be Sorted?
• Space/time trade-offs in hash coding with allowable errors
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Storing information with extractors.
• The Complexity of Maintaining an Array and Computing Its Partial Sums
• The Complexity of Some Simple Retrieval Problems
• The cell probe complexity of succinct data structures
• Two skew-binary numeral systems and one application

Cited in

(7)

• Space-optimal quasi-Gray codes with logarithmic read complexity
• Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes
• Lower bounds for restricted schemes in the two-adaptive bitprobe model
• Determining membership with 2 simultaneous queries
• On the bitprobe complexity of two probe adaptive schemes
• Two improved schemes in the bitprobe model
• Revisiting explicit adaptive two-probe schemes

This page was built for publication: A Survey of Data Structures in the Bitprobe Model

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