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∈[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(nlogU)�(�log⁡�) 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 has space consumption close to the information-theoretic optimum, using a total of

log(Un)+O(nlog(k)n)log⁡(��)+�(�log(�)⁡�)

bits, while supporting all operations in O(k)�(�) time, for any parameter k≤log∗n�≤log∗⁡�. The term O(log(k)n)=O(log⋯logkn)�(log(�)⁡�)=�(log⁡⋯log⏟��) is referred to as the wasted bits per key.

In this talk, we show a matching cell-probe lower bound: For U=n1+Θ(1)�=�1+Θ(1), any dictionary with O(log(k)n)�(log(�)⁡�) wasted bits per key must have expected operational time Ω(k)Ω(�), in the cell-probe model with word-size w=Θ(logU)�=Θ(log⁡�). Furthermore, if a dictionary stores values of Θ(logU)Θ(log⁡�) bits, we show that regardless of the query time, it must have Ω(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.

Joint work with Tianxiao Li, Jingxun Liang and Renfei Zhou.