Binary Fuse Filters: Fast and Smaller Than XOR Filters
21 days ago
- #performance optimization
- #probabilistic filters
- #data structures
- Binary fuse filters are introduced as a new type of probabilistic filter, offering faster and more memory-efficient set membership queries compared to existing filters like Bloom, cuckoo, and xor filters.
- Binary fuse filters achieve storage efficiency within 13% of the theoretical lower bound, improving upon xor filters' 23% and Bloom filters' 44%.
- Construction of binary fuse filters can be more than twice as fast as xor filters, with an option to further reduce storage to within 8% of the lower bound by slightly sacrificing query speed.
- Performance comparisons show binary fuse filters outperform a range of alternatives including Bloom filters, blocked Bloom filters, vector quotient filters, cuckoo filters, and ribbon filters.
- The work is inspired by Dietzfelbinger and Walzer, focusing on optimizing both storage efficiency and query speed without compromising on construction speed.