Determining membership with 2 simultaneous queries

DOI10.1016/J.TCS.2014.05.020zbMATH Open1360.68392OpenAlexW2024316265MaRDI QIDQ2250448FDOQ2250448

Authors: David M. Howard 

Publication date: 7 July 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.05.020

Recommendations

• On adaptive bitprobe schemes for storing two elements
• Set membership with a few bit probes
• On the bitprobe complexity of two probe adaptive schemes storing two elements
• Set membership with non-adaptive bit probes
• A two query adaptive bitprobe scheme storing five elements

zbMATH Keywords

sortinginformation retrievalmembershipsearchingcell-probe

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Cooperative games (91A12) Searching and sorting (68P10)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Should Tables Be Sorted?
• Low redundancy in static dictionaries with constant query time
• Membership in Constant Time and Almost-Minimum Space
• Are Bitvectors Optimal?
• Title not available (Why is that?)
• Storing information with extractors.
• On the cell probe complexity of membership and perfect hashing
• A Survey of Data Structures in the Bitprobe Model
• Data structures for storing small sets in the bitprobe model
• On the power of two, three and four probes
• Bit-probe lower bounds for succinct data structures

This page was built for publication: Determining membership with 2 simultaneous queries

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