Since 2014
Low Redundancy in Dictionaries with O(1) Worst Case Lookup Time
BRICS Report Series
View Archive Info| Field | Value | |
| Title |
Low Redundancy in Dictionaries with O(1) Worst Case Lookup Time
|
|
| Creator |
Pagh, Rasmus
|
|
| Description |
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 allsuch 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.
|
|
| Publisher |
Aarhus University
|
|
| Contributor |
—
|
|
| Date |
1998-01-28
|
|
| Type |
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion — |
|
| Format |
application/pdf
|
|
| Identifier |
https://tidsskrift.dk/brics/article/view/19434
10.7146/brics.v5i28.19434 |
|
| Source |
BRICS Report Series; No 28 (1998): RS-28 Low Redundancy in Dictionaries with O(1) Worst Case Lookup Time
BRICS Report Series; No 28 (1998): RS-28 Low Redundancy in Dictionaries with O(1) Worst Case Lookup Time 1601-5355 0909-0878 |
|
| Language |
eng
|
|
| Relation |
https://tidsskrift.dk/brics/article/view/19434/17055
|
|
| Rights |
Copyright (c) 2014 BRICS Report Series
|
|