Dynamic Filters and Retrieval with a Single Memory Access

The second data structure is a dynamic retrieval data structure that functions as a key-value filter for short values (i.e., $O(\log \log n)$ bits per value). It supports insertions, deletions, and approximate value queries. If the queried key is present in the dataset, an approximate value query returns the correct value. If the queried key is not present in the dataset, a negative output is returned with a probability of at least $1-\varepsilon$. The key-value filter is compact and performs all operations in constant time.
For every operation, the number of memory access is $1+o(1)$, in expectation.

Joint work with Ioana Bercea and Tomer Even.