2934: "Bloom Filter"

[ratammer]

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.

[somitomi]

Well, all I can say is, TIL what Bloom filters are. And not from the comic - I had to go and look them up.

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]

Well, all I can say is, TIL what Bloom filters are. And not from the comic - I had to go and look them up.

I almost said "same", but having read the first three paragraphs of the Wikipedia article I'm not actually sure I understand the concept

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?