Hacker News Reader

Comment by dangoldin | Hacker News Reader

Neat visualization. One of the nicest things about a Bloom Filter is that you'll never get a false negative (saying something is not inside even if it is). I'm not super familiar with Cuckoo filters but since it allows for removal it's possible to get false negatives.

You can replicate that by entering "cat" 5 times and then removing it 4 times. Cuckoo will indicate it's not in the filter despite it still showing up there a single time. I guess that's the "limited counting" aspect of it. Really cool.

View on HN

Based on the explanation, cuckoo filters need to reject inserts that would break the invariants, which the demo doesn't seem to do.

You are right that deletion from a probabilistic filter is sort of weird, because it is possible to delete something that never existed if it happens to exist as a false positive. If you can guarantee that the false deletion doesn't happen, then it should work as expected. There are variants of bloom filters that can do this as well.

Ah got it - thanks for the explanation. That makes a lot of sense now.

You're somewhat wrong about false negatives in Cuckoo filters. They can only occurr if buckets overflow. You can find the reasoning in the paper (Section 3.3): https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf

I'm not up to arguing about this, but is that not related to the cuckoo filter (this implementation?) seeming to have a limit of four repeats? From the cuckoo description: "When a matching fingerprint is not found, the entry is definitely not in the filter."

Yea - the comment above cleared it up. Apparently the Cuckoo filter should have rejected the latter inserts.

It isn't clear in the demo visualization, but insertions into the Cuckoo filter do get rejected after exhausting a maximum number of kick/relocation attempts. If I find some time I'll make that more apparent.

As for false negatives, this can happen in both Cuckoo and Counting Bloom filters if a value that is never added is removed, and the value would have resulted in a false positive on query. The contract for removal is that you must know that the value is currently in the filter. I'll clarify that in the text.

Reply on news.ycombinator.com