# L-rCBF: Learning-Based Key-Value Data Structure for Dynamic Data Processing
## 3 Proposed Work
### Learned rCBF  
We aim to propose a learning-based data structure that guarantees the same semantic characteristics as a single rCBF suitable for dynamic data processing. A learned model for multi-class classification can be used to construct a key-value data structure because the structure can be considered a multi-class classification task with \(Q\) classes if \(Q\) values are available for the key-value pairs. However, the model is not fully representative of the characteristics of an rCBF because the model can return false negatives (FNs) and false-class results (FRs), while the rCBF never produces an FN or FR. Hence, appropriate auxiliary structures should be added to provide the same semantic guarantees as the rCBF. The proposed L-rCBF comprises a learned model, false-class result BF (FR-BF), and verification rCBF (V-rCBF) to guarantee the same semantic characteristics as a single rCBF. The model has the advantage of maintaining a consistent memory requirement regardless of the size of the positive data; however, it may produce FNs by returning negative class0 for elements in positive class \(v\) (i.e., classified as non-elements included in \(S^{c}\)), and FRs by returning positive class \(q\) for elements belonging to class \(v\) for \(1\leq v,q\leq Q\) and \(v\
eq q\). Because the rCBF never produces an FN or FR, a single BF and rCBF should be constructed to prevent FNs and FRs. Because both the rCBF and FBF are BF structures that can be used as key-value structures, even though the rCBF is better than the FBF in terms of dynamic data processing, the only difference between L-rCBF and L-FBF is whether the rCBF or FBF is used as the verification structure. Hence, because the auxiliary structures of the L-rCBF and L-FBF are similar, the construction and search procedures of the L-rCBF are the same as those of the L-FBF in [20], except for the construction and search of the V-rCBF (i.e., using the V-rCBF instead of the verification FBF (V-FBF)). In constructing the L-rCBF, the model is first trained for sets \(S\) and \(S^{c}_{tr}\) (i.e., \(S^{c}\) for training), and then tested for every element in \(S\) to construct the FR-BF and V-rCBF. The model learns the distribution of elements included in each positive class (i.e., elements in class \(v\) for \(1\leq v\leq Q\)) and that of non-elements (i.e., non-elements in negative class 0) from the training data. Improving the accuracy of the model is crucial because as the accuracy increases, the elements that must be stored in the auxiliary structures decrease, resulting in a reduction in the overall memory requirements of the L-rCBF. After training the model and before testing it, a threshold (\(\tau_{m}\)) in the model should be set to adjust the false positive rate (FPR) of the L-rCBF. Even though the additional FR-BF and V-rCBF can solve the FRs and FNs from the model, the auxiliary structures cannot control the FPR. Furthermore, the elements stored in the FR-BF and V-rCBF vary depending on \(\tau_{m}\). In other words, a large \(\tau_{m}\) can reduce the FPR from the model; however, it may cause more FNs from the model, which implies that a greater number of elements should be programmed into the V-rCBF. In the experiment, we first set the desired FPR of the model, and the \(\tau_{m}\) was set according to the desired FPR using the validation set \(S^{c}_{\text{rd}}\) (i.e., \(S^{c}\) for setting \(\tau_{m}\)). After setting \(\tau_{m}\), the model is tested for elements in set \(S\). Elements with FR returned from the model (i.e., \(S_{FR}\)) are programmed into the FR-BF; elements with FR or FN returned from the model (i.e., \(S_{FR}\) or \(S_{FN}\)), as well as those with FP from the FR-BF (i.e., \(B_{FP}\)) among those with true positive (TP) from the model (i.e., \(S_{TP}\)), are programmed into the V-rCBF (i.e., \(S_{V}=S_{FR}\cup S_{FN}\cup B_{FP}\) and \(B_{FP}\subset S_{TP}\)).