Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The opposite of a bloom filter

somethingsimilar.com

Post reply on HN
Print view View original

21–27 of 27 posts

Re: The opposite of a bloom filter

#21

Post by Retric »

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

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

Re: The opposite of a bloom filter

#22

Post by ScottBurson »

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.

> The article states a Bloom filter is "guaranteed to report correctly if it contains the item", however a Bloom filter cannot do this.

I think what's going on here is that you're reading "if" as meaning "whether". In fairness, this is common English usage: "I'll tell you tomorrow if I'm going" usually means "I'll tell you tomorrow whether I'm going".

That's not what the OP means. The correct reading is perhaps clarified with a comma:

> A Bloom filter is guaranteed to report correctly, if it contains the item.

or perhaps better

> If it contains the item, a Bloom filter is guaranteed to report correctly.

Re: The opposite of a bloom filter

#23

Post by kakarot »

egocentric wrote: post #20
kakarot wrote: post #12

Earlier quoted context omitted.

Nothing wrong with being pedantic when dealing with definitions.

Since 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 :)

Certainly not, I'm all for some arguing on the internet.

Re: The opposite of a bloom filter

#24

Post by beefman »

pents90 wrote: post #5

I 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…

Bloom filters scale logarithmically with false positive rate and linearly with the number of items stored.

The article doesn't mention the false negative rate. Unlike a Bloom filter, it'll depend on order when the input includes repeated elements. But in general, required memory will increase quadratically in the number of items stored at a constant false negative rate (because of the "birthday paradox").

So it isn't the opposite of a Bloom filter. But what is?

Re: The opposite of a bloom filter

#25

Post by frankmcsherry »

pents90 wrote: post #5

I 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 probably runs afoul of your "at least not in a satisfying way" constraint, but:

It is pretty easy (an exercise) to implement the "opposite of a Bloom filter" if you start from a summary of the complete set of events and support deletion, rather than starting from the empty set and supporting addition.

What makes everything seem hard is the (often unstated) requirement that you start from an empty set and support addition, which is roughly as hard as implementing a Bloom filter that starts from the complete set and supports deletion. Neither of the links make this requirement explicit (though, it is implicit in their "motivation" sections).

Re: The opposite of a bloom filter

#26

Post by magicalhippo »

ScottBurson wrote: post #22
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.

> The article states a Bloom filter is "guaranteed to report correctly if it contains the item", however a Bloom filter cannot do this. I think what's going on here is that you're reading "if" as meaning "whether". In fairness, this is common English usage: "I'll tell you tomorrow if I'm going" usually means "I'll tell you tomorrow whether I'm going". That's not what the OP means. The correct reading is perhaps clari…

Ah yes, that would be it.

IMO it is better to present the Bloom filter by asking/stating what one can be certain of given each return value of the Bloom filter.

Post reply on HN