PL-FBF: A Partitioned Learned Functional Bloom Filter With Adaptive Memory Allocation for Key–Value Stores
IEEE Transactions on Computers · 2026-08 · 75 (8) · 3016-3030
DOI: 10.1109/tc.2026.3700857 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Computers, 2026-08. Verfasst von Yejee Lee und 2 weiteren Autor:innen. Die Arbeit nennt 27 Literaturangaben. Gefördert von: Ministry of Education and Gyeonggi-do, Republic of Korea.
Abstract (Originalsprache)
Learning-based data structures combine a learned model with auxiliary structures to efficiently handle large-scale data. By leveraging data distribution through a learned model, such structures can significantly improve search performance under limited memory. In this paper, we propose a partitioned learned functional Bloom filter (PL-FBF), which comprises a learned model and multiple partitioned functional Bloom filters (FBFs). The PL-FBF supports both membership checks and key–value retrieval, as in a single FBF, but achieves a lower search failure rate through prediction-based partitioning and adaptive memory allocation. The PL-FBF introduces a two-level partitioning strategy: inter-group partitioning based on predicted classes, and intra-group partitioning based on predicted probabilities, enabling fine-grained memory allocation tailored to data characteristics. Furthermore, unlike prior learning-based structures, the PL-FBF can be constructed without negative data, making it applicable even when negative samples are unavailable for training. We also present a theoretical analysis of the search failure probability of an FBF for skewed data and derive optimal size factors for intra-group partitions. Experiments show that the PL-FBF reduces the search failure rate compared to a single FBF under the same memory and achieves its best performance when using the theoretically optimal size factors.
Förderung
- Ministry of Education and Gyeonggi-do, Republic of Korea
Zitieren
APA
Lee, Y., Hur, Y., & Byun, H. (2026). PL-FBF: A Partitioned Learned Functional Bloom Filter With Adaptive Memory Allocation for Key–Value Stores. IEEE Transactions on Computers, 75(8), 3016-3030. https://doi.org/10.1109/tc.2026.3700857
Vancouver
Lee Y, Hur Y, Byun H. PL-FBF: A Partitioned Learned Functional Bloom Filter With Adaptive Memory Allocation for Key–Value Stores. IEEE Transactions on Computers. 2026;75(8):3016-3030. doi:10.1109/tc.2026.3700857
BibTeX
@article{Lee2026,
author = {Lee, Yejee and Hur, YeonHoo and Byun, Hayoung},
title = {PL-FBF: A Partitioned Learned Functional Bloom Filter With Adaptive Memory Allocation for Key–Value Stores},
journal = {IEEE Transactions on Computers},
year = {2026},
volume = {75},
number = {8},
pages = {3016--3030},
doi = {10.1109/tc.2026.3700857}
}
EUVIMED