A Two Query Adaptive Bitprobe Scheme Storing Five Elements
share
We are studying the adaptive bitprobe model to store an arbitrary subset S of size at most five from a universe 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.
READ FULL TEXT
