Learning Bloom Filters: A Review

Data structures for storing sets are crucial in various applications, including database systems and data science, as they enable fast membership queries, deduplication, and containment checks. The most prominent examples in this field are Bloom filters (BFs), which pose a randomized, approximate data structure for storing set properties based on hash mappings from the data domain to a binary array. Recently, variants of BFs have been proposed to achieve lower false positive rates with a smaller memory footprint by learning the underlying data distributions. This paper provides a comprehensive review of the structure underlying such learned variants, including the proposed learned oracles and backup filters that ensure no false positives occur. The research trends are identified, along with open challenges, to present possible future research directions for learned approaches to the approximate set membership problem.