Cascaded Learned Bloom Filter for Optimal Model-Filter Size Balance and Fast Rejection
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915141366317056 |
|---|---|
| author | Sato, Atsuki Matsui, Yusuke |
| author_facet | Sato, Atsuki Matsui, Yusuke |
| contents | Recent studies have demonstrated that learned Bloom filters, which combine machine learning with the classical Bloom filter, can achieve superior memory efficiency. However, existing learned Bloom filters face two critical unresolved challenges: the balance between the machine learning model size and the Bloom filter size is not optimal, and the reject time cannot be minimized effectively. We propose the Cascaded Learned Bloom Filter (CLBF) to address these issues. Our dynamic programming-based optimization automatically selects configurations that achieve an optimal balance between the model and filter sizes while minimizing reject time. Experiments on real-world datasets show that CLBF reduces memory usage by up to 24% and decreases reject time by up to 14 times compared to state-of-the-art learned Bloom filters. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_03696 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Cascaded Learned Bloom Filter for Optimal Model-Filter Size Balance and Fast Rejection Sato, Atsuki Matsui, Yusuke Data Structures and Algorithms Computational Complexity Machine Learning Recent studies have demonstrated that learned Bloom filters, which combine machine learning with the classical Bloom filter, can achieve superior memory efficiency. However, existing learned Bloom filters face two critical unresolved challenges: the balance between the machine learning model size and the Bloom filter size is not optimal, and the reject time cannot be minimized effectively. We propose the Cascaded Learned Bloom Filter (CLBF) to address these issues. Our dynamic programming-based optimization automatically selects configurations that achieve an optimal balance between the model and filter sizes while minimizing reject time. Experiments on real-world datasets show that CLBF reduces memory usage by up to 24% and decreases reject time by up to 14 times compared to state-of-the-art learned Bloom filters. |
| title | Cascaded Learned Bloom Filter for Optimal Model-Filter Size Balance and Fast Rejection |
| topic | Data Structures and Algorithms Computational Complexity Machine Learning |
| url | https://arxiv.org/abs/2502.03696 |