search

jonahharris / libcuckoofilter

A C library implementation of a Cuckoo Filter
MIT License
23 stars 9 forks source link

False negatives #5

Open rt121212121 opened 2 years ago

rt121212121 commented 2 years ago

I wrapped this as a Python extension and tested it with a range of inputs. What I observed was that I would get false negatives if I added hundreds of thousands of items and then checked if they were found. It turns out this is because the victim support is not implemented and this seems to corrupt the filter past a certain point (maybe dropped victims).

I implemented the victim support and this fixed the false negatives. However, what I then experienced was that if I tried to iterate through the added items and remove them, I encountered false negatives due to filter corruption. It is possible that this was due to my victim handling in the removal code but who knows at this point.

I suggest you alter the readme to indicate this implementation requires more work before it is not suitable for use. You can find my altered code here.

jonahharris commented 2 years ago

Thanks for this. I'll pull in your changes and add your attribution. Agreed on the comment addition, this was just a PoC library I didn't expect anyone to really use and have had a number of people send me things since.