View Full Document

LOW REDUNDANCY IN STATIC DICTIONARIES WITH CONSTANT QUERY TIME∗



View the full content.
View Full Document
View Full Document

4 views

Unformatted text preview:

c 2001 Society for Industrial and Applied Mathematics SIAM J COMPUT Vol 31 No 2 pp 353 363 LOW REDUNDANCY IN STATIC DICTIONARIES WITH CONSTANT QUERY TIME RASMUS PAGH Abstract A static dictionary is a data structure storing subsets of a nite universe U answering membership queries We show that on a unit cost RAM with word size log U a static dictionary for n element sets with constant worst case query time can be obtained using B O log log U o n bits of storage where B log2 U is the minimum number of bits needed to represent all nn element subsets of U Key words information retrieval dictionary hashing redundancy compression AMS subject classi cations 68P10 68P20 68P30 PII S0097539700369909 1 Introduction Consider the problem of storing a subset S of a nite set U such that membership queries u S can be answered in worst case constant time on a unit cost RAM We are interested only in membership queries so we assume that U 0 m 1 Also we restrict attention to the case where the RAM has word size log m In particular elements of U can be represented within a constant number of machine words and the usual RAM operations including multiplication on numbers of size mO 1 can be done in constant time Our goal will be to solve this the static dictionary problem using little memory measured in consecutive bits We express the complexity in terms of m U and n S and often consider the asymptotics when n is a function of m Since the queries can distinguish any two subsets of U we need at least m n di erent memory m con gurations that is at least B log n bits Log is base 2 throughout this paper We will focus on the case n m 2 and leave the symmetry implications to the reader Using Stirling s approximation to the factorial function one can derive the following where e 2 718 denotes the base of the natural logarithm 1 1 B n log e m n n2 m O log n It should be noted that using space very close to B is only possible if elements of S are stored implicitly since explicitly representing all



Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view LOW REDUNDANCY IN STATIC DICTIONARIES WITH CONSTANT QUERY TIME∗ and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view LOW REDUNDANCY IN STATIC DICTIONARIES WITH CONSTANT QUERY TIME∗ and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?