Low redundancy in static dictionaries with constant query time

Authors
Pagh, R
Citation
R. Pagh, Low redundancy in static dictionaries with constant query time, SIAM J COMP, 31(2), 2001, pp. 353-363
Citations number
17
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
0097-5397 → ACNP
Volume
31
Issue
2
Year of publication
2001
Pages
353 - 363
Database
ISI
SICI code
0097-5397(20011011)31:2<353:LRISDW>2.0.ZU;2-Y
Abstract
A static dictionary is a data structure storing subsets of a finite univers e U, answering membership queries. We show that on a unit cost RAM with wor d size Theta (log |U|), a static dictionary for n-element sets with constan t worst case query time can be obtained using B+O ( log log |U|) + o(n) bit s of storage, where B = inverted right perpendicular log(2)((|U|)(n))invert ed left perpendicular is the minimum number of bits needed to represent all n-element subsets of U.