## 2 Related Works
### Bloom Filter  
The Bloom filter is a multi-bit data structure that represents a set of elements succinctly and efficiently, and thus can support membership queries. It was proposed by [PERSON] in 1970 [21], and is widely used in packet classification [22], web caching [23], and network security [24].  
Essentially, the Bloom filter is an array of \(m\) bits with an initial value of zero for each bit, on which a set of \(k\) different hash functions \(h_{1}(),h_{2}(),\ldots,h_{k}()\) are used to insert or check elements. When programming the filter, or inserting the element \(x\), the bit positions in the array corresponding to the \(k\) hash indexes \(h_{1}(x),h_{2}(x),\ldots,h_{k}(x)\) are set to '1'. Instead, given a query for the element \(y\), we check the corresponding \(k\) bits at positions \(h_{1}(y),h_{2}(y),\ldots,h_{k}(y)\) generated from the same hash functions. If and only if all of them are '1', the filter returns a positive and we can conjecture that the element \(y\) would be a member of the set.  
The standard Bloom filter structure is shown in Figure 2, on which we have inserted elements \(x\) and \(y\), then query the membership of elements \(x\), \(y\), \(z_{1}\), and \(z_{2}\) (\(z_{1}\) and \(z_{2}\) have not been inserted in the filter). Obviously, the query results for \(x,y,z_{1}\), and \(z_{2}\) are positive, positive, negative, and positive, respectively.  
The most recognized advantage of the Bloom filter is that there are no results of false negatives, i.e., the membership query results will always return positives for inserted elements. However, the Bloom filter still produces false positive results with a certain probability. Considering a query in Figure 2 for the element \(z_{2}\) that has not been inserted, a false positive is returned since all the bits at positions \(h_{1}(z_{2})\), \(h_{2}(z_{2})\), and \(h_{3}(z_{2})\) are set to '1', which is caused by the insertion of other elements.  
Now, let us derive the false positive probability of the Bloom filter step by step. Supposing that generated hash indexes are uniformly distributed, the probability that a random bit in an array of \(m\) bits is set to '1' by a single hash function is clearly \(1/m\). After inserting \(n\) elements, the probability that a certain bit is not set to '1' is expressed as  
\[\left(1-\frac{1}{m}\right)^{k\cdot n}, \tag{1}\]  
Figure 2: Illustration of a standard Bloom filter querying membership of elements \(x\), \(y\), \(z_{1}\), and \(z_{2}\).  
where \(k\) is the number of hash functions. Hence, the false positive probability of the Bloom filter is calculated as  
\[f_{\text{BF}}=\left[1-\left(1-\frac{1}{m}\right)^{k\cdot n}\right]^{k}, \tag{2}\]  
if the size of the filter (i.e., \(m\)) is large enough, Equation (2) can be further simplified as follows.  
\[f_{\text{BF}}\approx\left(1-\text{e}^{-\frac{k\cdot n}{m}}\right)^{k}. \tag{3}\]  
As shown, the false positive probability can be reduced by adjusting the size of the Bloom filter and the number of hash functions, but it cannot be completely eliminated. For a given ratio of \(m/n\), in order to minimize \(f_{\text{BF}}\), we obtain the optimal value of \(k\):  
\[k_{\text{opt}}=\frac{m}{n}\cdot\ln 2, \tag{4}\]  
and, thus, the false positive probability in the optimal case is stated as  
\[f_{\text{BF min}}\approx\left(\frac{1}{2}\right)^{k}=\left(0.6185\right)^{ \frac{n}{n}}. \tag{5}\]  
There is another major limitation of the Bloom filter: it does not support the deletion of elements. Since a particular bit position may have been set to '1' by more than one element, clearing the bit (i.e., setting it to '0') when deleting a single element cannot guarantee that the Bloom filter is free from false negatives. Therefore, the element cannot be removed.