broom-filter · research · also Broom filters

Broom filter

A broom filter is an adaptive approximate-membership structure that refines fingerprints using remote collision information while retaining compact local state.

Correction: an exact dictionary check triggers a reverse lookup and fingerprint extension. The guarantee assumes suitable hashing and valid set updates. [1]

Deletion: correction history survives deletion and reinsertion until rehashing; the design retains quotient and adaptivity bits but drops the remainder. Local-space optimality excludes remote state and is not a measured latency claim. [1]

Relations

related

Bloom filter, Adaptive quotient filter, Adversarial-resilient filter

Citations

1. Bender et al. Bloom Filters, Adaptivity, and the Dictionary Problem. FOCS 2018. DOI: 10.1109/FOCS.2018.00026. arXiv v3, sections 2-4. (accessed 2026-11-12)

Further reading

2. Hesela: fresh challenges, repeated queries and correction history (accessed 2026-11-12)

JSON: /data/terms/broom-filter.json