Data structures for storing small sets in the bitprobe model

DOI10.1007/978-3-642-15781-3_14MaRDI QIDQ3586392zbMATH OpenOpenAlexFDO

Authors Smit Shah, Saswata Shannigrahi, Jaikumar Radhakrishnan

Publication date 6 September 2010

Published in Algorithms – ESA 2010 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-15781-3_14

Mathematics Subject Classification ID

Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Set membership with a few bit probes
• Improved explicit data structures in the bitprobe model
• Set membership with non-adaptive bit probes
• On the bitprobe complexity of two probe adaptive schemes storing two elements
• On adaptive bitprobe schemes for storing two elements

Cited in

(18)

• Revisiting explicit adaptive two-probe schemes
• Storing four elements in the two query bitprobe model
• On the bitprobe complexity of two probe adaptive schemes
• 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 storing two elements
• A Survey of Data Structures in the Bitprobe Model
• Improved explicit data structures in the bitprobe model
• Are Bitvectors Optimal?
• Are bitvectors optimal?
• Set membership with non-adaptive bit probes
• Bit-probe lower bounds for succinct data structures
• Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes
• Space Complexity of Two Adaptive Bitprobe Schemes Storing Three Elements
• Bit-probe lower bounds for succinct data structures
• Set membership with a few bit probes
• Storing set families more compactly with top ZDDs
• An analysis of Las Vegas algorithms for linear search

This page was built for publication: Data structures for storing small sets in the bitprobe model

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