# FODIT: A Filter-Based Module for Optimizing Data Storage in B5G IoT Environments
## 2 Background
### Filters
By using the filter, clients can immediately determine whether a record exists in the database without performing a full search. This pre-filtering mechanism avoids the computational overhead of querying for non-existent records. ### False Positives Analysis

False positives in the cuckoo filter occur when two elements, \(x\) and \(y\), share the same fingerprint and the same buckets. The probability of encountering a repeated fingerprint depends on the number of entries per bucket \(b\) and the fingerprint length \(f\) and is given by the following equation:

\[1-\left(1-\frac{1}{2^{f}}\right)^{2b}\approx\frac{2b}{2^{f}} \tag{5}\]

Equation (5) is derived through the following analysis. The probability of obtaining an identical fingerprint is as follows:

\[\frac{1}{2^{f}}\]

Consequently, the probability of obtaining a different fingerprint is as follows:

\[1-\frac{1}{2^{f}}\]

Given that the cuckoo filter permits \(b\) entries per bucket, the probability that none of the \(2b\) entries (across two buckets) match a specific fingerprint is as follows:

Figure 10: Figure presents comparative graphs between the query process with the FODIT module and the classical query process executed on DLT using 4%, 5%, 7%, and 8% of duplicate data. Assuming a desired false positive rate \(\epsilon\), if \(\frac{2b}{2^{7}}\leq\epsilon\), then the minimum required fingerprint length is approximately as follows:

\[f\geq\left\lceil\log_{2}\left(\frac{2b}{\epsilon}\right)\right\rceil=\left\lceil \log_{2}\left(\frac{1}{\epsilon}\right)+\log_{2}(2b)\right\rceil \tag{6}\]

Currently, there is no theoretical framework for determining the optimal number of entries per bucket. Nonetheless, based on empirical studies [49], it has been observed that the optimal configuration corresponds to \(b=4\). For the experiments in this article, the number of entries per bucket is \(b=4\), and the length of the fingerprint is \(f=256\) because we are using the hash function SHA-256 for computing the fingerprint \(f\). Given a target false positive rate of \(\epsilon=0.01\) (i.e., \(0.001\%\)) and a number of entries per bucket \(b=4\), we can compute the minimum required fingerprint length using the formula in Equation (6):

\[f\geq\left\lceil\log_{2}\left(\frac{2b}{\epsilon}\right)\right\rceil\]

Substituting the following values:

Figure 5:0

A fingerprint of at least \(f=10\) bits is required to achieve a \(1\%\) false positive rate when \(b=4\). Table 5 summarizes multiple false positive rates, as well as the corresponding percentages and the fingerprint lengths. On the other hand, if we are interested in computing the FPR, then given a fingerprint length of \(f=256\) bits and \(b=4\) entries per bucket, the false positive rate is approximately as follows:

Figure 5:1

Since

Figure 5:2

Then

Figure 5:3

The analysis of false positives in the cuckoo filter demonstrates that the false positive rate is tightly governed by the number of entries per bucket \(b\) and the fingerprint length \begin{table}
\begin{tabular}{l l l} \hline \hline \multicolumn{1}{c}{**FPR**} & \multicolumn{1}{c}{**Percentage**} & \multicolumn{1}{c}{**Length f**} \\ \hline \(\epsilon=0.01\) & \(1\%\) & \(10\) bits \\ \(\epsilon=0.001\) & \(0.1\%\) & \(13\) bits \\ \(\epsilon=0.0001\) & \(0.01\%\) & \(17\) bits \\ \(\epsilon=0.00001\) & \(0.001\%\) & \(20\) bits \\ \(\epsilon=0.000001\) & \(0.0001\%\) & \(23\) bits \\ \(\epsilon=0.0000001\) & \(0.000001\%\) & \(27\) bits \\ \(\epsilon=0.00000001\) & \(0.000001\%\) & \(30\) bits \\ \(\epsilon=0.000000001\) & \(0.0000001\%\) & \(33\) bits \\ \(\epsilon=0.000000001\) & \(0.00000001\%\) & \(37\) bits \\ \(\vdots\) & \(\vdots\) & \(\vdots\) \\ \(\epsilon=6.9\times 10^{-77}\) & \(1\times 10^{-75}\%\) & \(256\) bits \\ \hline \hline \end{tabular}
\end{table} 
Table 5: This table presents an analysis of the false positive rate (FPR) regarding the cuckoo filter. \(f\).