Set membership with non-adaptive bit probes

DOI10.4230/LIPICS.STACS.2017.38MaRDI QIDQ4636637zbMATH OpenFDO

Authors Mohit Garg, Jaikumar Radhakrishnan

Publication date 19 April 2018

Full work available at URL https://arxiv.org/abs/1612.09388

zbMATH Keywords

data structuresexpansioncompressionBloom filtersbit-probe model

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Analysis of algorithms and problem complexity (68Q25) Data structures (68P05)

Recommendations

• Set membership with a few bit probes
• Data structures for storing small sets in the bitprobe model
• On the power of two, three and four probes
• Are Bitvectors Optimal?
• On the bitprobe complexity of two probe adaptive schemes storing two elements

Cited in

(13)

• Data structures for storing small sets in the bitprobe model
• scientific article; zbMATH DE number 1875423 (Why is no real title available?)
• On the power of two, three and four probes
• Determining membership with 2 simultaneous queries
• The quantum complexity of set membership
• Bit-probe lower bounds for succinct data structures
• Are bitvectors optimal?
• Are Bitvectors Optimal?
• Exact and approximate membership testers
• 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 7250167 (Why is no real title available?)
• Set membership with a few bit probes

This page was built for publication: Set membership with non-adaptive bit probes

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