Resizable Retrieval

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 $\mathtt{\text{Insert}}$$(x,f(x))$ for $x\mathrm{\notin }K$, and deletions $\mathtt{\text{Delete}}$$(x)$ for $x\in K$. Given an upper bound $N$ on $\mathrm{\mid }K\mathrm{\mid }$, it is known how to solve the dynamic retrieval problem with $O(1)$-time operations and space $Nv+O(N\log \log (U\mathrm{/}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.