Low Redundancy in Static Dictionaries with Constant Query Time

Abstract

A static dictionary is a data structure storing subsets of a finite universe U, answering membership queries. We show that on a unit cost RAM with word size $\Theta(\log |U|)$, a static dictionary for n-element sets with constant worst case query time can be obtained using $B+O(\log\log |U|)+o(n)$ bits of storage, where $B=\ceiling{\log_2\binom{|U|}{n}}$ is the minimum number of bits needed to represent all n-element subsets of U.