3 ms·

I don't think that's quite right though. A bloom filter does not keep a list of hashes. If it did it'd grow with every item added to the set, and it doesn't. A

by Doxin 6y ago

I don't think that's quite right though. A bloom filter does not keep a list of hashes. If it did it'd grow with every item added to the set, and it doesn't. A bloom filter adds a new hash by bitwise-or-ing it with the currently stored value. Checking if a hash is present in the bloom filter is as simple as checking that all the 1 bits in the bash are 1 bits in the stored value in the bloom filter. This makes sure there are never any false negatives because bits only ever get turned on, never off. False positives are possible because of either direct hash collisions, or unrelated hashes turning on enough bits for a match.

G4E 6y ago
So it means with a dataset big enough, your bloom filter is virtualy all 1s, and will return true for every values you want to check regardless if it is actually in there ? Is there a threshold you can monitor to avoid this situation ?
- polyrand 6y ago
  Yes, if a dataset keeps growing, the whole bloom filter will eventually become 1s. If you know the (approximate) expected size of your dataset and the probabilities of false positives you can tolerate, you can calculate how big the filter should be and how many hashing functions you have to use. I guess there are other techniques to dynamically grow the filter when you need it.
eis 6y ago
It's indeed not a list of hashes but (as I said) a set of hashes. Usuaully the size of the set is static and determined when creating the bloom filter (how many bits in the bitmap). The hashes are not full blown hashes like a sha1 sum or similar but a bit (or a few) in the bitmap. You only add to the set and never remove. The bitwise or-ing with the stored value is the mentioned hash collision and just an implementation detail. It's still a set of hashes. "unrelated hashes turning on enough bits for a match" is the case of hash collisions or I am misunderstanding that part.

by Doxin 6y ago

G4E 6y ago

So it means with a dataset big enough, your bloom filter is virtualy all 1s, and will return true for every values you want to check regardless if it is actually in there ? Is there a threshold you can monitor to avoid this situation ?

polyrand 6y ago
Yes, if a dataset keeps growing, the whole bloom filter will eventually become 1s. If you know the (approximate) expected size of your dataset and the probabilities of false positives you can tolerate, you can calculate how big the filter should be and how many hashing functions you have to use. I guess there are other techniques to dynamically grow the filter when you need it.

eis 6y ago

It's indeed not a list of hashes but (as I said) a set of hashes. Usuaully the size of the set is static and determined when creating the bloom filter (how many bits in the bitmap). The hashes are not full blown hashes like a sha1 sum or similar but a bit (or a few) in the bitmap. You only add to the set and never remove. The bitwise or-ing with the stored value is the mentioned hash collision and just an implementation detail. It's still a set of hashes. "unrelated hashes turning on enough bits for a match" is the case of hash collisions or I am misunderstanding that part.