## 2 Background and Motivation
### Background
#### 2.1.2. Bloom Filter Data Structure  
A Bloom filter (\(B\)) is a space-efficient probabilistic data structure [18; 19; 20] that is used to test whether an element is a member of a set. Bloom filters utilize \(k\) distinct hash functions (\(h_{1}\),..., \(h_{k}\)) to map elements in the set (\(S\) = {\(s_{1}\),..., \(s_{n}\)}) to a bit array of \(m\) bits. When an element is inserted into the filter, it is hashed by each of the hash functions, and the corresponding bits in the array are set to 1. To check if an element is a member of the set, the element is hashed by the same hash functions, and the corresponding bits are checked. If any of the bits are not set, then the element is definitely not in the set. If all bits are set, it is probable that the element is in the set, but there is a chance of false positives.  
Figure 2 depicts the insert and query operations of the standard Bloom filter.  
* To insert each object \(s_{i}\) in the set \(S\),
* Compute the hash values \(h_{1}(s_{i})\),..., \(h_{k}(s_{i})\) for each object \(s_{i}\). The hash functions can be any hash functions that are collision-resistant.
* Set the corresponding bits in the Bloom filter \(B\) such that \(B[h_{1}(s_{i})]=B[h_{2}(s_{i})]=\ldots=B[h_{k}(s_{i})]=1\). Figure 2 depicts the insert operation of object\({}_{A}\), object\({}_{C}\), and object\({}_{F}\).  
* To determine whether an object, \(s_{i}\), belongs to set \(S\),
* Compute the hash values \(h_{1}(s_{i})\),..., \(h_{k}(s_{i})\) for each object \(s_{i}\).
* If all corresponding bits in the Bloom filter \(B\) are set, then membership query is successful; otherwise, the element is not in the set. However, if collisions occur during the hashing process and cause \(h_{1}(s_{i})\),..., \(h_{k}(s_{i})\) in the bit vector \(B\) to be set to 1, this leads to false positives. Figure 2 depicts the query operation of object\({}_{A}\) and object\({}_{D}\). As object\({}_{A}\) was originally inserted into the Bloom filter, its membership query results are positive. In contrast, object\({}_{D}\) was not inserted into the Bloom filter. However, the membership query returns a positive result due to the hash collisions. This approach results in false-positive errors.  
Figure 1: File distribution and transfer mechanisms. (**a**) File distribution. (**b**) State-of-the-art big data transfer mechanism. (**c**) Object-based big data transfer mechanism.  
As described above, if \(m\) is the size of the Bloom filter and \(k\) is the number of hash functions, then the probability that a certain bit is still zero after inserting one element and after insertng \(n\) elements is represented as follows [21]:  
\[p=(1-\frac{1}{m})^{k} \tag{1}\]  
\[p=(1-\frac{1}{m})^{kn}\approx(e^{-kn/m}). \tag{2}\]  
Therefore, the probability of false positive errors can be expressed as  
\[\epsilon=(1-(1-\frac{1}{m})^{kn})^{k}\approx(1-e^{-kn/m})^{k}. \tag{3}\]  
From Equation (3), we observe that a higher number of hash functions results in fewer false-positive errors. However, increasing the number of hash functions directly affects the computational overhead. Therefore, for a given \(m\) and \(n\), the required number of hash functions can be represented as  
\[k=\frac{m}{n}ln2. \tag{4}\]  
By substituting Equation (4) into Equation (3), we can express the false-positive error probability as  
\[e=(1-e^{(\frac{m}{n}ln2)\frac{n}{m})\frac{m}{n}ln2}. \tag{5}\]  
By simplifying Equation (5), we can represent it as  
\[lnc=-\frac{m}{n}(ln2)^{2} \tag{6}\]  
Thus, required number of bits is  
\[m=-\frac{nln\epsilon}{ln2^{2}} \tag{7}\]