Data Structures for Storing Small Sets in the Bitprobe Model

We study the following set membership problem in the bitprobe model: Given a set S from a finite universe U , represent it in memory so that membership queries of the form Is x in S? can be answered with a small number of bitprobes. We obtain explicit schemes that come close to the information theoretic lower bound of Buhrman et al. [STOC 2000, SICOMP 2002] and improve the results of Radhakrishnan et al. [ESA 2001] when the size of sets and the number of probes is small.

We show that any scheme that stores sets of size two from a universe of size m and answers membership queries using two bitprobes requires space Ω(m^(4/7)). The previous best lower bound was Ω(m^(1/2}). This is the first instance where the information theoretic lower bound is found to be not tight for adaptive schemes.

We show that any non-adaptive three probe scheme for storing sets of size two from a universe of size m requires Ω(m^(1/2}) bits of memory. This extends a result of Alon and Feige [SODA 2009] to small sets (to be presented in ESA 2010 joint work with Jaikumar Radhakrishnan and Smit Shah).