# FODIT: A Filter-Based Module for Optimizing Data Storage in B5G IoT Environments
## 2 Background
### Filters  
Filters are employed to optimize time and space efficiency [28]. These filters are widely used in big data analytics, networking, the Internet of Things, database management, and other domains that require large-scale data processing and rapid response times. **Definition 1**. : _The filters are space-efficient data structures used to represent a set's elements and allow membership tests._  
The membership test determines whether a given element belongs to a set. If the result of the query is positive, the element is assumed to be in the set, although this may occur with a certain probability of a false positive. The false positive rate depends on the design of the specific filter. Currently, there are several variants of filters. In this article, we compare four types, namely, the Bloom filter [23], the counting Bloom filter [29], the sliding Bloom filter [30], and the cuckoo filter [24]. Each of these filters supports a distinct set of operations. For example, as shown in Table 1, all the filters support insertion; however, only the counting Bloom filter and the cuckoo filter support deletion. Additionally, the table presents the false positive rate for each filter and outlines the computational complexity of insertion, query, and deletion operations. Typically, these filters rely on hash functions for their implementation. The complexity and scalability of each filter depend on its specific design. This paper focuses on the cuckoo filter as a tool to optimize the B5G IoT storage and queries, which provides a lower false positive rate, resulting in more accurate membership tests. This makes it a suitable choice for applications where minimizing false positives is critical. Furthermore, as shown in Table 1, the cuckoo filter reduces processing time by requiring fewer hash functions compared to other filters. Figure 1: The figure displays IoT architecture. The cuckoo filter is a probabilistic data structure that can be represented as an array \(CF[b]\) of \(b\) bins, where each bin contains \(d\) entries used to represent the elements of a set \(A\), with all entries initially empty. This filter supports insertion, search, and deletion operations. To insert an element \(x\) into the cuckoo filter \(CF[b]\), Algorithm 1 is used [24]. The first step of the algorithm is to compute the fingerprint \(f_{x}\) of the element using cryptographic hash functions, as follows:  
\[f_{x}=fingerprint(x) \tag{1}\]  
In the next step, the partial-key cuckoo hashing technique shown in Equations (2) and (3) is used to obtain the indexes \(h_{1}\) and \(h_{2}\) of the candidate bins:  
\[h_{1} =hash(x) \tag{2}\] \[h_{2} =h_{1}\oplus hash(f_{x}) \tag{3}\]  
If the bin with index \(h_{1}\) has any empty entry, then the fingerprint \(f_{x}\) is added, and the process ends. Otherwise, it will look in \(h_{2}\). If \(h_{2}\) has any empty entry, then the fingerprint \(f_{x}\) is added, and the process ends. If \(h_{1}\) and \(h_{2}\) do not have any empty entries, a bin \(i\) (\(i=h_{1}\) or \(i=h_{2}\)) is randomly chosen, and then an entry \(e\) from bin \(i\) is selected (see Algorithm 1). Once the selection is made, the fingerprint \(f_{e}\) stored in the entry \(e\) is retrieved, and the fingerprint \(f_{x}\) is inserted. An alternative position \(j\) is now calculated, indicating the bin into which the fingerprint \(f_{e}\) can be inserted:  
\[j=i\oplus hash(f_{e}) \tag{4}\]  
If the bin \(j\) has any empty entries, then the fingerprint \(f_{e}\) is inserted, and the insertion process ends. This process is repeated until a bin with an empty entry is found or until a maximum number of relocations is reached. After the relocations, if an empty bin is not found, then the cuckoo filter \(CF[b]\) is considered full and no items can be inserted. The search operation of an element \(x\) in the filter \(CF[b]\) is performed by a membership query. Unlike the insertion process, the search process does not need to handle displaced elements; instead, it can look directly at the two guaranteed bins \(h1\) and \(h2\).