## 2 Related Works
### Cuckoo Filter  
The cuckoo filter [25] proposed recently is considered an alternative to the Bloom filter that supports deletion operations and offers a lower false positive probability, for instance in networking applications such as IP packet forwarding [26], message authentication [27], and traffic monitoring [28]. It is a compact data structure using the probability-based cuckoo hashing algorithm [29], which maintains two dynamic hash tables to address hash collisions when inserting new keys. Instead of a bit in the Bloom filter, a partial key is used in the cuckoo filter to perform approximate set membership testing. In more detail, a multi-bit fingerprint is generated from a hash function \(f()\); for example, \(f(x)\) is stored in the filter when inserting the element \(x\). The cuckoo filter comprises an array of \(m\) buckets, each of which is formed by \(b\) cells, and each cell can store the fingerprint of an element. The fingerprint for an element \(x\) (i.e., \(f(x)\)) can be stored in two buckets at the positions given by two hash functions \(h_{1}()\) and \(h_{2}()\), respectively. In the original cuckoo filter paper [25], the authors suggest \(b=4\), to achieve the best or close-to-best space efficiency for the false positive probability. In addition, the authors cleverly set the following relationship (for an element \(x\)):  
\[h_{2}(x)=h_{1}(x)\oplus h_{1}[f(x)], \tag{6}\]  
the exclusive-OR operation in Equation (6) ensures an important property:  
\[h_{1}(x)=h_{2}(x)\oplus h_{1}[f(x)], \tag{7}\]  
namely, \(h_{1}(x)\) can also be calculated from \(h_{2}(x)\) and \(f(x)\), no matter if element \(x\) is stored at \(h_{1}(x)\) or \(h_{2}(x)\), which is important in programming. A cuckoo filter on which several elements are inserted is illustrated in Figure 3.  
In order to insert an element \(x\), select an empty cell in the buckets \(h_{1}(x)\) or \(h_{2}(x)\) and then store the fingerprint \(f(x)\), if any. If two buckets are full, randomly remove an element from one cell in these buckets and store \(f(x)\) in that cell. The element ejected will be inserted into its alternate bucket, which can be found by doing the exclusive-OR of its original address information (i.e., \(h_{1}(x)\) or \(h_{2}(x)\)) and the hash function \(h_{1}()\) of its fingerprint. The above procedure will be iterated until a free cell is found, and the element cannot be inserted in the filter if there are no empty buckets or cells available. The inserting process is more complex than that of the Bloom filter, especially in the case of the cuckoo filter with high occupancy, an insertion may lead to hundreds of element translocations, which is one of the drawbacks of the cuckoo filter. When checking the membership of an element \(y\), \(f(y)\), \(h_{1}(y)\), and \(h_{2}(y)\) are computed, and then it is checked if \(f(y)\) is stored in any cell of those buckets given by \(h_{1}(y)\) and \(h_{2}(y)\). Therefore, the results will always return positives for the elements that have been inserted in the filter. However, like the Bloom filter, there are also false positives when the element \(y\) not stored in the filter has the same fingerprint as an element \(x\) stored in the buckets \(h_{1}(y)\) or \(h_{2}(y)\) (i.e., \(f(y)=f(x)\)). Specifically, let us consider the worst case in which the cuckoo filter is full, the probability that \(f(y)\) matches the \(f\)-bit fingerprint in a cell is at most \(1/2^{f}\). Therefore, the upper bound of the false positive probability can be expressed as  
\[f_{\text{CF max}}=1-\left(1-\frac{1}{2^{f}}\right)^{2b}\approx\frac{2b}{2^{f}}, \tag{8}\]  
where \(b\) is the number of cells. As the authors state in ref. [25], Equation (8) can give a reasonably accurate estimate when the hash table is 95% full. For a cuckoo filter on which \(n\) elements are inserted, the load factor \(\alpha\) (\(0\leq\alpha\leq 1\)) or the occupancy is defined as  
\[\alpha=\frac{n}{b\cdot m}, \tag{9}\]  
where \(m\) is the total number of buckets or the size of the filter.