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.