4 ms·

> It appears that this filter can become "full", which is very different from a bloom filter. How is this different from a bloom filter?

• sharth 12y ago
  A bloom filter's insert function is basically: def insert(x): for hash in hashes: bloom_filter[hash(x)] = true The downside is that your false positive rate will increase as you insert elements. But, on the other hand, you get the guarantee of no false negatives. This cuckoo filter has no false negatives or false positives, but their Insert() function clearly can hit a case where it returns Failure.
  • justicezyx 12y ago
    It does have false positive. Remember it stores a fingerprint of the key instead of the real key.
  • placeybordeaux 12y ago
    It has false positives.
• fidotron 12y ago
  Bloom filters effectively represent the infinite set when it's all ones. You can always add more, and everything will return as probably in there already.