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 $\mathrm{\Sigma }$, the \emph{static dictionary} problem asks to preprocess these (key, value) pairs into a data structure, supporting value-retrieval queries: for any given $x\in [U]$, $\mathtt{v}\mathtt{a}\mathtt{l}\mathtt{R}\mathtt{e}\mathtt{t}(x)$ must return the value associated with $x$ if $x\in S$, or return $\mathrm{\perp }$ if $x\notin S$\mathrm{.}Thespecialcasewhere$|\Sigma|=1$ is called the \emph{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 $$\mathtt{O}\mathtt{P}\mathtt{T}$:= \lceil\lg_2\binom{U}{n}+n\lg_2|\Sigma|\rceil$ bits, which could be much less. In this paper, we design a randomized dictionary data structure using $\mathtt{O}\mathtt{P}\mathtt{T}+\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\lg n+O(\lg \lg \lg \lg \lg U)$ bits of space, and it has \emph{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 $\mathrm{\mid }\mathrm{\Sigma }\mathrm{\mid }$, and not the input. Previously, even for membership queries and $U\le n^{O(1)}$, the best known data structure with constant query time requires $\mathtt{O}\mathtt{P}\mathtt{T}+n\mathrm{/}\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\lg n$ bits of space (Pagh [Pag01] and P\v{a}tra\c{s}cu [Pat08]); the best-known using $\mathtt{O}\mathtt{P}\mathtt{T}+n^{0.999}$ space has query time $O(\lg n)$; the only known non-trivial data structure with $\mathtt{O}\mathtt{P}\mathtt{T}+n^{0.001}$ space has $O(\lg n)$ query time and requires a lookup table of size $\ge n^{2.99}$ (!). Our new data structure answers open questions by P\v{a}tra\c{s}cu and Thorup [Pat08,Tho13]. We also present a scheme that compresses a sequence $X\in {\mathrm{\Sigma }}^n$ to its zeroth order (empirical) entropy up to $\mathrm{\mid }\mathrm{\Sigma }\mathrm{\mid }\cdot \mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\lg n$ extra bits, supporting decoding each $X_i$ in $O(\lg \mathrm{\mid }\mathrm{\Sigma }\mathrm{\mid })$ expected time.