An Improved Scheme in the Two Query Adaptive Bitprobe Model

2018/12/12 by Baig, Mirza Galib Anwarul Husain, Kesh, Deepanjan, Sodani, Chirag
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1812.04802

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.

Related

• A Two Query Adaptive Bitprobe Scheme Storing Five Elements
• Improved Bounds for Two Query Adaptive Bitprobe Schemes Storing Five\n Elements
• Lower Bounds for Restricted Schemes in the Two-Adaptive Bitprobe Model
• Set Membership with a Few Bit Probes
• Set membership with non-adaptive bit probes