6 ms·
"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 contain
by ww520 9y ago
"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).
- aespinoza 9y agoI believe it is a typo. The rest of the article does align to that concept. At first glance I do disagree that his/her solution will be as efficient in terms of size of the set and as performant as bloom filters or cuckoo filters. But I would have to benchmark it to be sure.
- im3w1l 9y agoHe is saying "contains implies report". You are saying "not-report implies not-contain". These are logically equivalent.
- deleted 9y ago[deleted]
- ww520 9y agoThey 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.
- hexane360 9y agoThis is called the contrapositive of your statement. It's logically guaranteed. No one is claiming that "if the hash matches the object must be there". They're saying "if the object is there, the hash will match". This is logically equivalent to saying "if the hash does not match, the object is not there".
- finnh 9y agoGP is right; you need to be careful about how you read it. “contains implies report” is different than “report implies contains”. You are (correctly) arguing the against latter statement, which GP does not make.
- ScottBurson 9y agoIt'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").
- magicalhippo 9y agoThe 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.
- kata 9y agoI 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)
- kakarot 9y agoNothing wrong with being pedantic when dealing with definitions.
- egocentric 9y agoSince we're on the topic of being pedantic, "well, you know, that's just, like... your opinion, man". I'd argue that there's nothing excessive about arguing if A may, in fact, be the opposite of A :)
- kakarot 9y ago
- Retric 9y agoI can see what's confusing you, but it's correct as stated. Item is not a reference to the physical data structure in memory. If you treat it as a black box where you put items in and then ask it if it has seen the 'item' then the wording is more clear.