# L-rCBF: Learning-Based Key-Value Data Structure for Dynamic Data Processing
## 2 Related Work
### Counting Bloom Filter with Return Values  
The counting Bloom filter with return values (rCBF) is a key-value data structure suitable for dynamic data processing [5]. An rCBF is an \(m\)-cell array, where each cell consists of _counter_ and _value_ fields. The rCBF performs three operations using \(k\) hash functions: insert (program), search (query), and delete. The optimal \(k\) used for the rCBF can be calculated using \(\frac{m}{n}ln2\) as in (1), where \(n\) is the number of elements in set \(S=\{(x_{1},v_{1}),(x_{2},v_{2}),\cdots,(x_{n},v_{n})\}\)[24; 25].  
Let \(L\) be the number of bits in the value field and \(R\) the number of bits in the counter field. Each value field can represent \(2^{L}-1\) values because the rCBF does not need to reserve a value to represent a _conflict_ cell, unlike the FBF, which can represent \(2^{L}-2\) values. Each counter field represents the number of inserted elements (\(c\)) in each cell, and the maximum count \(c_{max}\) is \(2^{R}-1\).  
Figure 1 presents an example of inserting elements into an rCBF with \(n=3\), \(m=7\), and \(k=3\). To insert element (\(x_{3}\), \(v_{3}\)) into the cells pointed to by \(h_{1}(x_{1})\), \(h_{2}(x_{1})\), and \(h_{3}(x_{1})\), \(v_{3}\) is XORed with the values in the cells (i.e., rCBF\([h_{i}(x_{3})].value=\) rCBF\([h_{i}(x_{3})].value\oplus v_{3}\) for \(i=1\), \(2\), \(3\)), and all counters in the cells are incremented by \(1\), except for counters with \(c_{max}\) (i.e., rCBF\([h_{i}(x_{3})].count=\) rCBF\([h_{i}(x_{3})].count+1\)).  
In the search operation, an rCBF returns one of three search results: _negative_, _positive_, or _indeterminable_ (INDET). For a given input in set \(U\) (i.e., \(U=S\cup S^{c}\)), if at least one counter in the \(k\) cells is \(0\) or if two or more cells among the cells with \(c=1\) have different values, a negative is returned from the rCBF. If the value fields in cells with \(c=1\) are identical, the value in the fields is returned, which implies a positive; however, positives may be false owing to hash collisions. If all counters are greater than \(1\), an INDET is returned. FP and INDET results are classified as _search failures_.  
In the rCBF, even cells with two or more elements inserted can be used to delete elements; hence, elements can be deleted efficiently, improving the deletion performance. Algorithm 1 shows the procedure for deleting an element from the rCBF. To delete element (\(x\), \(v\)) in \(S\), \(v\) is XORed with the values in the cells pointed to by the \(k\) hash functions, and all counters in the cells are decremented by \(1\), except for counters with \(0\) or \(c_{max}\). For a cell with \(c_{max}\), the counter in the cell should not be decremented to prevent an FN because the cell may have more than \(c_{max}\) elements. If the accessed \(k\) cells have counters with \(c_{max}\), the element cannot be deleted and is called an _undeletable_. However, the deletion performance of the rCBF is better than that of the FBF because the rCBF can use cells with hash collisions, except for those with \(c_{max}\).  
Figure 1: Counting Bloom filter with return values (rCBF).