CS 244 ’18: Cuckoo for Filters


Walter Mostowy, Nathan Butler

Original 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.

In networking and other domains, it is often desired to test membership of items in very large sets without incurring large memory or performance costs. Bloom filters have long remained a popular solution to this need, but it comes with drawbacks such as poor data locality and an inability to delete items from the set. There have been many alternate approaches attempting to improve on one or more aspects of other filters, such as the counting Bloom filter, the blocked Bloom filter, the d-Left Counting Bloom filter, and the Quotient filter. More recently, Fan et al present yet another alternative, the Cuckoo filter, and show that it has notable performance benefits over its competition. In this paper, we present our attempt to replicate some of the key findings of Fan et al in their presentation of the Cuckoo filter. We describe how we implemented six filters, tuned them to the extent they were specified by Fan et al, and tested their insertion and lookup performance. Although we find differences in our results versus those of Fan et al, we confirm that Cuckoo filters overall have excellent performance relative to their peers and speculate that the differences largely lie in hardware differences and underspecification.

Full Report.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s