Binary fuse filters: Fast and smaller than xor filters (2022)

Related prior work:

Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters - https://news.ycombinator.com/item?id=22742905 - March 2020 (25 comments)

Xor Filters: Faster and Smaller Than Bloom Filters - https://news.ycombinator.com/item?id=21840821 - Dec 2019 (81 comments)

	▲	less_less an hour ago \| parent [-]
		See also the paper Ribbon filter: practically smaller than Bloom and Xor: https://arxiv.org/abs/2103.02515, which is a similar idea though not by the same authors. IIRC, binary fuse filters are faster to construct than ribbon filters, but typically not quite as space-efficient. There are also frayed ribbon filters (by me) which are slower and more complex to construct but more space-efficient. There's no paper for those, just a Rust implementation. Ribbon filters are deployed in Mozilla's Clubcard for distributing compressed certificate revocation lists: https://github.com/mozilla/clubcard and https://jmschanck.info/papers/20250327-clubcard.pdf. CRLs are an almost ideal application of this sort of compressed set tech, since the aggregator runs batch jobs and needs to distribute the set to very many clients. It's not perfectly ideal because CRLs require frequent updates and none of these methods support delta updates. There is a straightforward but inelegant workaround, which is to send a compressed set that represents the delta, and query both on the client.

▲

pastage 4 hours ago | parent | prev | next [-]

I recommend the zig library [1], it was a joy to use. Bloom filters was one of the first interesting algorithms I did in class back in university, we upgraded hardware during the lab making the use of bloom filters unnecessary in a lab ment to interactively show its usefulness. I have had this repeated since then, these filters are magic until hardware catches up, having smaller filter is lovely.

[1] https://github.com/hexops/fastfilter

▲

djmips 9 hours ago | parent | prev | next [-]

This feels like a better xor filter implementation.

	▲	orlp 4 hours ago \| parent [-]
		Same author.

▲

vgb2k18 8 hours ago | parent | prev [-]

Fast, but not faster than XOR filters. I was wondering if the title was a typo, but the article clarifies they sacrificed some speed for the smaller size.

	▲	nine_k 6 hours ago \| parent \| next [-]
		One construction is smaller and faster to build than xor filters, and another is even more compact, though slower: > we build probabilistic filters -- called binary fuse filters -- that are within 13% of the storage lower bound -- without sacrificing query speed. As an additional benefit, the construction of the new binary fuse filters can be more than twice as fast as the construction of xor filters. By slightly sacrificing query speed, we further reduce storage to within 8% of the lower bound.
	▲	vlovich123 5 hours ago \| parent \| prev [-]
		I think you misread: > that are within 13% of the storage lower bound -- without sacrificing query speed. As an additional benefit, the construction of the new binary fuse filters can be more than twice as fast as the construction of xor filters. By slightly sacrificing query speed, we further reduce storage to within 8% of the lower bound. They are faster to construct (2x) and smaller (within 13% of theoretical limit) while maintaining the same query performance.