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.
A cuckoo filter uses a -way set-associative hash table based on cuckoo hashing to store the fingerprints of all items (every bucket of the hashtable can store up to entries).
Particularly, the two potential buckets and in the table for a given item required
by cuckoo hashing are calculated by the following two hash functions
(termed as partial-key cuckoo hashing):
Applying the above two hash functions
to construct a cuckoo hash table enables item relocation based only on fingerprints
when retrieving the original item is impossible.
As a result, when inserting a new item that requires relocating an existing item ,
the other possible location in the table
for this item kicked out from bucket is calculated by
Based on partial-key cuckoo hashing, 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 locations to check by and .
If found, the appropriate lookup or delete operation can be performed in time.
More theoretical analysis of cuckoo filters can be found in the literature.
A cuckoo filter is similar to a Bloom filter in that they both are very fast and compact,
and they may both return false positives as answers to set-membership queries:
Space-optimal Bloom filters use bits of space per inserted key, where is the false positive rate. A cuckoo filter requires where is the hash table load factor, which can be based on the cuckoo filter’s setting. Note that the information theoretical lower bound requires bits for each item. Both bloom filters and cuckoo filters with low load can be compressed when not in use.
On a positive lookup, a space-optimal Bloom filter requires a constant memory accesses into the bit array, whereas a cuckoo filter requires constant two lookups at most.
Cuckoo filters have degraded insertion speed after reaching a load threshold, when table expanding is recommended. In contrast, Bloom filters can keep inserting new items at the cost of a higher false positive rate before expansion.
Bloom filters offer fast union and approximate intersection operations using cheap bitwise operations, which can also be applied to compressed bloom filters if streaming compression is used.
A cuckoo filter can only delete items that are known to be inserted before.
Insertion can fail and rehashing is required like other cuckoo hash tables. Note that the amortized insertion complexity is still .