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.
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.
13 Comments
hydroptic@sopuli.xyz · 58 pts · 2y
LPThinker@lemmy.world · 31 pts · 2y
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/
gbuttersnaps@programming.dev · 6 pts · 2y
This was a great read, thanks for sharing!
randomaccount43543@lemmy.world · 22 pts · 2y
https://explainxkcd.com/2934
Xeroxchasechase@lemmy.world · 16 pts · 2y
Is'nt bloom filter a shader that makes the picture look hazy and bright?
Ephera@lemmy.ml · 30 pts · 2y
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.
Xeroxchasechase@lemmy.world · 5 pts · 2y
Thanks
Die4Ever@programming.dev · 15 pts · 2y
https://en.m.wikipedia.org/wiki/Bloom_filter
rockSlayer@lemmy.world · 6 pts · 2y
A bloom filter is a data structure that is most useful in creating a spell check algorithm
hydroptic@sopuli.xyz · 13 pts · 2y
jaybone@lemmy.world · 1 pts · 2y
In this example, what would you use to prepopulate the filter?
hydroptic@sopuli.xyz · 1 pts · 2y
jaybone@lemmy.world · 2 pts · 2y
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?
hydroptic@sopuli.xyz · 2 pts · 2y
Audalin@lemmy.world · 10 pts · 2y
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/
Mubelotix@jlai.lu · 2 pts · 2y
I think I like hash-based probabilistic counting better, but this is interesting
Venat0r@lemmy.world · 1 pts · 2y
Not to be confused with Bloom shader effect.