TY - JOUR

T1 - NEARLY OPTIMAL STATIC LAS VEGAS SUCCINCT DICTIONARY

AU - Huacheng, Y. U.

N1 - Funding Information: Acknowledgment. The author would like to thank anonymous reviewers for helpful comments. Publisher Copyright: © 2022 Society for Industrial and Applied Mathematics

PY - 2022

Y1 - 2022

N2 - For positive integers U, n, and \sigma , given a set S of n (distinct) keys from key space [U], each associated with a value from [\sigma ], the static dictionary problem asks one to preprocess these (key, value) pairs into a data structure, supporting value-retrieval queries: for any given x \in [U], valRet(x) must return the value associated with x if x \in S, or return \bot if x \in / S. The special case where \sigma = 1 is called the membership problem. The ``textbook"" solution is to use a hash table, which occupies linear space and answers each query in constant time. On the other hand, the minimum possible space to encode all (key, value) pairs is only OPT:= \lceil lg2\bigl(Un\bigr) +n lg2 \sigma \rceil bits, which could be much smaller than a hash table. In this paper, we design a randomized dictionary data structure using OPT+poly lg n+ O(lg(\ell ) U) bits of space, and it has expected constant query time, assuming the query algorithm can access an external lookup table of size n\epsilon for any constant \ell and \epsilon . The lookup table depends only on U, n, and \sigma , and not the input. Previously, even for membership queries and U \leq nO(1), the best known data structure with constant query time requires OPT+n/poly lg n bits of space (Pagh [SIAM J. Comput., 31 (2001), pp. 353-363] and P\v atra\c scu [FOCS, IEEE Computer Society, Los Alamitos, CA, 2008, pp. 305-313]); the best known using OPT + n1 - \epsilon space has query time O(lg n). Our new data structure answers open questions by P\v atra\c scu and Thorup [FOCS, IEEE Computer Society, Los Alamitos, CA, 2008, pp. 305-313; Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 109 (2013), pp. 7-13]. We also present a scheme that compresses a sequence X \in [\sigma ]n to its zeroth order (empirical) entropy up to \sigma \cdot poly lg n extra bits, supporting decoding each Xi in O(lg \sigma ) expected time.

AB - For positive integers U, n, and \sigma , given a set S of n (distinct) keys from key space [U], each associated with a value from [\sigma ], the static dictionary problem asks one to preprocess these (key, value) pairs into a data structure, supporting value-retrieval queries: for any given x \in [U], valRet(x) must return the value associated with x if x \in S, or return \bot if x \in / S. The special case where \sigma = 1 is called the membership problem. The ``textbook"" solution is to use a hash table, which occupies linear space and answers each query in constant time. On the other hand, the minimum possible space to encode all (key, value) pairs is only OPT:= \lceil lg2\bigl(Un\bigr) +n lg2 \sigma \rceil bits, which could be much smaller than a hash table. In this paper, we design a randomized dictionary data structure using OPT+poly lg n+ O(lg(\ell ) U) bits of space, and it has expected constant query time, assuming the query algorithm can access an external lookup table of size n\epsilon for any constant \ell and \epsilon . The lookup table depends only on U, n, and \sigma , and not the input. Previously, even for membership queries and U \leq nO(1), the best known data structure with constant query time requires OPT+n/poly lg n bits of space (Pagh [SIAM J. Comput., 31 (2001), pp. 353-363] and P\v atra\c scu [FOCS, IEEE Computer Society, Los Alamitos, CA, 2008, pp. 305-313]); the best known using OPT + n1 - \epsilon space has query time O(lg n). Our new data structure answers open questions by P\v atra\c scu and Thorup [FOCS, IEEE Computer Society, Los Alamitos, CA, 2008, pp. 305-313; Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 109 (2013), pp. 7-13]. We also present a scheme that compresses a sequence X \in [\sigma ]n to its zeroth order (empirical) entropy up to \sigma \cdot poly lg n extra bits, supporting decoding each Xi in O(lg \sigma ) expected time.

KW - dictionary

KW - perfect hashing

KW - succinct data structure

UR - http://www.scopus.com/inward/record.url?scp=85134889302&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85134889302&partnerID=8YFLogxK

U2 - https://doi.org/10.1137/20M1363649

DO - https://doi.org/10.1137/20M1363649

M3 - Article

SN - 0097-5397

VL - 51

SP - 174

EP - 249

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 3

ER -