Nearly Optimal Static Las Vegas Succinct Dictionary

Abstract

Given a set $S$ of $n$ (distinct) keys from key space $[U]$, each associated with a value from $\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{valRet}(x)$ must return the value associated with $x$ if $x\in S$, or return $\perp$ if $x\notin S$. The special case where $|\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{OPT}:=\lceil {\lg }_2\left(\genfrac{}{}{0ex}{}{U}{n}\right)+n{\lg }_2|\Sigma |\rceil$ bits, which could be much less. In this paper, we design a randomized dictionary data structure using $\mathtt{OPT}+\mathrm{poly}\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 $|\Sigma |$, 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{OPT}+n/\mathrm{poly}\lg n$ bits of space (Pagh [Pag01] and Pǎtraşcu [Pat08]); the best-known using $\mathtt{OPT}+n^{0.999}$ space has query time $O(\lg n)$; the only known non-trivial data structure with $\mathtt{OPT}+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ǎtraşcu and Thorup [Pat08,Tho13]. We also present a scheme that compresses a sequence $X\in {\Sigma }^n$ to its zeroth order (empirical) entropy up to $|\Sigma |\cdot \mathrm{poly}\lg n$ extra bits, supporting decoding each $X_i$ in $O(\lg |\Sigma |)$ expected time.

preliminary version appeared in STOC'20