# Daisy Bloom Filters

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 48 references that are in the map.
- First posted on arXiv 30 May 2022.

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

- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [A Model for Learned Bloom Filters, and Optimizing by Sandwiching](https://mlsanity.com/paper/1901.00902/) (2019)
- [FITing-Tree: A Data-aware Index Structure](https://mlsanity.com/paper/1801.10207/) (2018)
- [Learning-based Support Estimation in Sublinear Time](https://mlsanity.com/paper/2106.08396/) (2021)
- [Testing probability distributions underlying aggregated data](https://mlsanity.com/paper/1402.3835/) (2014)
- [Adaptive Learned Bloom Filter (Ada-BF): Efficient Utilization of the Classifier](https://mlsanity.com/paper/1910.09131/) (2019)
- [Bloom Filters, Adaptivity, and the Dictionary Problem](https://mlsanity.com/paper/1711.01616/) (2017)
- [How to Approximate A Set Without Knowing Its Size In Advance](https://mlsanity.com/paper/1304.1188/) (2013)
- [Bloom Filters in Adversarial Environments](https://mlsanity.com/paper/1412.8356/) (2014)
- [Adaptive Cuckoo Filters](https://mlsanity.com/paper/1704.06818/) (2017)
- [Optimizing Bloom Filter: Challenges, Solutions, and Comparisons](https://mlsanity.com/paper/1804.04777/) (2018)
- [On the Optimal Time/Space Tradeoff for Hash Tables](https://mlsanity.com/paper/2111.00602/) (2021)
- [Succinct Filters for Sets of Unknown Sizes](https://mlsanity.com/paper/2004.12465/) (2020)
- [A Dynamic Space-Efficient Filter with Constant Time Operations](https://mlsanity.com/paper/2005.01098/) (2020)
- [Prefix Filter: Practically and Theoretically Better Than Bloom](https://mlsanity.com/paper/2203.17139/) (2022)

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

- [Online List Labeling with Predictions](https://mlsanity.com/paper/2305.10536/) (2023)
- [Incremental Approximate Single-Source Shortest Paths with Predictions](https://mlsanity.com/paper/2502.08125/) (2025)
- [Learned Static Function Data Structures](https://mlsanity.com/paper/2510.27588/) (2025)

## Abstract (arXiv)

A filter is a widely used data structure for storing an approximation of a given set S of elements from some universe U (a countable set).It represents a superset S'supseteq S that is ''close to S'' in the sense that for xnot∈ S, the probability that x∈ S' is bounded by some varepsilon > 0. The advantage of using a Bloom filter, when some false positives are acceptable, is that the space usage becomes smaller than what is required to store S exactly. Though filters are well-understood from a worst-case perspective, it is clear that state-of-the-art constructions may not be close to optimal for particular distributions of data and queries. Suppose, for instance, that some elements are in S with probability close to 1. Then it would make sense to always include them in S', saving space by not having to represent these elements in the filter. Questions like this have been raised in the context of Weighted Bloom filters (Bruck, Gao and Jiang, ISIT 2006) and Bloom filter implementations that make use of access to learned components (Vaidya, Knorr, Mitzenmacher, and Krask, ICLR 2021). In this paper, we present a lower bound for the expected space that such a filter requires. We also show that the lower bound is asymptotically tight by exhibiting a filter construction that executes queries and insertions in worst-case constant time, and has a false positive rate at most varepsilon  with high probability over input sets drawn from a product distribution. We also present a Bloom filter alternative, which we call the textitDaisy Bloom filter, that executes operations faster and uses significantly less space than the standard Bloom filter.