Campus Event Calendar

Event Entry

What and Who

Dynamic Filters and Retrieval with a Single Memory Access

Guy Even
Tel-aviv University
AG1 Mittagsseminar (own work)
AG 1  
AG Audience

Date, Time and Location

Monday, 3 July 2023
30 Minutes
E1 4


We introduce two probabilistic data structures within the word RAM model. The first is a dynamic filter that allows for approximate membership queries, insertions, and deletions. This filter is space-efficient and performs all operations in constant time with a single memory access per operation.

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.


Roohani Sharma
+49 681 9325 1116
--email hidden

Virtual Meeting Details

passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

If you wish to attend the talk online but do not have the zoom password, contact Roohani Sharma at

Roohani Sharma, 07/01/2023 12:48
Roohani Sharma, 06/13/2023 12:29 -- Created document.