Adaptive Learned Bloom Filter (Ada-BF): Efficient Utilization of the Classifier
This work addresses efficiency bottlenecks in data structures for large-scale systems, representing an incremental but practically important advancement.
The paper tackles the problem of inefficient utilization of classifier probability scores in learned Bloom filters, proposing new algorithms that achieve lower false positive rates and reduced memory usage compared to existing approaches, with demonstrated improvements on real-world datasets.
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.