mlsanityData to 7 Oct 2026

A Model for Learned Bloom Filters, and Optimizing by Sandwiching

arXiv 1901.00902 ↗First posted 3 Jan 2019cs.LG cs.DB stat.MLcited by 64

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 64 papers in the map (data through 7 Oct 2026). First posted on arXiv 3 Jan 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 12; 2022: 14; 2023: 5; 2024: 11; 2025: 15; 2026: 7.

64 papers.

Sort:

  1. 2021Learning to Optimize: A Primer and A Benchmarkcited by 206
  2. 2021Faster Matchings via Learned Dualscited by 56
  3. 2021Learning-Augmented k-means Clusteringcited by 26
  4. 2022Online Algorithms with Multiple Predictionscited by 22
  5. 2022Customizing ML Predictions for Online Algorithmscited by 21
  6. 2022Triangle and Four Cycle Counting with Predictions in Graph Streamscited by 20
  7. 2021Learning-based Support Estimation in Sublinear Timecited by 16
  8. 2021Can Q-Learning be Improved with Advice?cited by 13
  9. 2024Online bipartite matching with imperfect advicecited by 13
  10. 2022A Regression Approach to Learning-Augmented Online Algorithmscited by 12
  11. 2021(Optimal) Online Bipartite Matching with Degree Informationcited by 11
  12. 2022Learning-Augmented Algorithms for Online Linear and Semidefinite Programmingcited by 11
38 more
  1. 2021Double Coverage with Machine-Learned Advicecited by 10
  2. 2022Improved Learning-augmented Algorithms for k-means and k-medians Clusteringcited by 10
  3. 2023Active causal structure learning with advicecited by 10
  4. 2023Improved Frequency Estimation Algorithms with and without Predictionscited by 10
  5. 2022Single-Leg Revenue Management with Advicecited by 9
  6. 2022Learning-Augmented Algorithms for Online TSP on the Linecited by 8
  7. 2023Online List Labeling with Predictionscited by 5
  8. 2021DeepBF: Malicious URL detection using Learned Bloom Filter and Evolutionary Deep Learningcited by 4
  9. 2021Learned Sorted Table Search and Static Indexes in Small Model Spacecited by 4
  10. 2021On the Choice of General Purpose Classifiers in Learned Bloom Filters: An Initial Analysis Within Basic Filterscited by 4
  11. 2024Learning-Augmented Search Data Structurescited by 4
  12. 2024Learning-Based Algorithms for Graph Searching Problemscited by 4
  13. 2024A Survey of Learned Indexes for the Multi-dimensional Spacecited by 4
  14. 2024Learning multivariate Gaussians with imperfect advicecited by 4
  15. 2025Approximate Proportionality in Online Fair Divisioncited by 4
  16. 2021Online Capacity Scaling Augmented With Unreliable Machine Learning Predictionscited by 3
  17. 2021Online Primal-Dual Algorithms with Predictions for Packing Problemscited by 3
  18. 2022On the Suitability of Neural Networks as Building Blocks for The Design of Efficient Learned Indexescited by 3
  19. 2022Daisy Bloom Filterscited by 3
  20. 2024Learning-Based Heavy Hitters and Flow Frequency Estimation in Streamscited by 3
  21. 2025Incremental Approximate Single-Source Shortest Paths with Predictionscited by 3
  22. 2022Proteus: A Self-Designing Range Filtercited by 2
  23. 2024Primal-Dual Algorithms with Predictions for Online Bounded Allocation and Ad-Auctions Problemscited by 2
  24. 2024Fast and Accurate Triangle Counting in Graph Streams Using Predictionscited by 2
  25. 2025Learning-Augmented Frequent Directionscited by 2
  26. 2026Context Compaction Theorycited by 2
  27. 2022Compressing (Multidimensional) Learned Bloom Filterscited by 1
  28. 2023Online Covering with Multiple Expertscited by 1
  29. 2024Credence: Augmenting Datacenter Switch Buffer Sharing with ML Predictionscited by 1
  30. 2024Learning-based Sketches for Frequency Estimation in Data Streams without Ground Truthcited by 1
  31. 2025LotusFilter: Fast Diverse Nearest Neighbor Search via a Learned Cutoff Tablecited by 1
  32. 2025Optimizing Health Coverage in Ethiopia: A Learning-augmented Approach and Persistent Proportionality Under an Online Budgetcited by 1
  33. 2025Learning-Augmented Streaming Algorithms for Correlation Clusteringcited by 1
  34. 2025Product distribution learning with imperfect advicecited by 1
  35. 2026Mathematical Foundations of Poisoning Attacks on Linear Regression over Cumulative Distribution Functionscited by 1
  36. 2022Testing the Robustness of Learned Index Structurescited by 0
  37. 2022A Critical Analysis of Classifier Selection in Learned Bloom Filterscited by 0
  38. 2023From Specific to Generic Learned Sorted Set Dictionaries: A Theoretically Sound Paradigm Yelding Competitive Data Structural Boosters in Practicecited by 0

50 most cited of 64 All 64 (JSON)