3 ms·

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

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.

nutheracc 10y ago
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."
- dangoldin 10y ago
  Yea - the comment above cleared it up. Apparently the Cuckoo filter should have rejected the latter inserts.
  - bdupras 10y ago
    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.
grogers 10y ago
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.
- dangoldin 10y ago
  Ah got it - thanks for the explanation. That makes a lot of sense now.
lorenzhs 10y ago
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 https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf

nutheracc 10y ago

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

dangoldin 10y ago
Yea - the comment above cleared it up. Apparently the Cuckoo filter should have rejected the latter inserts.
- bdupras 10y ago
  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.

grogers 10y ago

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.

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

lorenzhs 10y ago

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 https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf