An improved scheme in the two query adaptive bitprobe model

DOI10.1007/978-3-030-25005-8_3MaRDI QIDQ2301733zbMATH OpenOpenAlexFDO

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

Publication date 25 February 2020

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

zbMATH Keywords

data structureadaptive schemebitprobe modelset membership problem

Mathematics Subject Classification ID

Data structures (68P05)

Abstract: In this paper, we look into the adaptive bitprobe model that stores subsets of size at most four from a universe of size m, and answers membership queries using two bitprobes. We propose a scheme that stores arbitrary subsets of size four using O(m^{5/6}) amount of space. This improves upon the non-explicit scheme proposed by Garg and Radhakrishnan [Garg2015] which uses O(m^{16/17}) amount of space, and the explicit scheme proposed by Garg [Thesis2015] which uses O(m^{14/15}) amount of space.

Recommendations

• Two improved schemes in the bitprobe model
• On the bitprobe complexity of two probe adaptive schemes
• Two new schemes in the bitprobe model
• On the bitprobe complexity of two probe adaptive schemes storing two elements
• On adaptive bitprobe schemes for storing two elements
• A two query adaptive bitprobe scheme storing five elements
• Lower bounds for restricted schemes in the two-adaptive bitprobe model
• Revisiting explicit adaptive two-probe schemes

Cited in

(6)

• Lower bounds for restricted schemes in the two-adaptive bitprobe model
• Two new schemes in the bitprobe model
• Storing four elements in the two query bitprobe model
• Two improved schemes in the bitprobe model
• A two query adaptive bitprobe scheme storing five elements
• On adaptive bitprobe schemes for storing two elements

This page was built for publication: An improved scheme in the two query adaptive bitprobe model

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