Are Bitvectors Optimal?

We study the it static membership problem: Given a set S of at most n keys drawn from a universe U of size m, store it so that queries of the form "Is u in S?" can be answered by making few accesses to the memory. We study schemes for this problem that use space close to the information theoretic lower bound of Ω(nlog(m/n)) bits and yet answer queries by reading a small number of bits of the memory. We show that, for ε > 0, there is a scheme that stores O(n/ε²log m) bits and answers membership queries using a randomized algorithm that reads just one bit of memory and errs with probability at most ε. We consider schemes that make no error for queries in S but are allowed to err with probability at most ε for queries not in S. We show that there exist such schemes that store O((n/ε)² log m) bits and answer queries using just one bitprobe. If multiple probes are allowed, then the number of bits stored can be reduced to O(n1+δlog m) for any δ > 0. The schemes mentioned above are based on probabilistic constructions of set systems with small intersections. We show lower bounds that come close to our upper bounds (for a large range of n and ε): Schemes that answer queries with just one bitprobe and error probability ε must use Ω(n/εlog(1/ε) log m) bits of storage; if the error is restricted to queries not in S, then the scheme must use Ω(n²/ε² log (n/ε)log m) bits of storage. We also consider deterministic schemes for the static membership problem and show tradeoffs between space and the number of probes.