News for hackers. Stuff that matters.
Re:Probabilistic Filters By Example: Cuckoo Filter and Bloom... by dangoldin on Tuesday July 19, 2016 @08:46PM (#12126084)
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.

Re:Probabilistic Filters By Example: Cuckoo Filter and Bloom... by grogers on Wednesday July 20, 2016 @08:05AM (#12128330)
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.

Re:Probabilistic Filters By Example: Cuckoo Filter and Bloom... by dangoldin on Wednesday July 20, 2016 @08:11AM (#12128358)
Ah got it - thanks for the explanation. That makes a lot of sense now.
Re:Probabilistic Filters By Example: Cuckoo Filter and Bloom... by lorenzhs on Wednesday July 20, 2016 @09:22AM (#12128793)
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
Re:Probabilistic Filters By Example: Cuckoo Filter and Bloom... by nutheracc on Wednesday July 20, 2016 @05:56AM (#12127850)
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."
Re:Probabilistic Filters By Example: Cuckoo Filter and Bloom... by dangoldin on Wednesday July 20, 2016 @08:12AM (#12128359)
Yea - the comment above cleared it up. Apparently the Cuckoo filter should have rejected the latter inserts.
Re:Probabilistic Filters By Example: Cuckoo Filter and Bloom... by bdupras on Wednesday July 20, 2016 @08:16PM (#12133607)
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.