Resizable Retrieval (opens in new tab)

A dynamic retrieval data structure encodes a function $f:K \rightarrow [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 pose...