The opposite of a bloom filter

Post by kata » Sat, Oct 07, 2017, 9:14 PM UTC

magicalhippo wrote: post #10

ScottBurson wrote: post #8

Earlier quoted context omitted.

It's correct; you've misread it — in fact, you're agreeing with it. What it's saying is, if the item is in the set, the Bloom filter is guaranteed to report that it is in the set. What you're saying is, if the filter says the item is not in the set, then it is guaranteed not to be in the set. Those two statements are equivalent (being contrapositives: "A implies B" is equivalent to "not B implies not A").

The article states a Bloom filter is "guaranteed to report correctly if it contains the item", however a Bloom filter cannot do this. The bits set by the various hash functions could very well be set due to some other key. What the Bloom filter _can_ say, is that if none of the bits are set, then clearly the key was never inserted.

Post by chewbacha » Sat, Oct 07, 2017, 9:36 PM UTC

DenisM wrote: post #9

TLDR: a cache with LRU eviction, but only storing the keys, not the values.

Post by magicalhippo » Sat, Oct 07, 2017, 10:10 PM UTC

kata wrote: post #11

magicalhippo wrote: post #10

Earlier quoted context omitted.

The article states a Bloom filter is "guaranteed to report correctly if it contains the item", however a Bloom filter cannot do this. The bits set by the various hash functions could very well be set due to some other key. What the Bloom filter _can_ say, is that if none of the bits are set, then clearly the key was never inserted.

I think it might just be a strangely formed sentence where the part "if it contains the item" is not the subject of the report, but a condition: If it contains the item -> reports that it contains the item (correctly) If it doesn't contain the item -> may report that it contains the item (incorrectly)

Post by hexane360 » Sat, Oct 07, 2017, 10:23 PM UTC

ww520 wrote: post #16

im3w1l wrote: post #6

Earlier quoted context omitted.

He is saying "contains implies report". You are saying "not-report implies not-contain". These are logically equivalent.

They are not. Multiple objects can map to the same hash key due to collision. Just because a hashtable containing the hash key of an object does not mean the object has been seen before. An object's hash key not contained in the hashtable definitely assures that the object has not been seen before.

Post by ww520 » Sat, Oct 07, 2017, 10:29 PM UTC

ScottBurson wrote: post #8

ww520 wrote: post #2

"A Bloom filter is a data structure that may report it contains an item that it does not (a false positive), but is guaranteed to report correctly if it contains the item (“no false negatives”)." I'm afraid that is not how it works. A Bloom filter can tell whether an item may be in the set (false positive) but can definitely tell an item is NOT in the set (no false negative).

It's correct; you've misread it — in fact, you're agreeing with it. What it's saying is, if the item is in the set, the Bloom filter is guaranteed to report that it is in the set. What you're saying is, if the filter says the item is not in the set, then it is guaranteed not to be in the set. Those two statements are equivalent (being contrapositives: "A implies B" is equivalent to "not B implies not A").