Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries

Abstract

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 [BFCK+22] has space consumption close to the information-theoretic optimum, using a total of \[ \log\binom{U}{n}+O(n\log^{(k)} n) \] bits, while supporting all operations in $O(k)$ time, for any parameter $k\le {\log }^{\ast }n$. The term $O({\log }^{(k)}n)=O(\underset{k}{\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+\hat{I}˜(1)}$, any dictionary with $O({\log }^{(k)}n)$ wasted bits per key must have expected operational time $\hat{I}\text{c◯}(k)$, in the cell-probe model with word-size $w=\hat{I}˜(\log U)$. Furthermore, if a dictionary stores values of $\hat{I}˜(\log U)$ bits, we show that regardless of the query time, it must have $\hat{I}\text{c◯}(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.

38 pages; in FOCS 2023