Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries

A dictionary data structure maintains a set of at most n keys from the universe $[U]$ under key insertions and deletions, such that given a query $x \in[U]$, it returns if x is in the set. Some variants also store values associated to the keys such that given a query x, the value associated to x is returned when x is in the set.This fundamental data structure problem has been studied for six decades since the introduction of hash tables in 1953. A hash table occupies $O(n \log U)$ bits of space with constant time per operation in expectation. There has been a vast literature on improving its time and space usage. The state-of-the-art dictionary by Bender, Farach-Colton, Kuszmaul, Kuszmaul and Liu [1] has space consumption close to the information-theoretic optimum, using a total of \begin{equation*}\log \begin{pmatrix} U \\ n \end{pmatrix}+On\log ^{\left(k\right)} n\end{equation*} bits, while supporting all operations in $O(k)$ time, for any parameter $k \leq \log ^{*} n$. The term $O\left(\log ^{(k)} n\right)=O(\underbrace{\log \cdots \log n})$ is referred to as the wasted bits per key.In this paper, we prove a matching cell-probe lower bound: For $U=n^{1+\Theta(1)}$, any dictionary with $O\left(\log ^{(k)} n\right)$ wasted bits per key must have expected operational time $\Omega(k)$, in the cell-probe model with word-size $w=\Theta(\log U)$. Furthermore, if a dictionary stores values of $\Theta(\log U)$ bits, we show that regardless of the query time, it must have $\Omega(k)$ expected update time. It is worth noting that this is the first cell-probe lower bound on the trade-off between space and update time for general data structures.