# L-rCBF: Learning-Based Key-Value Data Structure for Dynamic Data Processing
## 5 Performance Evaluation
### Performance Comparison of rCBF, L-FBF, and L-rCBF  
Our simulation was performed for datasets with specific distributions because learning-based data structures use the distribution of the elements in each set. A total of 245,514 URLs were used as a positive set (i.e., \(S\)) with six return values (i.e., six classes) [28], and 1,491,178 blacklisted URLs were used as a negative set (i.e., \(S^{c}\)) [29]. We compared five BF structures: a single rCBF, L-FBF\({}_{1}\), L-FBF\({}_{2}\), L-rCBF\({}_{1}\), and L-rCBF\({}_{2}\). Each of the two L-FBFs supports the deletion operation using a V-FBF for dynamic data. This performance comparison used two models with different classification accuracies and memory requirements. One model was included in the L-FBF\({}_{1}\) and L-rCBF\({}_{1}\), and the other model was included in the L-FBF\({}_{2}\) and L-rCBF\({}_{2}\). The memory requirement of a model generally increases with the accuracy of the model in a learning-based structure. However, this does not necessarily imply that the total memory requirement of the structure increases. For a fair comparison, we first constructed the L-rCBF\({}_{1}\), and then constructed the other four structures with the same memory requirement as that of the L-rCBF\({}_{1}\). To train the two models, character-level pretrained embeddings were utilized with principal component analysis (PCA). The models include a long short-term memory (LSTM) layer, two one-dimensional convolutional neural network (CNN) layers, and three fully connected layers with softmax activation. However, because the hyperparameters of the two models are different, the memory requirements and accuracies of the models are also different. Table 1 compares the number of weights (\(w\)) and memory requirements of the two models. The memory requirement of a model depends on \(w\) because it is calculated using \(w\). Model\({}_{2}\) for the L-rCBF\({}_{2}\) and L-FBF\({}_{2}\) requires more memory than Model\({}_{1}\) for the L-rCBF\({}_{1}\) and L-FBF\({}_{1}\); however, Model\({}_{2}\) provides a higher level of accuracy. Because an additional FP from the FR-BF causes an FN from the V-rCBF, an L-rCBF should be reconstructed at threshold \(\tau_{d}\) before the FR-BF begins to return an additional FP owing to too many deletions. Threshold \(\tau_{d}\) can be set to the number of deleted elements at the point where the theoretically calculated \(n_{fp,b}\) is less than and close to 1. Let \(n_{tp}\) be \(|S_{TP}|\), \(n_{b}\) the number of elements programmed in the FR-BF (i.e., \(|S_{FR}|\)), \(m_{b}\) the FR-BF size, \(k_{b}\) the number of hash functions of the FR-BF, and \(n_{b}^{\prime}\) the number of elements to be programmed into the FR-BF for deletion. Therefore, \(n_{fp,b}\) can be calculated as follows:  
\[n_{fp,b}=(n_{tp}-n_{b}^{\prime})\cdot\Big{(}1-(1-\frac{1}{m_{b}})^{k_{b}(n_{b} +n_{b}^{\prime})}\Big{)}^{k_{b}}. \tag{11}\]  
Figure 3 shows the theoretical and experimental \(n_{fp,b}\) in the L-rCBF\({}_{1}\) with Model\({}_{1}\) according to the elements deleted. When deleting more than 15% of the elements in the L-rCBF\({}_{1}\), \(n_{fp,b}\geq 1\). Hence, \(\tau_{d}\) can be predefined as 15% of the elements. In this experiment, reconstruction was not considered for a simple performance comparison; hence, to evaluate the deletion performance, 15% of the randomly selected URLs among those in \(S\) were deleted. In addition, a search performance experiment was performed for all URLs in \(U\) (i.e., \(U=S\cup S_{ls}^{c}\)). In the construction procedure, the L-rCBF\({}_{1}\) is constructed first, and then the other four structures are constructed with the same amount of memory as that of the L-rCBF\({}_{1}\).