Hacker News Reader

Comment by jchw | Hacker News Reader

A bit tangential, but I suspect many people don’t know is there is actually more information-dense data structures for the use case of bloom filters; Cuckoo filters for example can get close to the theoretical lower bound of information required and have some other interesting properties. So you should consider that before reaching for bloom filters, probably!

View on HN

Or you go with Xor filters, which are more efficient than both Cockoo and Bloom filters. [0]

[0] https://arxiv.org/abs/1912.08258 ("Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters")

Thanks, that’s even more interesting. I thought cuckoo filters were near the theoretical limit of information density so it looks like I have some more learning to do.

Cuckoo filters get far less explanation articles on Hacker News than Bloom filters, which pop up on the front page every month!

Bloom filter was probably chosen not because of its false negative rate but because it was good enough whatever its false negative rate is.

I'd guess bloom filters were often chosen because it was one of the only available options. I believe cuckoo filters were invented in 2014.

Bloom filters have no false negatives, they have only false positives. If it were the other way round, they would be of no practical use as you'd have to query the original datastructure in any case:

- If the bloom filter said "True", then you go ahead and fetch the data from the original structure - If the bloom filter said "False" but that might be a false negative then you'd have to anyway query the original structure to be sure

With 0% false negatives but a relatively small rate of false positives instead, you don't have to query the original source if the filter gave a "False".

Btw. Bloom filters were one of the first probabilistic data structures with real practical uses and still to this day are widely used. They are still not out-classed in every way by newer algorithms like Cuckoo filters.

To clarify why this is the case. It is because bloom filters effectively group everything in set X that you want to check for into a much smaller "approximated set" (the bit-vector). You can then check elements of set Y against the approximated set as a much faster test of whether they are in set X. The important detail here is that the approximated set will be positive for anything that matches an item in set X plus some additional items that are not in set X.

Right. Another way to think about bloom filters is a data structure that remembers a list of hashes. It will tell you "oh I saw this hash before". What it will NOT tell you is "oh I saw this element before".

If "Foo" and "Bar" hash to "XX" and you've shown "Foo" to the filter, it will think it saw "Bar" because what you are really asking is if it saw something that hashes to "XX".

That's the false positive.

On the flip side if "Baz" hashes to "XY" then the filter would tell you with certainty that it never saw "Baz" because it never saw anything hashing to "XY" and so "Baz" could not have been seen either.

I like your explanation a little better than mine because it is more true to the actual behaviour of the bloom filter. Mine maybe simplifies more than is needed for a clear explanation.

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.

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

Reply on news.ycombinator.com