TY - GEN

T1 - Nearly optimal static Las Vegas succinct dictionary

AU - Yu, Huacheng

N1 - Publisher Copyright:
© 2020 ACM.

PY - 2020/6/8

Y1 - 2020/6/8

N2 - Given a set S of n (distinct) keys from key space [U], each associated with a value from ς, the static dictionary problem asks to preprocess these (key, value) pairs into a data structure, supporting value-retrieval queries: for any given xg [U], valRet(x) must return the value associated with x if xg S, or return g¥ if xg‰ S. The special case where |ς|=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:= glg2(Un)+nlg2|ς|g‰ bits, which could be much less. In this paper, we design a randomized dictionary data structure using OPT+lgn+O(lglglglglgU) bits of space, and it has expected constant query time, assuming the query algorithm can access an external lookup table of size n0.001. The lookup table depends only on U, n and |ς|, and not the input. Previously, even for membership queries and U≤ nO(1), the best known data structure with constant query time requires OPT+n/lgn bits of space by Pagh (SIAM J. Comput. 2001) and PÇtraşcu (FOCS 2008); the best known using OPT+n0.999 space has query time O(lgn); the only known non-trivial data structure with OPT+n0.001 space has O(lgn) query time and requires a lookup table of size ≥ n2.99 (!). Our new data structure answers open questions by PÇtraşcu and Thorup.

AB - Given a set S of n (distinct) keys from key space [U], each associated with a value from ς, the static dictionary problem asks to preprocess these (key, value) pairs into a data structure, supporting value-retrieval queries: for any given xg [U], valRet(x) must return the value associated with x if xg S, or return g¥ if xg‰ S. The special case where |ς|=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:= glg2(Un)+nlg2|ς|g‰ bits, which could be much less. In this paper, we design a randomized dictionary data structure using OPT+lgn+O(lglglglglgU) bits of space, and it has expected constant query time, assuming the query algorithm can access an external lookup table of size n0.001. The lookup table depends only on U, n and |ς|, and not the input. Previously, even for membership queries and U≤ nO(1), the best known data structure with constant query time requires OPT+n/lgn bits of space by Pagh (SIAM J. Comput. 2001) and PÇtraşcu (FOCS 2008); the best known using OPT+n0.999 space has query time O(lgn); the only known non-trivial data structure with OPT+n0.001 space has O(lgn) query time and requires a lookup table of size ≥ n2.99 (!). Our new data structure answers open questions by PÇtraşcu and Thorup.

KW - Dictionary

KW - Las vegas algorithm

KW - Locally decodable source coding

KW - Succinct data structure

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

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

U2 - 10.1145/3357713.3384274

DO - 10.1145/3357713.3384274

M3 - Conference contribution

AN - SCOPUS:85086763368

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 1389

EP - 1401

BT - STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing

A2 - Makarychev, Konstantin

A2 - Makarychev, Yury

A2 - Tulsiani, Madhur

A2 - Kamath, Gautam

A2 - Chuzhoy, Julia

PB - Association for Computing Machinery

T2 - 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020

Y2 - 22 June 2020 through 26 June 2020

ER -