Adaptive Learned Bloom Filter (Ada-BF): Efficient Utilization of the Classifier

Abstract

Recent work suggests improving the performance of Bloom filter by incorporating a machine learning model as a binary classifier. However, such learned Bloom filter does not take full advantage of the predicted probability scores. We proposed new algorithms that generalize the learned Bloom filter by using the complete spectrum of the scores regions. We proved our algorithms have lower False Positive Rate (FPR) and memory usage compared with the existing approaches to learned Bloom filter. We also demonstrated the improved performance of our algorithms on real-world datasets.

14 pages, 6 figures

References in corpus (1)

• A Model for Learned Bloom Filters, and Optimizing by Sandwiching

Cited by in corpus (5)

• Proteus: A Self-Designing Range Filter
• Partitioned Learned Bloom Filter
• Shift-Table: A Low-latency Learned Index for Range Queries using Model Correction
• COAX: Correlation-Aware Indexing on Multidimensional Data with Soft Functional Dependencies
• Approximate Membership Query Filters with a False Positive Free Set