A two query adaptive bitprobe scheme storing five elements

DOI10.1007/978-3-030-10564-8_25zbMATH Open1434.68119arXiv1810.13331OpenAlexW2899197552MaRDI QIDQ5236173FDOQ5236173

Authors: Mirza Galib Anwarul Husain Baig, Deepanjan Kesh, Chirag Sodani 

Publication date: 15 October 2019

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

Abstract: We are studying the adaptive bitprobe model to store an arbitrary subset S of size at most five from a universe U of size m and answer the membership queries of the form "Is x in S?" in two bitprobes. In this paper, we present a data structure for the aforementioned problem. Our data structure takes O(m^{10/11}) space. This result improves the non-explicit result by Garg and Radhakrishnan [2015] which takes O(m^{20/21}) space, and the explicit result by Garg [2016] which takes O(m^{18/19} ) space for the aforementioned set and query sizes.

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

Recommendations

• An improved scheme in the two query adaptive bitprobe model
• Storing four elements in the two query bitprobe model
• On adaptive bitprobe schemes for storing two elements
• On the bitprobe complexity of two probe adaptive schemes storing two elements

zbMATH Keywords

data structuresbitprobe modelset membership problem

Mathematics Subject Classification ID

Data structures (68P05)

Cited In (4)

• Determining membership with 2 simultaneous queries
• Storing four elements in the two query bitprobe model
• An improved scheme in the two query adaptive bitprobe model
• On adaptive bitprobe schemes for storing two elements

This page was built for publication: A two query adaptive bitprobe scheme storing five elements

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