Title 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.
Well, all I can say is, TIL what Bloom filters are. And not from the comic - I had to go and look them up.
2934: "Bloom Filter"
2934: "Bloom Filter"
Title 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.
Well, all I can say is, TIL what Bloom filters are. And not from the comic - I had to go and look them up.
Re: 2934: "Bloom Filter"
I almost said "same", but having read the first three paragraphs of the Wikipedia article I'm not actually sure I understand the concept
-
chridd
- Scorekeeper-Keeper
- Posts: 159
- Joined: Tue Aug 24, 2021 8:02 pm
- Location: west coast US
- Contact:
Re: 2934: "Bloom Filter"
It's a way of "approximately" representing a set of values. In a simple version, you have some number of bits, and for each element of the set, you set one of the bits to 1 based on a hash of that element. Then if you want to look up an element of that set, you can check the bit corresponding to that element's hash. If it's a 1, then the element might be in the set (or there might just be another element with the same hash), but if it's a 0, then the element is definitely not.
This could be useful, for instance, if the actual full set of values is stored somewhere that's slow to access; you could have the bloom filter on smaller local memory, and so sometimes you can quickly say "no, that's not in the set" without having to access the full set.
A more complicated version sets more than one bit per value (say, 3), and then checks if all of them are 1 when looking up a value. If any of the bits is 0, then the element is definitely not in the set.
Does that make more sense?