Set membership with non-adaptive bit probes

DOI10.4230/LIPICS.STACS.2017.38zbMATH Open1402.68034arXiv1612.09388MaRDI QIDQ4636637FDOQ4636637

Authors: Mohit Garg, Jaikumar Radhakrishnan 

Publication date: 19 April 2018

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

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

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)

Cited In (13)

• Are bitvectors optimal?
• Title not available (Why is that?)
• Bit-probe lower bounds for succinct data structures
• The quantum complexity of set membership
• Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes
• Bit-probe lower bounds for succinct data structures
• Determining membership with 2 simultaneous queries
• Title not available (Why is that?)
• Exact and approximate membership testers
• Set membership with a few bit probes
• Are Bitvectors Optimal?
• Data structures for storing small sets in the bitprobe model
• On the power of two, three and four 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)