4 ms·
To clarify why this is the case. It is because bloom filters effectively group everything in set X that you want to check for into a much smaller "approximated
by ImaCake 6y ago
To clarify why this is the case. It is because bloom filters effectively group everything in set X that you want to check for into a much smaller "approximated set" (the bit-vector). You can then check elements of set Y against the approximated set as a much faster test of whether they are in set X. The important detail here is that the approximated set will be positive for anything that matches an item in set X plus some additional items that are not in set X.
- eis 6y agoRight. Another way to think about bloom filters is a data structure that remembers a list of hashes. It will tell you "oh I saw this hash before". What it will NOT tell you is "oh I saw this element before". If "Foo" and "Bar" hash to "XX" and you've shown "Foo" to the filter, it will think it saw "Bar" because what you are really asking is if it saw something that hashes to "XX". That's the false positive. On the flip side if "Baz" hashes to "XY" then the filter would tell you with certainty that it never saw "Baz" because it never saw anything hashing to "XY" and so "Baz" could not have been seen either.
- ImaCake 6y agoI like your explanation a little better than mine because it is more true to the actual behaviour of the bloom filter. Mine maybe simplifies more than is needed for a clear explanation.