Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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

How is this different from a bloom filter?



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.


It has false positives.


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.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: