Are Bitvectors Optimal?

DOI10.1137/S0097539702405292MaRDI QIDQ3149891zbMATH OpenFDO

Authors

Publication date 29 September 2002

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539702405292

zbMATH Keywords

bit probe modeldata structuresset membership problemset systems

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Information storage and retrieval of data (68P20)

Recommendations

• Are bitvectors optimal?
• Set membership with a few bit probes
• Data structures for storing small sets in the bitprobe model
• Set membership with non-adaptive bit probes
• Improved explicit data structures in the bitprobe model

Cited in

(19)

• Revisiting explicit adaptive two-probe schemes
• Determining membership with 2 simultaneous queries
• Lower bounds for predecessor searching in the cell probe model
• An efficient superpostional quantum Johnson-Lindenstrauss lemma via unitary \(t\)-designs
• A Survey of Data Structures in the Bitprobe Model
• Are bitvectors optimal?
• Expander graphs and their applications
• Membership in Constant Time and Almost-Minimum Space
• On finding the closest bitwise matches in a fixed set
• scientific article; zbMATH DE number 1982202 (Why is no real title available?)
• Submodular functions: learnability, structure, and optimization
• Set membership with non-adaptive bit probes
• Nearly Optimal Static Las Vegas Succinct Dictionary
• Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes
• Set membership with a few bit probes
• Integer Representation and Counting in the Bit Probe Model
• Exact and approximate membership testers
• Optimal non-adaptive cell probe dictionaries and hashing
• Integer representation and counting in the bit probe model

This page was built for publication: Are Bitvectors Optimal?

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