# L-rCBF: Learning-Based Key-Value Data Structure for Dynamic Data Processing
## 5 Performance Evaluation
### Comparison of Probabilities between Theoretical and Experimental Results for rCBF  
This section compares the _undeletable_ and _search failure_ probabilities (i.e., \(P(U)\) and \(P(F_{s})\)) between the theoretical and experimental results for the rCBF and FBF supporting the deletion operation. To obtain the results for \(P(U)\) and \(P(F_{s})\), experiments were performed using \(2^{15}\) random URLs for set \(S\) and \(2*2^{15}\) URLs for \(S^{c}\), and the URLs were obtained from ALEXA [30]. To allocate the same number of bits to a value field in the rCBF and a cell in the FBF, we assumed 254 return values; hence, a cell in the rCBF has a two-bit counter and eight-bit value field, and a cell in the FBF has eight bits to store values. However, the rCBF can store up to 255 values for eight bits (i.e., \(2^{8}-1\)) because the rCBF does not need to reserve the maximum value \(2^{8}-1\) as a conflict value. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline  & & **rCBF** & \multicolumn{3}{c}{**L-FBF\({}_{2}\)**} \\  & & & **Dynamic Data** & **Static Data** \\ \hline \multirow{2}{*}{\(S\)} & TP & 94.896 & 99.938 & 99.982 \\  & INDET (\(l|S\)) & 5.104 & 0.062 & 0.018 \\ \hline \multirow{2}{*}{\(S^{c}\)} & TN & 99.318 & 99.453 & 99.453 \\  & FP (\(F_{p}|S^{c}\)) & 0.646 & 0.547 & 0.547 \\  & INDET (\(l|S^{c}\)) & 0.036 & 0 & 0 \\ \hline Search failures & FP+INDET & 1.307 & 0.258 & 0.245 & 0.218 \\ \hline \multicolumn{2}{c}{Reduction rate in search failures} & \multirow{2}{*}{-} & \multirow{2}{*}{81.25} & \multirow{2}{*}{83.32} \\  & compared with a single rCBF & & & & \\ \end{tabular}
\end{table} 
Table 4: Comparison of search failure rates between L-FBFs for dynamic and static data (%). \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline  & & **rCBF** & **L-FBF\({}_{1}\)** & **L-FBF\({}_{2}\)** & **L-rCBF\({}_{1}\)** & **L-rCBF\({}_{2}\)** \\ \hline \multirow{2}{*}{\(S\)} & TP & 94.896 & 99.901 & 99.938 & 98.767 & 99.181 \\  & INDET (\(l|S\)) & 5.104 & 0.099 & 0.062 & 1.233 & 0.819 \\ \hline \multirow{2}{*}{\(S^{c}\)} & TN & 99.318 & 99.480 & 99.453 & 99.388 & 99.407 \\  & FP (\(F_{p}|S^{c}\)) & 0.646 & 0.520 & 0.547 & 0.610 & 0.593 \\  & INDET (\(l|S^{c}\)) & 0.036 & 0 & 0 & 0.002 & 0 \\ \hline Search failures & FP+INDET & 1.307 & 0.258 & 0.245 & 0.998 & 0.734 \\ \hline \multicolumn{2}{c}{Reduction rate in search failures} & \multirow{2}{*}{-} & \multirow{2}{*}{80.26} & \multirow{2}{*}{81.25} & \multirow{2}{*}{23.64} & \multirow{2}{*}{43.84} \\  & compared with a single rCBF & & & & & \\ \end{tabular}
\end{table} 
Table 3: Comparison of search failure rates when using same amount of memory (%). \begin{table}
\begin{tabular}{c c c c c} \hline \hline  & **L-FBF\({}_{3}\)** & **L-FBF\({}_{4}\)** & **L-rCBF\({}_{1}\)** & **L-rCBF\({}_{2}\)** \\ \hline UNDEL-FP & 0.027 & 0.022 & 0.014 & 0.014 \\ UNDEL-C & 1.227 & 0.758 & 0.003 & 0 \\ \hline Total & 1.255 & 0.779 & 0.016 & 0.014 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Comparison of undeletable rates when using verification structure with same \(\alpha_{v}\) (%). Let \(n\) be the number of elements stored in a BF structure, \(\alpha\) the size factor of the structure, \(m\) the number of cells in the structure (i.e., BF size \(m=\alpha n\)), and \(M\) the memory requirement of the structure. Figures 4 and 5 compare the \(P(U)\) and \(P(F_{s})\) between the theoretical and experimental results according to the BF size, respectively. When each \(\alpha\) of the FBF is 2, 4, and 8, each \(\alpha\) of the rCBF\({}_{1}\) is 1.6, 3.2, and 6.4, respectively, because the rCBF\({}_{1}\) uses the same \(M\) as the FBF. The rCBF\({}_{2}\) uses the same \(\alpha\) as the FBF. Although the \(\alpha\) of the rCBF\({}_{1}\) is smaller than that of the FBF, the \(P(U)\) of the rCBF\({}_{1}\) is much smaller than that of the FBF. The \(P(F_{S})\) of the rCBF\({}_{1}\) is slightly greater than that of the FBF; however, if insertions and deletions are repeated, the \(P(F_{S})\) of the rCBF would be better than that of the FBF.