The opposite of a bloom filter
somethingsimilar.com
The opposite of a bloom filter
1–10 of 27 posts
Re: The opposite of a bloom filter
#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).
Re: The opposite of a bloom filter
#3"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).
I 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.
Re: The opposite of a bloom filter
#4"It's a cache." The use case is deduplication in an event-stream environment. This calls for exact matching without hash collisions.
Re: The opposite of a bloom filter
#5I would argue that the opposite of a bloom filter doesn't really exist, at least not in a satisfying way. A bloom filter's size is dependent only on the desired false positive rate, whereas its opposite must be dependent on the size of the data. (And don't be fooled by data that can be represented by a primary key, that's not as general as a bloom filter.) I tried, with limited success, to explain my point of view in this answer on StackExchange: https://cstheory.stackexchange.com/questions/6596/a-probabil...
Re: The opposite of a bloom filter
#6"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).
He is saying "contains implies report". You are saying "not-report implies not-contain".
These are logically equivalent.
Re: The opposite of a bloom filter
#7"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).
He is saying "contains implies report". You are saying "not-report implies not-contain". These are logically equivalent.
[deleted]
Re: The opposite of a bloom filter
#8"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").
Re: The opposite of a bloom filter
#9TLDR: a cache with LRU eviction, but only storing the keys, not the values.
Re: The opposite of a bloom filter
#10"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").
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.