BARC talk by Navid Eslami

Tuesday, April 29, 2025, Navid Eslami, PhD student at the University of Toronto, Canada, will give a talk on "Range Filters".

Abstract:
Range filters are compact probabilistic data structures that answer approximate range emptiness queries. They are used in many domains, e.g., in key-value stores, to quickly rule out the existence of keys in a given query range and avoid having to search for them in storage. However, all existing range filters exhibit at least one of the following shortcomings: (1) they do not provide a rigorous false positive rate guarantee for any workload, (2) they have slow queries, (3) they are static structures, and (4) they do not support variable-length keys or query ranges. In this talk, we first present Memento filter, the first range filter to simultaneously provide a worst-case false positive rate guarantee, dynamicity, and fast operations. Memento filter matches the information-theoretic memory lower bound of any range filter for answering (worst-case) range queries of bounded length over fixed-length keys. We then circumvent the lower bound by considering  relaxed false positive rate guarantee that holds for “well-behaved” data distributions. We introduce Diva, the first range filter to provide this relaxed guarantee while supporting variable-length keys and queries, dynamic operations, and high performance, all at the same time.

Bio:
Navid is a second-year PhD student in the SysNet group at the University of Toronto. He is a member of the ORCA Lab, where he has the pleasure of being supervised by Prof. Niv Dayan. Navid designs data structures tailored to database systems, focusing on randomized and sketching data structures. He also optimizes his data structures to leverage the power and speed of modern hardware to the fullest, making them lightning-fast!

Host:
Rasmus Pagh