5 ms·
I'm familiar with both cuckoo hashing and Bloom filters but had not until now seen a demonstration of cuckoo filters; they look very useful. But there is one st
by bograt 9y ago
I'm familiar with both cuckoo hashing and Bloom filters but had not until now seen a demonstration of cuckoo filters; they look very useful. But there is one stated fact that I'm finding hard to believe:
> Cuckoo filters improve on Bloom filters by supporting deletion
The page implies that this is achieved by removing the fingerprint from the hash table, but presumably one cannot guarantee that another key doesn't share the same fingerprint. This would result in a false negative for that key and violate an essential characteristic of the data structure.
Perhaps there's a nuance of the implementation I've missed.
- PokemonNoGo 9y agoI 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 https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
- bograt 9y agoHaving 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.
- hinkley 9y agoHashing 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.
- bdupras 9y agoA few types of filters support deletion (e.g. counting bloom filters and cuckoo filters). To my knowledge all of them require prior knowledge that an entry was successfully inserted. That is, if you guess at deleting an entry and are successful, then you'll ruin the filter by creating a false-negative case. As for collisions, only a limited number of colliding entries can be inserted into a cuckoo - after which a subsequent insertion will knowingly fail. So say Alice and Bob hash out to the same values, and you've inserted 2 Alices and 1 Bob. When you delete one Alice, it doesn't matter which entry is removed - two entries still remain that hash to Alice and Bob. Perhaps the nuance you mention is that the alternate bucket index for an entry is calculated only from the fingerprint, not from the entry data. This has the effect that even when multiple entries share fingerprints, any one can be removed. (Again, _only_ if the system requesting the delete positively knows that the entry was previously successfully inserted.) The other colliding entry will still be found on query and will generate a "maybe" response.
- plopilop 9y agoThe idea is that two elements x and y despite having the same fingerprint, will be stored into two different buckets. So you can have several time the same fingerprint in a Cuckoo filter, which you can't in a Bloom Filter. When you want to remove x, you remove one of the two fingerprints, it does not matter which since they're the same. Next when you query y you will be sure to still have a positive answer. Note that however the deletion won't necessarily make the filter forget about x. It will just clear some place in the structure.