# L-rCBF: Learning-Based Key-Value Data Structure for Dynamic Data Processing
## 2 Related Work  
### Functional Bloom Filter  
The functional Bloom filter (FBF) is a data structure that stores values corresponding to keys, and the key-value pairs are included in set \(S=\{(x_{1},v_{1}),(x_{2},v_{2}),\cdots,(x_{n},v_{n})\}\). An FBF is an \(m\)-cell array, and each cell stores a value. The FBF can perform three operations: insert (program), search (query), and delete. The FBF can be configured to support the deletion operation depending on whether the data are static or dynamic. The insert operation for dynamic data is slightly different from that for static data. If deletions are infrequent, the FBF is constructed for static data because the search performance of the FBF for static data is better than that for dynamic data. Most previous studies described the FBF for static data without considering deletions; however, we explain an FBF that supports deletion for dynamic data.  
The operations use \(k\) hash functions to access \(k\) cells. The optimal \(k\) for the BF structures can be calculated as follows [24; 25]:  
\[k=\frac{m}{n}ln2, \tag{1}\]  
where \(n\) denotes the number of elements in set \(S\). Let \(L\) be the number of bits in a single cell for a value. Each cell is initialized to 0 and can represent \(2^{L}-2\) values because the maximum value \(2^{L}-1\) is reserved to represent a _conflict_ cell, which implies that two or more elements are stored in the cell.  
In inserting an element (\(x_{j}\), \(v_{j}\)) into an FBF for dynamic data, for \(1\leq j\leq n\), all cells with value 0 among the cells pointed to by \(k\) hash functions are set to value \(v_{j}\), and the other cells, which have values different from 0, are set to _conflict_ cells with \(2^{L}-1\). For an FBF for static data, the cells that already have the value \(v_{j}\) retain this value even if the keys already stored in the cells are not equal to \(x_{j}\).  
In searching for an input in set \(U\) (i.e., \(U=S\cup S^{c}\)), an FBF returns one of three search results: _negative_, _positive_, or _indeterminable_ (INDET). If at least one of the \(k\) cells has a value of 0 or if two or more cells among the cells have different values, a negative is returned from the FBF. If every cell except for the conflict cells has the same value, the value is returned, which implies a positive; however, positives may be false owing to hash collisions. If all cells have value \(2^{L}-1\) (i.e., conflict cells), an INDET is returned. False positive (FP) and INDET results are classified as _search failures_.  
In deleting an element in an FBF for dynamic data, only cells storing one element can be used among the \(k\) cells. That is, among the cells pointed to by the \(k\) hash functions, the cells, except for the conflict cells, are changed to 0. Conflict cells with two or more elements inserted are not used for deletion to prevent false negatives (FNs). If all accessed \(k\) cells are conflict cells, the element cannot be deleted and is called an _undeletable_. In addition, the FBF for static data does not support deletion operations.  
Even though the FBF operations can be adjusted for dynamic data, the FBF is not perfectly suitable for frequent insertions and deletions because conflict cells cannot be used for the three operations.  
In addition, in the three operations of BF structures (i.e., FBF and rCBF), the cells pointed to by \(k\) hash functions are accessed. Once a BF structure is constructed, the \(k\) does not change while repeating insertions and deletions, unless the structure is reconstructed. Hence, the time complexity of the operations is \(O(1)\).