News for hackers. Stuff that matters.
Re:Probabilistic Filters By Example by PokemonNoGo on Wednesday March 28, 2018 @10:50AM (#16698079)
I had the same thoughts and checked the paper[0]. They address it under 3.3 Delete

>Deletion does not have to clean the entry after deleting an item. It also avoids the “false deletion”....

[0]https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf

Re:Probabilistic Filters By Example by bograt on Wednesday March 28, 2018 @11:35AM (#16698509)
Having quickly read the paper, the deletion guarantees seem slightly weak.

An item's position in the table is derived from two things: a fingerprint (a constant-sized hash) and second hash (ranging over the table). Nothing prevents two or more items from colliding on both hashes and therefore being indistinguishable from each other.

If the number of items in such a collision exceeds twice the fixed bucket size then deletion may result in false negatives.

In most practical applications there will be no useful way to bound the number of collisions. The paper shows results with bucket sizes of 4 and 8, but I don't know what the real-world probabilities of breaching these limits would be.

Re:Probabilistic Filters By Example by hinkley on Wednesday March 28, 2018 @11:52AM (#16698713)
Hashing items that present themselves as equivalent is a very old problem with plenty of literature. It can be a pain in the butt to fix retroactively but it does tend to get fixed when there are big enough performance or correctness concerns in play.