xkcd #2934: Bloom Filter
Alt text:
Sometimes, you can tell Bloom filters are the wrong tool for the job, but when they're the right one you can never be sure.
261
Comments13Alt text:
Sometimes, you can tell Bloom filters are the wrong tool for the job, but when they're the right one you can never be sure.
For anyone interested in learning more about bloom filters, this is a technical but extremely accessible and easy to follow introduction to them, including some excellent interactive visualizations: https://samwho.dev/bloom-filters/
This was a great read, thanks for sharing!
https://explainxkcd.com/2934
Is'nt bloom filter a shader that makes the picture look hazy and bright?
That's the bloom shader effect: https://en.wikipedia.org/wiki/Bloom_(shader_effect)
But yeah, some people might refer to that as "bloom filter", although it's not what's meant here.
Thanks
https://en.m.wikipedia.org/wiki/Bloom_filter
A bloom filter is a data structure that is most useful in creating a spell check algorithm
In this example, what would you use to prepopulate the filter?
So you’re just putting a bunch of values in memory that you can access quickly, like similar to a hash set contains(), maybe hoping for O(1) time. But other than that there’s no trick to it?
There's a recent algorithm using somewhat similar ideas for approximate counting of unique objects in a stream with constant memory:
https://www.quantamagazine.org/computer-scientists-invent-an-efficient-new-way-to-count-20240516/
I think I like hash-based probabilistic counting better, but this is interesting
Not to be confused with Bloom shader effect.