News for hackers. Stuff that matters.
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.