Revisiting Explicit Adaptive Two-Probe Schemes

In the bitprobe model the concern is, primarily, the number of bits that must be probed in a data structure in order to answer queries, and how limiting probes affects the storage requirements. In this note we revisit an explicit membership scheme of Radhakrishnan et al. [ESA 2001], which stores an n = 2 element subset of a universe [1, m], occupies O(m^2/3 ) bits, and supports membership queries in t = 2 bit probes. We show that, with a small modification, their scheme also works for n = 3 elements. This provides the first fully explicit scheme answering their open problem of whether there exist schemes that occupy o(m) bits for t = 2 and n > 2.