Blocked Bloom Filters with Choices
Johanna Elena Schmitz, Jens Zentgraf 1, Sven Rahmann · 2025
Read Blocked Bloom Filters with Choices by Johanna Elena Schmitz, Jens Zentgraf 1, Sven Rahmann (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-18977.txt.
Description
Johanna Elena Schmitz, Jens Zentgraf, and Sven Rahmann add a twist to Bloom filters, the compact data structures that answer membership questions with no false negatives and a few allowed false positives. Blocked Bloom filters divide memory into blocks for speed, but pay for it in space. The authors let each key choose between two or more alternative blocks for its fingerprints.
That single freedom keeps the blocked design's virtues, fast online insertion and graceful behavior when slightly overloaded, while removing its main cost. At the same memory the new filter produces fewer false positives than a blocked filter; at the same error rate it uses less space. The paper covers the method, an engineered implementation, a detailed performance study, and uses in bioinformatics, where such filters index huge sequence collections. Code and workflows are posted publicly.
Catalog record
| CREATOR | Johanna Elena Schmitz, Jens Zentgraf 1, Sven Rahmann |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 58 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-18977