Nearly Optimal Static Las Vegas Succinct Dictionary

Given a set S of n (distinct) keys from key space [U], each associated with a value from Sigma, the static dictionary problem asks to preprocess these (key, value) pairs into a data structure, supporting value retrieval queries: for any given x is an element of [U], valRet(x) must return the value associated with x if x is an element of S, or return perpendicular to if x is not an element of S. The special case where vertical bar Sigma vertical bar = 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 := inverted right perendicularlg(2)((U)(n)) + n lg(2) Sigma vertical bar inverted left perendicular bits, which could be much less. In this paper, we design a randomized dictionary data structure using OPT + poly lg n + O(1g lg lg lg lg U) bits of space, and it has expected constant query time, assuming the query algorithm can access an external lookup table of size n(0.001). The lookup table depends only on U, n and vertical bar Sigma vertical bar, and not the input. Previously, even for membership queries and U <= n(O(1)) the best known data structure with constant query time requires OPT + n/poly lg n bits of space by Pagh (SIAM J. Comput. 2001) and PatraKu (FOCS 2008); the best known using OPT + n0.999 space has query time O(lg n); the only known non-trivial data structure with OPT+ n(0.0001) space has O(lg n) query time and requires a lookup table of size >= n(2.99) (!). Our new data structure answers open questions by PatraKu and Thorup.