Data structure for approximate set membership
A cuckoo filter is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set, like a Bloom filter does. False positive matches are possible, but false negatives are not – in other words, a query returns either "possibly in set" or "definitely not in set". A cuckoo filter can also delete existing items, which is
not supported by Bloom filters.
In addition, for applications that store many items and
target moderately low false positive rates, cuckoo filters can achieve
lower space overhead than space-optimized Bloom filters.
Cuckoo filters were first described in 2014.
Algorithm description.
A cuckoo filter uses a hash table based on cuckoo hashing to store the fingerprints of items. The data structure is broken into buckets of some size formula_1. To insert the fingerprint of an item formula_2, one first computes two potential buckets formula_3 and formula_4 where formula_2 could go. These buckets are calculated using the formula
formula_6
formula_7
Note that, due to the symmetry of the XOR operation, one can compute formula_4 from formula_3, and formula_3 from formula_4. As defined above, formula_12; it follows that formula_13. These properties are what make it possible to store the fingerprints with cuckoo hashing.
The fingerprint of formula_2 is placed into one of buckets formula_3 and formula_4. If the buckets are full, then one of the fingerprints in the bucket is evicted using cuckoo hashing, and placed into the other bucket where it can go. If that bucket, in turn, is also full, then that may trigger another eviction, etc.
The hash table can achieve both high utilization (thanks to cuckoo hashing), and compactness because only fingerprints are stored. Lookup and delete operations of a cuckoo filter are straightforward. 
There are a maximum of two buckets to check by formula_3 and formula_4. If found, the appropriate lookup or delete operation can be performed in formula_19 time. Often, in practice, formula_1 is a constant.
In order for the hash table to offer theoretical guarantees, the fingerprint size formula_21 must be at least formula_22 bits. Subject to this constraint, cuckoo filters guarantee a false-positive rate of at most formula_23.
Comparison to Bloom filters.
A cuckoo filter is similar to a Bloom filter in that they both are fast and compact, and they may both return false positives as answers to set-membership queries:
References.
 ;templatestyles src="Reflist/styles.css" / ;