| Title |
Partitioned Learned Bloom Filter-based Structures for Dynamic Data |
| Authors |
이예지(Yejee Lee) ; 변하영(Hayoung Byun) |
| DOI |
https://doi.org/10.5573/ieie.2023.60.10.10 |
| Keywords |
Bloom filter; Data structure; Dynamic data; Learned model |
| Abstract |
A learned Bloom filter (LBF) is a learning-based structure that can replace a single standard Bloom filter (BF) with a learned model and an additional BF. A partitioned learned Bloom filter (PL-BF), a variant of the LBF, can improve search performance by partitioning the single additional BF into multiple smaller ones based on the data distribution of the learned model. However, the PL-BF does not support deletion operations. In this paper, we propose two variants of the PL-BF for dynamic data with frequent insertions and deletions: partitioned learned counting Bloom filter (PL-CBF) and partitioned learned quarternary Bloom filter (PL-QBF). The PL-CBF and PL-QBF divide the data distribution into five ranges and allocate five counting Bloom filters (CBFs) and five quarternary Bloom filters (QBFs) with different size factors to each range, respectively. Experiments show that the PL-CBF and PL-QBF effectively support data deletions and the structures are suitable for dynamic data processing. In addition, the search performance of PL-CBF and PL-QBF is improved by more than 80% compared to CBF and QBF, respectively, when using the same amount of memory. |