Low Redundancy in Dictionaries with O(1) Worst Case Lookup Time
AbstractA 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.
How to Cite
Pagh, R. (1998). Low Redundancy in Dictionaries with O(1) Worst Case Lookup Time. BRICS Report Series, 5(28). https://doi.org/10.7146/brics.v5i28.19434
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.