Abstract:
A static dictionary is a data structure for storing
subsets of a finite universe U, so that membership queries can be answered
efficiently. We study this problem in a unit cost RAM model with word size
, and show that for n-element subsets, constant worst
case query time can be obtained using 
bits of
storage, where 
is the minimum
number of bits needed to represent all such subsets. The solution for dense
subsets uses 
bits of storage, and
supports constant time rank queries. In a dynamic setting, allowing
insertions and deletions, our techniques give an O(B) bit space
usage
Available as PostScript, PDF.