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 is an element of [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 log (U n) + O(n log((k)) n) bits, while supporting all operations in O(k) time, for any parameter k <= log * n. The term O(log((k)) n) = O(log ... log n k) 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(log((k)) n) wasted bits per key must have expected operational time Omega(k), in the cellprobe model with word-size w = Theta(logU). 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.