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

Rasmus Pagh

November 1998


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 tex2html_wrap_inline27, and show that for n-element subsets, constant worst case query time can be obtained using tex2html_wrap_inline31 bits of storage, where tex2html_wrap_inline33 is the minimum number of bits needed to represent all such subsets. The solution for dense subsets uses tex2html_wrap_inline35 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.


Last modified: 2003-06-08 by webmaster.