Low Redundancy in Dictionaries with O(1) Worst Case Lookup Time
Rasmus Pagh November 1998 |
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. |