# L-rCBF: Learning-Based Key-Value Data Structure for Dynamic Data Processing
###### Abstract  
Learning-based data structures, such as a learned Bloom filter and a learned functional Bloom filter (L-FBF), have recently been proposed to replace traditional structures. However, using these structures for dynamic data processing is difficult because a specific element cannot be deleted from a trained model. A counting Bloom filter with return values (rCBF) is a more efficient key-value structure than a functional Bloom filter (FBF) for repetitive insertions and deletions. In this study, we propose a learned rCBF (L-rCBF) comprising a model, a Bloom filter, and an rCBF and the deletion algorithm for the L-rCBF. To delete a specific element from the L-rCBF, two different operations are performed according to run different cases. In the experiments, the proposed L-rCBF is compared with a single rCBF and an L-FBF in terms of undeletables and search failures, and this comparison is conducted using two different models. In addition, we present a theoretical analysis of the rCBF with experimental results to demonstrate that a structure with an rCBF is more suitable for dynamic data than a structure with an FBF. key-value data structure; Bloom filter; learning-based structure; dynamic data; deep learning +
Footnote †: journal: 2023, 13, 12116. A counting Bloom filter with return values (rCBF) is a key-value data structure suitable for applications that handle dynamic data, such as the pending interest table (PIT) lookup in NDN [5]. Unlike a BF, an rCBF is an array of cells composed of multiple bits and is used for a multi-class classification task. Each cell in the rCBF consists of two fields: _counter_ and _value_. The rCBF provides the same functionalities as the FBF and supports dynamic applications better than the FBF because the rCBF uses counters. Because cells with two or more elements inserted can be used for rCBF operations, if insertions and deletions are repeated, replacing the FBF with an rCBF is appropriate. Several data structures applying machine learning have recently been proposed [20; 21; 22]. Learning-based structures can guarantee the same operations and characteristics as traditional data structures and enhance the performance of the structures. A learned Bloom filter (LBF), a learning-based data structure for a binary classification task, provides the same semantic guarantees as a BF and comprises a learned model and a BF [21; 22]. A learned FBF (L-FBF), a learning-based key-value structure for a multi-class classification task, provides the same semantic guarantees as an FBF and comprises a learned model, BF, and FBF [20]. The LBF and L-FBF can significantly improve search performance (i.e., search failure rates, including false positive rates) when using the same memory size as the BF and FBF, respectively. However, the LBF and L-FBF cannnot be used for dynamic data processing because the elements stored in the structures cannot be deleted. Hence, learning-based BF structures have the following problems. * Designing a deletion algorithm for a learning-based structure is difficult because once a model is trained, it does not provide a deletion for a specific element; hence, most existing learning-based structures cannot be used for dynamic data processing [21; 22]. * To delete specific elements, learning-based structures should utilize auxiliary structures other than the learned model. If a deletion algorithm for a learning-based structure can be designed, the application range in which the structure can be used will widen considerably. * In the case of the LBF, a deletion operation cannot be provided because the auxiliary structure is a standard BF. For the deletion operation, the standard BF should be replaced with an updatable BF variant for dynamic data. A stable learned Bloom filter (SLBF) is the first LBF variant for dynamic data and consists of a learned model and SBFs [23]. However, the SLBF can be used only for binary classification. * The L-FBF was presented for static data in [20]; hence, a deletion algorithm of the L-FBF has never been proposed.