# A Critical Analysis of Classifier Selection in Learned Bloom Filters

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 57 references that are in the map.
- First posted on arXiv 28 Nov 2022.

## Builds on (most cited first, 11 of 11)

- [On the Properties of Neural Machine Translation: Encoder-Decoder Approaches](https://mlsanity.com/paper/1409.1259/) (2014)
- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [How Complex is your classification problem? A survey on measuring classification complexity](https://mlsanity.com/paper/1808.03591/) (2018)
- [A Model for Learned Bloom Filters, and Optimizing by Sandwiching](https://mlsanity.com/paper/1901.00902/) (2019)
- [RadixSpline: A Single-Pass Learned Index](https://mlsanity.com/paper/2004.14541/) (2020)
- [Benchmarking Learned Indexes](https://mlsanity.com/paper/2006.12804/) (2020)
- [Adaptive Learned Bloom Filter (Ada-BF): Efficient Utilization of the Classifier](https://mlsanity.com/paper/1910.09131/) (2019)
- [A Critical Analysis of Recursive Model Indexes](https://mlsanity.com/paper/2106.16166/) (2021)
- [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)

## Abstract (arXiv)

Learned Bloom Filters, i.e., models induced from data via machine learning techniques and solving the approximate set membership problem, have recently been introduced with the aim of enhancing the performance of standard Bloom Filters, with special focus on space occupancy. Unlike in the classical case, the "complexity" of the data used to build the filter might heavily impact on its performance. Therefore, here we propose the first in-depth analysis, to the best of our knowledge, for the performance assessment of a given Learned Bloom Filter, in conjunction with a given classifier, on a dataset of a given classification complexity. Indeed, we propose a novel methodology, supported by software, for designing, analyzing and implementing Learned Bloom Filters in function of specific constraints on their multi-criteria nature (that is, constraints involving space efficiency, false positive rate, and reject time). Our experiments show that the proposed methodology and the supporting software are valid and useful: we find out that only two classifiers have desirable properties in relation to problems with different data complexity, and, interestingly, none of them has been considered so far in the literature. We also experimentally show that the Sandwiched variant of Learned Bloom filters is the most robust to data complexity and classifier performance variability, as well as those usually having smaller reject times. The software can be readily used to test new Learned Bloom Filter proposals, which can be compared with the best ones identified here.