Package org.elasticsearch.common.util

Class CuckooFilter

java.lang.Object
org.elasticsearch.common.util.CuckooFilter
All Implemented Interfaces:
Writeable
public class CuckooFilter extends Object implements Writeable
An approximate set membership datastructure CuckooFilters are similar to Bloom Filters in usage; values are inserted, and the Cuckoo can be asked if it has seen a particular value before. Because the structure is approximate, it can return false positives (says it has seen an item when it has not). False negatives are not possible though; if the structure says it _has not_ seen an item, that can be trusted. The filter can "saturate" at which point the map has hit it's configured load factor (or near enough that a large number of evictions are not able to find a free slot) and will refuse to accept any new insertions. NOTE: this version does not support deletions, and as such does not save duplicate fingerprints (e.g. when inserting, if the fingerprint is already present in the candidate buckets, it is not inserted). By not saving duplicates, the CuckooFilter loses the ability to delete values. But not by allowing deletions, we can save space (do not need to waste slots on duplicate fingerprints), and we do not need to worry about inserts "overflowing" a bucket because the same item has been repeated repeatedly NOTE: this CuckooFilter exposes a number of Expert APIs which assume the caller has intimate knowledge about how the algorithm works. It is recommended to use SetBackedScalingCuckooFilter instead. Based on the paper: Fan, Bin, et al. "Cuckoo filter: Practically better than bloom." Proceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies. ACM, 2014. https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf

  • Method Details