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.
[ Parent
| on HN ]
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.