# L-rCBF: Learning-Based Key-Value Data Structure for Dynamic Data Processing
## 3 Proposed Work
### Deletion Algorithm of L-rCBF  
The proposed L-rCBF should provide a deletion to guarantee the same characteristics as those of a single rCBF. However, once a model in the L-rCBF is trained on a set, specific elements cannot be deleted from the model because it learns the distribution of the set. Therefore, we propose a deletion algorithm for elements inserted using the auxiliary structures (i.e., the FR-BF and V-rCBF). In other words, the novelty of this paper lies in the fact that a key-value structure using a learned model can support deletions. Although L-rCBF is similar to L-FBF in terms of both construction and search procedures, the L-FBF in [20] cannot support deletions because the V-FBF in the L-FBF is for static data without considering deletions. Algorithm 2 shows the deletion algorithm for the L-rCBF. When searching for an element after deleting it, the L-rCBF should return a negative. Hence, depending on which set the element to be deleted belongs to (i.e., \(S_{FN}\), \(S_{FR}\), \(B_{FP}\), or \(S_{TP}-B_{FP}\)), one of two operations is performed: OP1) delete the element from the V-rCBF or OP2) program the element to the FR-BF. ```
1:proceduredelete_LrCBF(\(x,v\))
2:\(result\) = testModel(\(x\))
3:if\(result==0\)then\(\triangleright\) FN from model
4:\(operation\) = OP1
5:elseif\(result!=v\)then\(\triangleright\) FR from model
6:\(operation\) = OP1
7:else\(\triangleright\) TP from model
8:ifqueryBF(FR-BF, \(x\)) then\(\triangleright\) FP from FR-BF
9:\(operation\) = OP1
10:else
11:\(operation\) = OP2
12:if\(operation==OP1\)then
13:delete_rCBF(V-rCBF, \(x\), \(v\))
14:else
15:programBF(FR-BF, \(x\))
```  
**Algorithm 2** Deletion algorithm of L-rCBF  
To delete element (\(x\), \(v\)) in \(S\) for \(1\leq v\leq Q\), a learned model is first tested (line 2). If the element is included in \(S_{FN}\), the model returns a negative (i.e., \(result==0\)), which implies that the element is stored in the V-rCBF; hence, for the V-rCBF to return a negative as a final result, the element is deleted from the V-rCBF (lines 3, 4, 12, and 13). If the element is included in \(S_{FR}\), the model returns a value not equal to \(v\), resulting in a query to the FR-BF. Because every element in \(S_{FR}\) is stored in the FR-BF, it returns a positive, and the V-rCBF is then queried. Hence, the element is deleted from the V-rCBF (lines 5, 6, 12, and 13). Even though the model returns \(v\) (i.e., \(S_{TP}\)), the element is deleted from the V-rCBF if the FR-BF returns a positive (i.e., \(B_{FP}\), lines 8, 9, 12, and 13). Otherwise, if the FR-BF returns a negative (i.e., \(S_{TP}-B_{FP}\)), the element is programmed into the FR-BF (lines 11 and 15) to change the final result of the search, from \(v\) to negative, after the deletion. In other words, when searching for the element in \(S_{TP}-B_{FP}\) after OP2, the FR-BF returns a positive, and the V-rCBF then returns a negative as the final result because the element has never been programmed into the V-rCBF. In addition, the time complexity of the deletion algorithm is \(O(1)\) because the model is tested once and one of the auxiliary structures (i.e., V-rCBF or FR-BF) is accessed to perform OP1 or OP2. After performing OP2, the L-rCBF may return a few FNs because additional FPs from the FR-BF may occur. Before deletions, elements in \(S_{TP}-B_{FP}\) are not stored in both the FR-BF and V-rCBF because the model returns true values for the elements. However, if additional FPs from the FR-BF occur after deleting some elements in \(S_{TP}-B_{FP}\), the V-rCBF is queried for the elements with FPs (i.e., those in a subset of \(S_{TP}-B_{FP}\)) and returns negatives, which are false results (i.e., FNs). To prevent such FNs, when the number of deleted elements exceeds a threshold (\(\tau_{d}\)), the L-rCBF is reconstructed for the remaining elements. \(\tau_{d}\) can be set according to the number of additional FPs from the FR-BF (\(n_{fp,b}\)) because the FPs from the FR-BF cause the V-rCBF to return the FNs as the final results.