somitomi wrote: ↑Sat May 18, 2024 8:36 pm
ratammer wrote: ↑Sat May 18, 2024 6:52 am
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?
