3 ms·
Bloom filters are great, but unfortunately don't support deletions of items as a particular key might be being used by more than element in the filter and you d
by dmlittle 10y ago
Bloom filters are great, but unfortunately don't support deletions of items as a particular key might be being used by more than element in the filter and you don't know if it's same to delete. A few weeks ago, someone posted about Cuckoo Filters [1] which are like Bloom Filters but allow for key deletion.
[1]: https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
- politician 10y agoOrganizing Bloom filters into (e.g. daily) shards allows for deletion without much trouble.
- dlhavema 10y agoIsn't there a variant that uses a counter instead of a bit. If counter > 0 the flag is set?
- dmlittle 10y agoYes, but by using a counter you increase the size of the filter and you introduce the possibility of overflows. Let's say you use 3 bits to count (rather than 1) your filter is now x3 the size and if you end up adding more than 7 items with the same key, you'll get an overflow and your false positive rate will go up. Cuckoo filters allow for deletions while using less space than a bloom or counting filter.
- mjevans 10y agoYou can think of the result of a bloom filter as a lossfully compressed index of the question: "Is this in the set?" which has the lossful property of sometimes falsely answering yes. If you actually have the backing data then it's possible to re-compute a new result which excludes some items. It is also possible to confirm if an answer that was yes is actually in the set.