Partitioned Learned Bloom Filters
Abstract
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.
Cite
Text
Vaidya et al. "Partitioned Learned Bloom Filters." International Conference on Learning Representations, 2021.Markdown
[Vaidya et al. "Partitioned Learned Bloom Filters." International Conference on Learning Representations, 2021.](https://mlanthology.org/iclr/2021/vaidya2021iclr-partitioned/)BibTeX
@inproceedings{vaidya2021iclr-partitioned,
title = {{Partitioned Learned Bloom Filters}},
author = {Vaidya, Kapil and Knorr, Eric and Mitzenmacher, Michael and Kraska, Tim},
booktitle = {International Conference on Learning Representations},
year = {2021},
url = {https://mlanthology.org/iclr/2021/vaidya2021iclr-partitioned/}
}