Website Maintenance Alert
Due to scheduled maintenance, the USENIX website will not be available on Tuesday, December 17, from 10:00 am to 2:00 pm Pacific Daylight Time (UTC -7). We apologize for the inconvenience.
If you are trying to register for Enigma 2020, please complete your registration before or after this time period.
Cuckoo Filter: Better Than Bloom
Bin Fan, David G. Andersen, and Michael Kaminsky
High-speed approximate set-membership tests are critical for many applications, and Bloom filters are used widely in practice, but do not support deletion. In this article, we describe a new data structure called the cuckoo filter that can replace Bloom filters for many approximate set-membership test applications. Cuckoo filters allow adding and removing items dynamically while achieving higher lookup performance, and also use less space than conventional, non-deletion-supporting Bloom filters for applications that require low false positive rates (ϵ< 3%).