4 ms·

There are many alternatives to Bloom filters, but some variants of Bloom filters are still competitive. I'm one of the authors of some benchmarks for filters: h

There are many alternatives to Bloom filters, but some variants of Bloom filters are still competitive. I'm one of the authors of some benchmarks for filters: https://github.com/FastFilter/fastfilter_cpp https://github.com/FastFilter/fastfilter_cpp (this is based on the cuckoo filter benchmark) and https://github.com/FastFilter/fastfilter_java https://github.com/FastFilter/fastfilter_java For static sets (where you construct the filter once and then use it for lookup), blocked Bloom filters are the fastest, for lookup. They do need a bit more space (maybe 10% more than Bloom filters). Also very fast are binary fuse filters (which are new), and xor filters. They also save a lot of space compared to others. Cuckoo filters, ribbon filters, and Bloom filters are a bit slower. It's a trade-off between space and lookup speed really. For dynamic sets (where you can add and remove entries later), the fastest (again for lookup) are "Succinct counting blocked Bloom filter" (no paper yet for this): they are a combination of blocked Bloom filters and counting Bloom filters, so lookup is identical to the blocked Bloom filter. Then cuckoo filters, and counting Bloom filters.

ozankabak 5y ago
Where can I find more information about the "Succinct counting blocked Bloom filter"? Can you point to an implementation or a document? Thanks.
- thomasmg 5y ago
  Sure. So far, there are only two Java implementations. One is using "Rank" and the other is using "Select": https://github.com/FastFilter/fastfilter_java/blob/master/fastfilter/src/main/java/org/fastfilter/bloom/count/SuccinctCountingBlockedBloomRanked.java https://github.com/FastFilter/fastfilter_java/blob/master/fa... https://github.com/FastFilter/fastfilter_java/blob/master/fastfilter/src/main/java/org/fastfilter/bloom/count/SuccinctCountingBlockedBloom.java https://github.com/FastFilter/fastfilter_java/blob/master/fa... It should be relatively easy to port it to other programming languages. Compared to regular counting Bloom filters, there are some advantages (e.g. uses half the space, lookup is much faster, no risk of overflows). It has a disadvantage: add+remove are slower (currently). Cuckoo filters need less space, but otherwise advantages+disadvantages are the same. For more questions, just open an issue on that project (I'm one of the authors).
  - ozankabak 5y ago
    Thank you!
jerf 5y ago
> "Succinct counting blocked Bloom filter" Incidentally, for people who don't know this already, if you want to just generally Google about these data structures and learn about them, the search term is "succinct data structure". There's been a lot of interesting work in this area. And they are not lossy in general; obviously lossy structures are interesting but there's some mind-blowing non-lossy succinct data structures as well.
- gorkish 5y ago
  Thank you for posting the correct incantation for one to speak at the oracle.

ozankabak 5y ago

Where can I find more information about the "Succinct counting blocked Bloom filter"? Can you point to an implementation or a document? Thanks.

thomasmg 5y ago
Sure. So far, there are only two Java implementations. One is using "Rank" and the other is using "Select": https://github.com/FastFilter/fastfilter_java/blob/master/fastfilter/src/main/java/org/fastfilter/bloom/count/SuccinctCountingBlockedBloomRanked.java https://github.com/FastFilter/fastfilter_java/blob/master/fa... https://github.com/FastFilter/fastfilter_java/blob/master/fastfilter/src/main/java/org/fastfilter/bloom/count/SuccinctCountingBlockedBloom.java https://github.com/FastFilter/fastfilter_java/blob/master/fa... It should be relatively easy to port it to other programming languages. Compared to regular counting Bloom filters, there are some advantages (e.g. uses half the space, lookup is much faster, no risk of overflows). It has a disadvantage: add+remove are slower (currently). Cuckoo filters need less space, but otherwise advantages+disadvantages are the same. For more questions, just open an issue on that project (I'm one of the authors).
- ozankabak 5y ago
  Thank you!

jerf 5y ago

> "Succinct counting blocked Bloom filter" Incidentally, for people who don't know this already, if you want to just generally Google about these data structures and learn about them, the search term is "succinct data structure". There's been a lot of interesting work in this area. And they are not lossy in general; obviously lossy structures are interesting but there's some mind-blowing non-lossy succinct data structures as well.

gorkish 5y ago
Thank you for posting the correct incantation for one to speak at the oracle.