提出级联学习布隆过滤器，平衡模型与过滤器大小，大幅加速拒绝查询。
Cascaded Learned Bloom Filter for Optimizing Model-Filter Size Balance and Fast Rejection
- 设计级联架构统一现有方法，用动态规划搜索最优配置。
- 相比最优基线，内存减少17%，拒绝时间降低65倍。
- 适合需要高速过滤和低内存的推荐系统、数据库场景。
近期研究显示，将机器学习与经典布隆过滤器结合的学得布隆过滤器（LBF）可实现更优的内存效率。然而仍面临两大挑战：(1) 联合优化机器学习模型与布隆过滤器的大小；(2) 系统性地最小化拒绝时间。本文提出级联学得布隆过滤器（CLBF），一种统一架构，泛化了现有LBF设计，包括夹心式LBF和分块LBF。在该框架内，我们开发了一种基于动态规划的优化器，探索离散参数空间，识别出在模型与过滤器大小间达到近似最优平衡、同时实现快速拒绝的配置。在真实数据集上的实验表明，相较于固定模型下内存效率最优的分块LBF，CLBF内存使用最多降低17%，拒绝时间最多降低65倍。代码已公开于 https://github.com/atsukisato/CascadedLBF。
原文摘要 · Abstract (English)
Recent studies have demonstrated that learned Bloom filters (LBFs), which combine machine learning with the classical Bloom filter, can achieve superior memory efficiency. However, two challenges remain: (1) jointly optimizing the sizes of the machine learning model and Bloom filters, and (2) systematically minimizing reject time. We propose the Cascaded Learned Bloom Filter (CLBF), a unified architecture that generalizes existing LBF designs, including Sandwiched LBF and Partitioned LBF. Within this framework, we develop a dynamic programming-based optimizer that explores a discretized parameter space and identifies near-optimal configurations that balance model and filter sizes while achieving fast rejection. Experiments on real-world datasets show that CLBF reduces memory usage by up to 17% and decreases reject time by up to a factor of 65 compared to Partitioned LBF, the state-of-the-art LBF in terms of memory efficiency under a fixed machine learning model. Our code is publicly available at https://github.com/atsukisato/CascadedLBF.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。