Research map / Learning theory and algorithms / Prediction and decision losses

Ensemble Learned Bloom Filters: Two Oracles are Better than One

ICML 2025 · Learning theory and algorithms › Prediction and decision losses · approach: Active learning and subset selection

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes ensemble learned Bloom filters (ELBF, ELBF++) that combine multiple small learned oracles, each with its own or a shared backup Bloom filter, optimized via a Knapsack-based algorithm and a greedy merging algorithm to minimize FPR under a space budget.

Problem

Learned Bloom filters rely on a single learned oracle whose size is a bottleneck under limited memory, since accuracy gains from larger oracles diminish. The paper asks how to combine multiple smaller oracles with backup filters to minimize overall false positive rate under a fixed space budget.

Approach

Depart from single-oracle LBFs by orchestrating multiple small oracles, each with its own optimally sized backup Bloom filter, solving the allocation as a Knapsack problem; for correlated oracles, share backup filters among groups chosen by a greedy partition search with a random-forest estimator of joint false-positive probability.

Key results

• ELBF achieves lower FPR than BF, LBF, Ada-BF, PLBF and Fast PLBF++ across memory budgets (1,000 to 3,000 Kb) on the EMBER virus signature scan task.
• Under stringent memory budgets the canonical BF has much higher FPR than learning-augmented peers, and the gap shrinks as memory grows.
• ELBF has lower time overhead than Ada-BF and PLBF; ELBF++ is slower than ELBF due to its heuristics.

Measured effects reported in the paper

Surprising findings

• When memory is abundant, the canonical Bloom filter outperforms the learning-augmented baselines (LBF, Ada-BF, PLBF, Fast PLBF++) because oracle FPR dominates the global FPR.

Limitations

• ELBF++ relies on heuristics (greedy merging) and has no optimality guarantee.
• Experiments are limited to one main task (virus signature scan) in the body; other tasks are deferred to appendix.
• Oracles are assumed mutually independent for the main ELBF design; correlated case needs a learned estimator of joint FPR.

Experimental setup

Datasets: EMBER

Benchmarks: EMBER virus signature scan

Metrics: false positive rate time overhead (s)

Baselines: Bloom filter LBF Ada-BF PLBF Fast PLBF++

Builds on: Learned Bloom filters (Kraska et al., 2018) Sandwiched LBF (Mitzenmacher, 2018) PLBF (Vaidya et al., 2021) Ada-BF (Dai & Shrivastava, 2020) Fast PLBF++ (Sato & Matsui, 2023)

Closest papers by meaning

• LotusFilter: Fast Diverse Nearest Neighbor Search via a Learned Cutoff Table (CVPR 2025 · similarity 0.83)
• MEPSI: An MDL-Based Ensemble Pruning Approach with Structural Information (AAAI 2024 · similarity 0.83)
• Learning-Augmented Search Data Structures (ICLR 2025 · similarity 0.81)
• Free Lunch in the Forest: Functionally-Identical Pruning of Boosted Tree Ensembles (AAAI 2025 · similarity 0.81)
• A Bitter Lesson for Data Filtering (NeurIPS 2026 · similarity 0.81)
• Prediction-Powered Adaptive Shrinkage Estimation (ICML 2025 · similarity 0.81)