Reproduce “Binary Fuse Filters: Fast and Smaller Than Xor Filters” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Thomas Mueller Graf, Daniel Lemire
Binary Fuse filters, developed by Thomas Mueller Graf and Daniel Lemire, introduce an approximate set membership data structure that uses memory within 8-13% of the theoretical lower bound and constructs more than twice as fast as Xor filters, while maintaining high query performance. The work establishes a new benchmark for static probabilistic filters by optimizing space, construction speed, and query efficiency.
Key insights
- Localized hashing, by constraining hash outputs to consecutive memory segments, substantially improves cache hit rates and overall performance for both filter construction and query operations.
- The combination of partial sorting input keys and the iterative peeling algorithm results in a highly optimized construction process that is significantly faster than previous fingerprint-based filters.
- Through empirical tuning, the filter achieves a high success probability for construction while maintaining an array size very close to the theoretical minimum, demonstrating a strong balance between practicality and efficiency.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.