Resizable Retrieval

Abstract

A dynamic retrieval data structure encodes a function $f:K\to [2^v]$ for a set $K\subseteq [U]$, while supporting queries $f(x)$ for $x\in K$, insertions \texttt{Insert}$(x,f(x))$ for $x\notin K$, and deletions \texttt{Delete}$(x)$ for $x\in K$. Given an upper bound $N$ on $|K|$, it is known how to solve the dynamic retrieval problem with $O(1)$-time operations and space $Nv+O(N\log \log (U/N))$ bits. An open question, first posed by Demaine et al. in 2006, is whether a similar bound can be achieved with a resizable data structure, whose space bound is parameterized by the \emph{current} size $n$ of $K$. We answer this question in the affirmative and prove matching lower bounds for the space-time trade-off achieved by our data structure. We also give corollaries for space-efficient memory allocation and dynamic filters.