Cuckoo filter is a Bloom filter replacement for approximated set-membership queries. While Bloom filters are well-known space-efficient data structures to serve queries like "if item x is in a set?", they do not support deletion. Their variances to enable deletion (like counting Bloom filters) usually require much more space.
Cuckoo filters provide the flexibility to add and remove items dynamically. A cuckoo filter is based on cuckoo hashing (and therefore named as cuckoo filter). It is essentially a cuckoo hash table storing each key's fingerprint. Cuckoo hash tables can be highly compact, thus a cuckoo filter could use less space than conventional Bloom filters, for applications that require low false positive rates (< 3%).
For details about the algorithm and citations please use this article for now
"Cuckoo Filter: Better Than Bloom" by Bin Fan, Dave Andersen and Michael Kaminsky
A cuckoo filter supports following operations:
- Add(key): insert key to the filter
- Contain(key): return if key is already inserted, it may return false positive results like Bloom filters
- Delete(key): delete the given key from the filter
- Size(): return the total number of keys existing in the filter
- SizeInBytes(): return the filter size in bytes
/src/
the C++ implementation of cuckoo filter
/example/test.cc
an example of using cuckoo filter. To build this example, simply type
$ make
Bin Fan [email protected]
David G. Andersen [email protected]
Michael Kaminsky [email protected]