A Two Query Adaptive Bitprobe Scheme Storing Five Elements

2018/10/31 by Mirza Galib Anwarul Husain Baig, Baig, Mirza Galib Anwarul Husain, Deepanjan Kesh +3
Computer Science · #Algorithms and Data Compression #Error Correcting Code Techniques #Complexity and Algorithms in Graphs

paper · pdf · doi:10.48550/arxiv.1810.13331

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.

Related

• An Improved Scheme in the Two Query Adaptive Bitprobe Model
• 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