Low redundancy in static dictionaries with O(1) 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 Ω(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 stor-|U| age, where B = ⌈log2 ⌉ is the minimum number of bits needed to n represent all such subsets. For |U | = n log O(1) n the dictionary supports constant time rank queries.