Determining membership with 2 simultaneous queries

DOI10.1016/J.TCS.2014.05.020MaRDI QIDQ2250448zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

sortinginformation retrievalmembershipsearchingcell-probe

Mathematics Subject Classification ID

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

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

Cites work

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

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)