Low Redundancy in Dictionaries with O(1) Worst Case Lookup Time

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  Omega(log |U|), and show that for n-element subsets,
constant worst case query time can be obtained using B +O(log log |U|)+o(n) bits of storage, where B = [log2 (|U| / n)]
is the minimum number of bits needed to represent all
such subsets. The solution for dense subsets uses B + O( |U| log log |U| / log |U| ) 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.