Cuckoo filter

Cuckoo filter

A cuckoo filter is a data structure that is used as a filter and is based on the cuckoo hash table. It replaces the original element with a fingerprint of the element in the hash table and has four major advantages over traditional Bloom Filters: it supports adding and removing items dynamically, achieves higher lookup performance, is easier to implement than alternatives such as the quotient filter, and requires less space than a space-optimized Bloom filter when the target false positive rate is less than 3%.From: Data Plane Development Kit (DPDK) [2020], Cluster-based distributed dynamic cuckoo filter system for Redis [2020]

Forwarding

View Chapter

Purchase Book

Published in Heqing Zhu, Data Plane Development Kit (DPDK), 2020

Yipeng Wang, Jasvinder Singh, Zhe Tao, Liang Ma, Heqing Zhu

The membership library in DPDK provides a couple of different filter data structures; each data structure has a slightly different design and property. For example, a vector of bloom filters is provided to serve as an array of bloom filters. With this data structure, one can check if a key belongs to a certain data set of all the data sets represented by the multiple bloom filters. Another filter data structure is hash table-based filter, which is based on cuckoo filter (B. Fan, et al, Cuckoo Filter: Practically Better Than Bloom.). Compared to traditional hash table, cuckoo filter does not store the full key but only a signature of the key into the table. Without the full key comparison, there could be false positives while the memory requirement is much less.

Cluster-based distributed dynamic cuckoo filter system for Redis

View Article

Journal Information

Published in International Journal of Parallel, Emergent and Distributed Systems, 2020

Peng Li, Baozhou Luo, Wenjun Zhu, He Xu

By replacing the original element with a ﬁngerprint of the element in the cuckoo hash table [19], Fan et al. recently proposed the cuckoo filter, a practical data structure that can replace both counting and traditional Bloom Filters with four major advantages: (1) It supports adding and removing items dynamically; (2) It achieves higher lookup performance; (3) It is easier to implement than alternatives such as the quotient ﬁlter; and (4) it requires less space than a space-optimised Bloom ﬁlter when the target false positive rate ε is less than 3%.

Explore chapters and articles related to this topic

Forwarding

Cluster-based distributed dynamic cuckoo filter system for Redis