3 ms·

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

by 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).

by emn13 6y ago

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).