News for hackers. Stuff that matters.
Re:Binary Fuse Filters: Fast and Smaller Than XOR Filters by Sesse__ on Thursday January 22, 2026 @09:13AM (#46719484)
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!

Re:Binary Fuse Filters: Fast and Smaller Than XOR Filters by withoutboats3 on Thursday January 22, 2026 @10:28AM (#46720514)
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.
Re:Binary Fuse Filters: Fast and Smaller Than XOR Filters by thomasmg on Thursday January 22, 2026 @02:28PM (#46724009)
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/fa... [2] https://github.com/thomasmueller/tinyStats

Re:Binary Fuse Filters: Fast and Smaller Than XOR Filters by Sesse__ on Friday January 23, 2026 @11:02AM (#46734072)
FWIW, I found 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.)
Re:Binary Fuse Filters: Fast and Smaller Than XOR Filters by thomasmg on Friday January 23, 2026 @11:12AM (#46734206)
Yes, non-blocked is also possible. This would need a bit less space, and would be a bit slower. The counts > 1 (per bit that is set) are stored spearately, yes.
Re:Binary Fuse Filters: Fast and Smaller Than XOR Filters by Sesse__ on Friday January 23, 2026 @01:29PM (#46735910)
> This would need a bit less space, and would be a bit slower.

I guess that is because the count storage update is really slow, right, so it's better to have one than two (or whatever number of set bits) operations? At least the linked code seems to process it one by one bit when updating, and without some sort of “rank of n-th set bit” operation (which would accelerate the “select” version fairly well), I'm not sure it could be made much faster than that either.

Edit: I see https://github.com/FastFilter/fastfilter_java/blob/master/fa... tries to make that operation in O(1), but to be honest, with this many operations, the cure almost looks worse than the disease. :-) Haven't benchmarked, though.

Re:Binary Fuse Filters: Fast and Smaller Than XOR Filters by thomasmg on Sunday January 25, 2026 @01:32AM (#46751364)
Yes the count storage update is a bit slow. It could be implemented as a background thread, so that it is not blocking. It depends on the use case wheter this is a problem. The 'blocked' variant might be faster to optimize I assume, if this is needed.
Re:Binary Fuse Filters: Fast and Smaller Than XOR Filters by Sesse__ on Sunday January 25, 2026 @03:56AM (#46752107)
> It could be implemented as a background thread, so that it is not blocking.

How would you realistically do this without creating more overhead in the thread communication than what you're saving? I've never heard of offloading a 30–40 cycle operation to a thread before. Typically sending an atomic across CPUs is what, 200 cycles? (That's assuming you have the thread just sitting there in some kind of pool; firing up a new one is much, much more expensive. It also assumes you never need to hear back from it, so wouldn't work well for a decrease where you need to know the count.)

Re:Binary Fuse Filters: Fast and Smaller Than XOR Filters by thomasmg on Sunday January 25, 2026 @01:30PM (#46756699)
Right, it would be wasteful if it's done for each entry separately. But that is not needed. (I should probably write an article about this and a better implementation).

The "succinct counting (blocked) Bloom filters" have two components: the regular Bloom filter for querying, and the count storage. The count storage is not "strictly" needed for querying: you will never get a false _negative_ is increments / decrements in the count storage are deferred. So updating the count storage can be done asynchronously. Both increments and decrements, if you want. So these can be buffered, eg 100 increments / decrements at a time. Sure, the false-positive rate is slightly higher than needed if the decrements are deferred, but with a large filter this effect is small.

So that means, you can buffer increments / decrements in the count storage. You still want to do the "or" operations in the the Bloom filter part synchronously, so that you don't get false negatives. And then, it is no longer just 30-40 cycles, but 3000-4000 cycles, or 30'000-40'000 cycles, or so. I understand this would not be trivial to implement, but also not very complex. I never really had a real-world use case so far, so I didn't work on a full implementation yet.

Re:Binary Fuse Filters: Fast and Smaller Than XOR Filters by Sesse__ on Sunday January 25, 2026 @03:54PM (#46758096)
Sure, you can batch. But that means your decrements must be _entirely_ buffered, right? Because you cannot remove anything from the main filter until you know its count is zero, and you don't know its count until you've processed all increments. And you need to do that under a lock, or you'll have a race where you could have a false negative in the main filter for a short while.
Re:Binary Fuse Filters: Fast and Smaller Than XOR Filters by thomasmg on Sunday January 25, 2026 @06:55PM (#46759988)
Yes exactly!
Re:Binary Fuse Filters: Fast and Smaller Than XOR Filters by orlp on Friday January 23, 2026 @10:31AM (#46733678)
Bloom filters also become full.

As it fills up the false probability rate goes up. Once the false probability rate reaches the threshold of unacceptability, the bloom filter is full, and you can no longer insert into it.

That most interfaces still let you do something that looks like an insert is an interface failure, not a bloom filter feature.

If you find this controversial and want to reply "I don't have a threshold of unacceptability", I'll counter that a false probability rate of 100% will be reached eventually. And if you still find that acceptable, you can trivially modify any probabilistic filter to "never become full" by replacing the "is full" error condition with setting a flag that all future queries should return a false positive.

Re:Binary Fuse Filters: Fast and Smaller Than XOR Filters by fmajid on Friday January 23, 2026 @04:55PM (#46738472)
Counting Quotient Filters (CQF) and Mixed-Counters Quotient Filters (MQF) are more efficient than Bloom Filters, and can count, making them highly suited for applications like rate-limiting at scale.

https://link.springer.com/content/pdf/10.1186/s12859-021-039...