Beyond Bloom: A Tutorial on Future Feature-Rich Filters

Filters, such as Bloom, quotient, and cuckoo, save space by maintaining an approximate representation of a set and occasionally returning false positives. Filters play a critical role in building modern dataintensive applications and are used across various domains such as databases, storage engines, computational biology, cyber- security, and networks. There has been extensive research on filters in the past few decades resulting in filters with much improved performance and features. Yet modern data-intensive applications are still designed around the limitations of traditional filters resulting in complex designs and sub-optimal performance. This tutorial aims to bring together researchers at the forefront of filter data structure research to help the database community learn about the recent advancements in the theory and practice of filters. The tutorial will cover real-world case studies of redesigning applications using the modern filter APIs to achieve simplicity and improved application performance. The tutorial will further help uncover the open research problems, both in theory and systems, and increase interaction among researchers to tackle those problems.