Optimal Time-Space Tradeoff for Dynamic Difference-Encoded Dictionaries

Abstract

The dynamic dictionary is a fundamental data structure that maintains a set $S\subset [U]$ of size $n$ (we assume $n=U^{1-\Theta(1)}$), supporting insertions, deletions and membership queries. Previous works mostly focused on constructing dictionaries that support operations in $O(1)$ time and use space as close to the \emph{information-theoretic bound} of $\log\binom{U}{n}$ bits as possible. In this paper, we study \emph{difference-encoded} dictionaries, which are dictionaries that use space close to the gap entropy $\text{gap}(S):=\sum_{i=2}^{|S|}\left(\lceil\log(x_i-x_{i-1}+1)\rceil+1\right)$ bits to store the set $S=\{x_1<\dots<x_n\}$. On many real-world datasets where the keys are clustered, we have $\text{gap}(S)\ll \log\binom{U}{n}$, making difference-encoded dictionaries more favorable than standard dictionaries in practice. Prior to this work, the best dynamic difference-encoded dictionary is by Blandford and Blelloch [SODA'04], whose construction supports operations in $O(\log n)$ time and uses $O(\text{gap}(S))$ bits of space. In the static case, Gupta, Hon, Shah and Vitter [DCC'06] presented a dictionary that uses $$ \text{gap}(S)+O(n\log\log U) $$ bits of space and supports membership queries in $O(\log\log n)$ time. In this work, we go beyond these bounds and fully settle the optimal time-space tradeoff for difference-encoded dictionaries. For an arbitrary parameter $0<\varepsilon<1/4$, we construct a dynamic dictionary that supports operations in $O(\log\varepsilon^{-1}/\log\log\varepsilon^{-1})$ expected amortized time and uses $$ \text{gap}(S)\cdot(1+O(\varepsilon))+O\left(n\log\frac{\text{gap}(S)}{n}\right) $$ bits of space. We also prove a matching lower bound, showing that our time-space tradeoff is optimal even in the \emph{static} case.