3 ms·

Bloom filter was probably chosen not because of its false negative rate but because it was good enough whatever its false negative rate is.

jchw 6y ago
I'd guess bloom filters were often chosen because it was one of the only available options. I believe cuckoo filters were invented in 2014.
eis 6y ago
Bloom filters have no false negatives, they have only false positives. If it were the other way round, they would be of no practical use as you'd have to query the original datastructure in any case: - If the bloom filter said "True", then you go ahead and fetch the data from the original structure - If the bloom filter said "False" but that might be a false negative then you'd have to anyway query the original structure to be sure With 0% false negatives but a relatively small rate of false positives instead, you don't have to query the original source if the filter gave a "False". Btw. Bloom filters were one of the first probabilistic data structures with real practical uses and still to this day are widely used. They are still not out-classed in every way by newer algorithms like Cuckoo filters.
- 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 ago
    Right. 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 ago
      I 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.
- emn13 6y ago
  Of course that's purely a matter of perspective. If you regard a bloom filter as an approximation of inclusion in a set, it's a false positive, which is how we usually look at it. But if you look at it as a an approximation of safe urls e.g. in a browser it's a false negative (and there are no false positives). The data structure doesn't care; it's just bits: if the overall set is finite, it's even quite hard to tell which makes most sense, but in the more usual practically unbounded case, sure, finite subset inclusion approximation seems a less braintwisting interpretation.
  - eis 6y ago
    It's an interesting thought but I'd argue the following. First, the definition of Bloom filters is a probabilistic data structure to test the presence of an element in a set no matter the program logic around it. But secondly, given your example of safe browsing, you can flip positive and negative meanings around freely by how you define the question. Is it "is this a bad domain?" or "is this a good domain?" which you both can convert to "is this domain in the set?" and "is this domain NOT in the set?". And that's a general problem with "positives" and "negatives", they depend purely on the question and the question can have a boolean negator in it. But that's a logical layer above the data structure. As you said, the data structure does not care, it is just bits and therefore the question is "is the element in the set?". Same as one could ask "Is it day?" or "Is it night?" which both query the same underlying data about the time and location but would have opposite meanings for positive and negative results. And so, to give the two terms a better meaning we have a definition of the data structure and the operations on it which defines the meanings of negatives and positives. I think some part of the reason for confusion with false negatives and positives results from the conotations of "positive" (good) and "negative" (bad).

jchw 6y ago

I'd guess bloom filters were often chosen because it was one of the only available options. I believe cuckoo filters were invented in 2014.

eis 6y ago

Bloom filters have no false negatives, they have only false positives. If it were the other way round, they would be of no practical use as you'd have to query the original datastructure in any case: - If the bloom filter said "True", then you go ahead and fetch the data from the original structure - If the bloom filter said "False" but that might be a false negative then you'd have to anyway query the original structure to be sure With 0% false negatives but a relatively small rate of false positives instead, you don't have to query the original source if the filter gave a "False". Btw. Bloom filters were one of the first probabilistic data structures with real practical uses and still to this day are widely used. They are still not out-classed in every way by newer algorithms like Cuckoo filters.

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 ago
  Right. 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 ago
    I 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.
emn13 6y ago
Of course that's purely a matter of perspective. If you regard a bloom filter as an approximation of inclusion in a set, it's a false positive, which is how we usually look at it. But if you look at it as a an approximation of safe urls e.g. in a browser it's a false negative (and there are no false positives). The data structure doesn't care; it's just bits: if the overall set is finite, it's even quite hard to tell which makes most sense, but in the more usual practically unbounded case, sure, finite subset inclusion approximation seems a less braintwisting interpretation.
- eis 6y ago
  It's an interesting thought but I'd argue the following. First, the definition of Bloom filters is a probabilistic data structure to test the presence of an element in a set no matter the program logic around it. But secondly, given your example of safe browsing, you can flip positive and negative meanings around freely by how you define the question. Is it "is this a bad domain?" or "is this a good domain?" which you both can convert to "is this domain in the set?" and "is this domain NOT in the set?". And that's a general problem with "positives" and "negatives", they depend purely on the question and the question can have a boolean negator in it. But that's a logical layer above the data structure. As you said, the data structure does not care, it is just bits and therefore the question is "is the element in the set?". Same as one could ask "Is it day?" or "Is it night?" which both query the same underlying data about the time and location but would have opposite meanings for positive and negative results. And so, to give the two terms a better meaning we have a definition of the data structure and the operations on it which defines the meanings of negatives and positives. I think some part of the reason for confusion with false negatives and positives results from the conotations of "positive" (good) and "negative" (bad).