4 ms·

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

by 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
    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.
    - Sesse__ 9mo ago
      > 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/fastfilter/src/main/java/org/fastfilter/bloom/count/Select.java#L151 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.
      - thomasmg 9mo ago
        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.
        Sesse__ 9mo ago
        > 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.)
orlp 9mo ago
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.
fmajid 9mo ago
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-03996-x.pdf https://link.springer.com/content/pdf/10.1186/s12859-021-039...

by Sesse__ 9mo ago

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
  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.
  - Sesse__ 9mo ago
    > 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/fastfilter/src/main/java/org/fastfilter/bloom/count/Select.java#L151 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.
    - thomasmg 9mo ago
      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.
      - Sesse__ 9mo ago
        > 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.)

orlp 9mo ago

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.

fmajid 9mo ago

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-03996-x.pdf https://link.springer.com/content/pdf/10.1186/s12859-021-039...