hesela.devDaisy Bloom filter
A Daisy Bloom filter varies each key's hash-probe count using input and query distributions to reduce space under a query-weighted error bound.
Mechanism: Different keys can use different numbers of bit probes, including zero probes that always answer positive. Insertions and queries use the same per-key rule, preserving positive answers for inserted keys. [1]
Error denominator: Definition 1 weights absent-key false positives by their probability among all queries. It does not divide by the probability of querying an absent key. Consequently, its bound is neither a per-key error bound nor necessarily the same percentage among negative queries. [1]
Model: The input set comes from n independent draws with replacement from P; queries follow Q. Theorem 4 assumes sum(p_x*q_x) <= epsilon/n and holds with high probability over the sampled sets. It bounds Daisy operations by ceil(log2(1/epsilon)); the separate constant-time construction is not the Daisy bit-array design. [1]
Model implication: The overlap condition also gives E[Pr(query is present)] <= n*sum(p_x*q_x) <= epsilon, by a union bound over sampled inputs. Hit-heavy synthetic examples illustrate denominator arithmetic, not typical inputs from this low-overlap model.
Accounting: The analysis assumes constant-time access to distribution probabilities and excludes the oracle's storage. Practical comparisons must include that information and its lookup cost. [1]
Relations
- related
- Bloom filter, Learned Bloom filter
Citations
- Bercea, Houen and Pagh. Daisy Bloom Filters. SWAT 2024. DOI: 10.4230/LIPIcs.SWAT.2024.9. Definition 1, sections 1.1 and 5.
- Hesela: Daisy filters and the error denominator
Sources & caveats
- Primary-source synthesis of the published SWAT 2024 paper, not an implementation benchmark or a claim of production deployment.
- The linked worked example is synthetic denominator arithmetic, not execution of the Daisy construction. [2]