CuckooFilter

A Cuckoo filter for instances of E that implements the ProbabilisticFilter interface.

"Cuckoo filters can replace Bloom filters for approximate set membership tests. Cuckoo filters support adding and removing items dynamically while achieving even higher performance than Bloom filters. For applications that store many items and target moderately low false positive rates, cuckoo filters have lower space overhead than space-optimized Bloom filters. Cuckoo filters outperform previous data structures that extend Bloom filters to support deletions substantially in both time and space." - Fan, et. al.

Cuckoo filters offer constant time performance for the basic operations add, remove, contains and sizeLong.

This class does not permit null elements.

Cuckoo filters implement the Serializable interface. They also support a more compact serial representation via the writeTo and readFrom methods. Both serialized forms will continue to be supported by future versions of this library. However, serial forms generated by newer versions of the code may not be readable by older versions of the code (e.g., a serialized cuckoo filter generated today may not be readable by a binary that was compiled 6 months ago).

ref: Cuckoo Filter: Practically Better Than Bloom Bin Fan, David G. Andersen, Michael Kaminsky†, Michael D. Mitzenmacher‡ Carnegie Mellon University, †Intel Labs, ‡Harvard University

Parameters

See also