# Optimal Time-Space Tradeoff for Dynamic Difference-Encoded Dictionaries

Preprint · Guy E. Blelloch, Yang Hu, William Kuszmaul, Jingxun Liang, Renfei Zhou

- Archive id: arxiv:2608.06077
- Published: 2026-08-06
- arXiv: https://arxiv.org/abs/2608.06077
- Source URL: https://arxiv.org/abs/2608.06077
- PDF: https://arxiv.org/pdf/2608.06077
- Provenance: arxiv

## Abstract

The dynamic dictionary is a fundamental data structure that maintains a set $S\\subset \[U\]$ of size $n$ (we assume $n=U^{1-Θ(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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.