A Model for Learned Bloom Filters, and Optimizing by Sandwiching
arXiv:1901.00902
Abstract
Recent work has suggested enhancing Bloom filters by using a pre-filter, based on applying machine learning to determine a function that models the data set the Bloom filter is meant to represent. Here we model such learned Bloom filters,, with the following outcomes: (1) we clarify what guarantees can and cannot be associated with such a structure; (2) we show how to estimate what size the learning function must obtain in order to obtain improved performance; (3) we provide a simple method, sandwiching, for optimizing learned Bloom filters; and (4) we propose a design and analysis approach for a learned Bloomier filter, based on our modeling approach.
12 pages; the complete version of the paper that appears in NIPS 2018, including addendum on learned Bloomier filters. arXiv admin note: substantial text overlap with arXiv:1802.00884, arXiv:1803.01474
References in corpus (3)
Cited by in corpus (22)
- Learning to Optimize: A Primer and A Benchmark
- Scheduling with Predictions and the Price of Misprediction
- Learning Space Partitions for Nearest Neighbor Search
- The Primal-Dual method for Learning Augmented Algorithms
- (Learned) Frequency Estimation Algorithms under Zipfian Distribution
- Adaptive Learned Bloom Filter (Ada-BF): Efficient Utilization of the Classifier
- Customizing ML Predictions for Online Algorithms
- A survey of sketches in traffic measurement: Design, Optimization, Application and Implementation
- The Supermarket Model with Known and Predicted Service Times
- Learning-based Support Estimation in Sublinear Time
- Faster Matchings via Learned Duals
- Online Algorithms for Multi-shop Ski Rental with Machine Learned Advice
- Learned Indexes for Dynamic Workloads
- Learning-Augmented -means Clustering
- Deep Learning Service for Efficient Data Distribution Aware Sorting
- NeuroDB: A Neural Network Framework for Answering Range Aggregate Queries and Beyond
- Frequency Estimation in Data Streams: Learning the Optimal Hashing Scheme
- Compressing (Multidimensional) Learned Bloom Filters
- Learning Based Distributed Tracking
- Online Primal-Dual Algorithms with Predictions for Packing Problems
- Hash Adaptive Bloom Filter
- Learning from Data to Speed-up Sorted Table Search Procedures: Methodology and Practical Guidelines