google / guava

Google core libraries for Java
Apache License 2.0
50.26k stars 10.91k forks source link

Allow removal of elements from a BloomFilter #1518

Open gissuebot opened 10 years ago

gissuebot commented 10 years ago

Original issue created by kak@google.com on 2013-08-29 at 07:19 AM


via https://groups.google.com/forum/#!topic/guava-discuss/bwimfMksFWg

In a paper from 2005[1], Pagh et al. proposed a bloom filter extension that is also capable of removing elements. Getting the number of items stored within is also possible through this extension. Do you see any possibility to extend Guava to also support these features?

[1] http://dl.acm.org/citation.cfm?id=1070548

bdupras commented 9 years ago

A filter construction described in a 2014 paper [1] allows for removal. The Cuckoo Filter is an alternative to a Bloom Filter that leverages partial key cuckoo hashing and a fingerprint/bucket structure.

@beala and I have proposed the addition of a Cuckoo Filter to Guava in #2226. We have a working implementation that we could adapt to the Guava style fairly if there's interest.

[1] Cuckoo Filter: Practically Better Than Bloom Bin Fan, David G. Andersen, Michael Kaminsky, Michael D. Mitzenmacher

/cc @apc999