5 ms·

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

138 points by redbell 9mo ago

djmips 9mo ago
This feels like a better xor filter implementation.
- orlp 9mo ago
  Same author.
- pwagland 9mo ago
  This is mentioned on the first page of the paper: > Building on theoretical work by Dietzfelbinger and Walzer [8], we propose a novel practical approach, the binary fuse filters. They are conceptually similar to xor filters, and they rely on nearly the same simple code.
dang 9mo ago
Related prior work: Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters - https://news.ycombinator.com/item?id=22742905 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 https://news.ycombinator.com/item?id=21840821 - Dec 2019 (81 comments)
- less_less 9mo ago
  See also the paper Ribbon filter: practically smaller than Bloom and Xor: https://arxiv.org/abs/2103.02515 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 https://github.com/mozilla/clubcard and https://jmschanck.info/papers/20250327-clubcard.pdf 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.
vgb2k18 9mo ago
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 9mo ago
  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 9mo ago
  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.
pastage 9mo ago
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 https://github.com/hexops/fastfilter
Sesse__ 9mo ago
As far as I can see, these classes of filters (including xor filters) have some practical issues for many applications: They can become full (refuse new entries altogether), and they need to know all the elements up-front (no incremental inserts). Is there anything more modern than Bloom filters that don't have these restrictions? I'm especially fond of tiny filters; a well-placed 32- or 64-bit Bloom filter can be surprisingly effective in the right context!
- withoutboats3 9mo ago
  Cuckoo filters outperform bloom filters and allow dynamic insertion and deletion (unlike bloom filters, which only allow insertion). The trade off is that insertion can fail if the table is too full and then would need to expand or store those entries some other way to avoid a false negative.
- thomasmg 9mo ago
  There are many variants. It really depends on what features you need. Cuckoo filters were mentioned. If you want to add and remove entries and the regular counting Bloom filter are not good enough, I would look at the "succinct counting blocked Bloom filter" [1]: they only need about twice the space than regular Bloom filters. Sure, cuckoo filters need less memory, but they can fail basically any time, while these can not. Tiny filters: Some time ago I worked on tiny statistics [2]. This includes some 64-bit HyperLogLog implementations; some use linear counting, which is basically a 64-bit Bloom filter, until some limit, and only then switch to HyperLogLog. This is great for distinct counts of columns in databases (cardinality estimation). This project also includes 64-bit approximate counts and histograms. [1] https://github.com/FastFilter/fastfilter_java/blob/master/fastfilter/src/main/java/org/fastfilter/bloom/count/SuccinctCountingBloomRanked.java https://github.com/FastFilter/fastfilter_java/blob/master/fa... [2] https://github.com/thomasmueller/tinyStats https://github.com/thomasmueller/tinyStats
  - Sesse__ 9mo ago
    FWIW, I found https://github.com/FastFilter/fastfilter_java/issues/28 https://github.com/FastFilter/fastfilter_java/issues/28 a pretty good explanation of what's going on in the succinct counting blocked Bloom filters. (I'm not sure if the blocking is needed for the normal Bloom filter part, though, i.e., all bits don't necessarily need to fall within the same block, no? But the counts are stored separately for each block.)
thomasmg 9mo ago
I'm one of the authors. Feel free to ask anything.
- kuhdungbingo 9mo ago
  Now would this be useful in high scaling games, specifically: determining if you might be a winner of game with a grid of 10^nx10^n (where n>5). A very large "cow bingo game", where the insertions are made randomly spawned on a grid? Seems one of the other filters would be more appropriate as they support dynamic insertion. Still very neat, nice work!
  - thomasmg 9mo ago
    Yes, you would need a dynamic filter (eg. regular Bloom filter or cuckoo filter) for this, due to the insertions. Static filters are good for eg. leaked password lists, LSM trees (LevelDB, RocksDB), and so on.
avadodin 9mo ago
I'm saddened that there aren't more replies to this. Bloom filters are the coolest thing ever and I wish I could replace them with something better.

138 points by redbell 9mo ago

djmips 9mo ago

This feels like a better xor filter implementation.

orlp 9mo ago
Same author.
pwagland 9mo ago
This is mentioned on the first page of the paper: > Building on theoretical work by Dietzfelbinger and Walzer [8], we propose a novel practical approach, the binary fuse filters. They are conceptually similar to xor filters, and they rely on nearly the same simple code.

dang 9mo ago

Related prior work: Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters - https://news.ycombinator.com/item?id=22742905 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 https://news.ycombinator.com/item?id=21840821 - Dec 2019 (81 comments)

less_less 9mo ago
See also the paper Ribbon filter: practically smaller than Bloom and Xor: https://arxiv.org/abs/2103.02515 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 https://github.com/mozilla/clubcard and https://jmschanck.info/papers/20250327-clubcard.pdf 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.

vgb2k18 9mo ago

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 9mo ago
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 9mo ago
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.

pastage 9mo ago

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 https://github.com/hexops/fastfilter

Sesse__ 9mo ago

As far as I can see, these classes of filters (including xor filters) have some practical issues for many applications: They can become full (refuse new entries altogether), and they need to know all the elements up-front (no incremental inserts). Is there anything more modern than Bloom filters that don't have these restrictions? I'm especially fond of tiny filters; a well-placed 32- or 64-bit Bloom filter can be surprisingly effective in the right context!

withoutboats3 9mo ago
Cuckoo filters outperform bloom filters and allow dynamic insertion and deletion (unlike bloom filters, which only allow insertion). The trade off is that insertion can fail if the table is too full and then would need to expand or store those entries some other way to avoid a false negative.
thomasmg 9mo ago
There are many variants. It really depends on what features you need. Cuckoo filters were mentioned. If you want to add and remove entries and the regular counting Bloom filter are not good enough, I would look at the "succinct counting blocked Bloom filter" [1]: they only need about twice the space than regular Bloom filters. Sure, cuckoo filters need less memory, but they can fail basically any time, while these can not. Tiny filters: Some time ago I worked on tiny statistics [2]. This includes some 64-bit HyperLogLog implementations; some use linear counting, which is basically a 64-bit Bloom filter, until some limit, and only then switch to HyperLogLog. This is great for distinct counts of columns in databases (cardinality estimation). This project also includes 64-bit approximate counts and histograms. [1] https://github.com/FastFilter/fastfilter_java/blob/master/fastfilter/src/main/java/org/fastfilter/bloom/count/SuccinctCountingBloomRanked.java https://github.com/FastFilter/fastfilter_java/blob/master/fa... [2] https://github.com/thomasmueller/tinyStats https://github.com/thomasmueller/tinyStats
- Sesse__ 9mo ago
  FWIW, I found https://github.com/FastFilter/fastfilter_java/issues/28 https://github.com/FastFilter/fastfilter_java/issues/28 a pretty good explanation of what's going on in the succinct counting blocked Bloom filters. (I'm not sure if the blocking is needed for the normal Bloom filter part, though, i.e., all bits don't necessarily need to fall within the same block, no? But the counts are stored separately for each block.)

thomasmg 9mo ago

I'm one of the authors. Feel free to ask anything.

kuhdungbingo 9mo ago
Now would this be useful in high scaling games, specifically: determining if you might be a winner of game with a grid of 10^nx10^n (where n>5). A very large "cow bingo game", where the insertions are made randomly spawned on a grid? Seems one of the other filters would be more appropriate as they support dynamic insertion. Still very neat, nice work!
- thomasmg 9mo ago
  Yes, you would need a dynamic filter (eg. regular Bloom filter or cuckoo filter) for this, due to the insertions. Static filters are good for eg. leaked password lists, LSM trees (LevelDB, RocksDB), and so on.

avadodin 9mo ago

I'm saddened that there aren't more replies to this. Bloom filters are the coolest thing ever and I wish I could replace them with something better.