# Partitioned Learned Bloom Filter

arXiv: https://arxiv.org/abs/2006.03176 · HTML: https://mlsanity.com/paper/2006.03176/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jun 2020.

## Built on by (most cited first, 10 of 10)

- [Faster Matchings via Learned Duals](https://mlsanity.com/paper/2107.09770/) (2021)
- [Triangle and Four Cycle Counting with Predictions in Graph Streams](https://mlsanity.com/paper/2203.09572/) (2022)
- [Learned Sorted Table Search and Static Indexes in Small Model Space](https://mlsanity.com/paper/2107.09480/) (2021)
- [On the Choice of General Purpose Classifiers in Learned Bloom Filters: An Initial Analysis Within Basic Filters](https://mlsanity.com/paper/2112.06563/) (2021)
- [On the Suitability of Neural Networks as Building Blocks for The Design of Efficient Learned Indexes](https://mlsanity.com/paper/2203.14777/) (2022)
- [Proteus: A Self-Designing Range Filter](https://mlsanity.com/paper/2207.01503/) (2022)
- [Compressing (Multidimensional) Learned Bloom Filters](https://mlsanity.com/paper/2208.03029/) (2022)
- [Mathematical Foundations of Poisoning Attacks on Linear Regression over Cumulative Distribution Functions](https://mlsanity.com/paper/2603.00537/) (2026)
- [Mergeable Model-Side Aggregation States for Long-Context Language Models](https://mlsanity.com/paper/2607.26448/) (2026)
- [From Specific to Generic Learned Sorted Set Dictionaries: A Theoretically Sound Paradigm Yelding Competitive Data Structural Boosters in Practice](https://mlsanity.com/paper/2309.00946/) (2023)

## Abstract (arXiv)

Bloom filters are space-efficient probabilistic data structures that are used to test whether an element is a member of a set, and may return false positives. Recently, variations referred to as learned Bloom filters were developed that can provide improved performance in terms of the rate of false positives, by using a learned model for the represented set. However, previous methods for learned Bloom filters do not take full advantage of the learned model. Here we show how to frame the problem of optimal model utilization as an optimization problem, and using our framework derive algorithms that can achieve near-optimal performance in many cases. Experimental results from both simulated and real-world datasets show significant performance improvements from our optimization approach over both the original learned Bloom filter constructions and previously proposed heuristic improvements.