Ensemble Learned Bloom Filters: Two Oracles are Better than One
Authors: Ming Lin
Lin CHEN
Venue: ICML 2025 poster (2025)
Keywords: Learned Bloom Filters
membership testing
learning-augmented algorithms
combinatorial optimization
Primary area: optimization

Abstract: Bloom filters (BF) are space-efficient probabilistic data structures for approximate membership testing. Boosted by the proliferation of machine learning, learned Bloom filters (LBF) were recently proposed by augmenting the canonical BFs with a learned oracle as a pre-filter, the size of which is crucial to the compactness of the overall system. In this paper, inspired by ensemble learning, we depart from the state-of-the-art single-oracle LBF structure by demonstrating that, by leveraging multiple learning oracles of smaller size and carefully optimizing the accompanied backup  filters, we can significantly boost the performance of LBF under the same space budget. 
We then design and optimize ensemble learned Bloom filters for mutually independent and correlated learning oracles respectively. We also empirically demonstrate the performance improvement of our propositions under three practical data analysis tasks.

Ensemble Learned Bloom Filters: Two Oracles are Better than One
Ming Lin 1
Lin Chen
Abstract
lookup tables (Goodrich & Mitzenmacher, 2011) etc.
Bloom filters (BF) are space-efficient probabilis- tic data structures for approximate membership testing. Boosted by the proliferation of machine learning, learned Bloom filters (LBF) were re- cently proposed by augmenting the canonical BFs with a learned oracle as a pre-filter, the size of which crucial to the compactness of the overall system. In this paper, inspired by ensemble Iearn- ing, we depart from the state-of-the-art single- oracle LBF structure by demonstrating that, by leveraging multiple learning oracles of smaller size and carefully optimizing the accompanied backup filters, we can significantly boost the per- formance of LBF under the same space budget. We then design and optimize ensemble learned Bloom filters for mutually independent and corre- lated learning oracles respectively. We also empir- ically demonstrate the performance improvement of our propositions under three practical data anal- ysis tasks.
Boosted by the proliferation of machine learning, learned Bloom filters (LBF) were recently proposed (Kraska et al., 2018; Mitzenmacher, 2018), 18), with the design rationale that we can leverage the specific structure exhibited by data items to reduce the space of BFs without sacrificing lookup accu- racy. Technically, a pre-filter is constructed by implement- ing learning model, termed as the learned oracle or simply oracle for brevity, filter the queried items. The items with negative responses at the filter are then passed to backup BF for final check. As the backup filter only needs to deal with filtered items, we can reduce its size and come up with a more compact searning-augmenter data structure, even after taking into account the space overhead brought by the oracle. Along this direction, Mitzenmacher (Mitzenmacher, 2018) proposed sandwich structure to further improve the performance. Under the condition that the score distribution of the oracle is available, several variants attempted to make the best use of the oracle to improve the overall lookup per- formance: Vaidya et al. (Vaidya et al., 2021) segmented the score space of the oracle into multiple regions by using mul- tiple thresholds, and uses separate backup Bloom filters for each region: Sato al. (Sato & Matsui, 2023) accelerated the construction while maintaining the same memory effi- ciency as Vaidya el al. (Vaidya et al., 2021); Dai et al. (Dai & Shrivastava, 2020) attributed different number of hash functions in different regions.
1. Introduction
Originally proposed by and named after Bloom in the sem- inal paper (Bloom, 1970), Bloom filters (BF) are space- efficient data structures for solving the membership lookup problem by compactly recording a given set I of data items bit array and outputting a binary answer when queried. As a structural property, the space compactness BFs is achieved at the price of limited false positives but false negative. Due to the neat structure with profound theoretic and practical implications, BFs have received significant research attention, leading to a palette of extensions and variants including Bloomier filters (Chazelle et al., 2004), counting BF (Bonomi et al., 2006), and invertible Bloom
In virtually all the state-of-the-an LBF design, the oracle has crucial impact on the performance of the system as a whole. A more accurate oracle results in smaller false positive rate (FPR). However, it has been well-demmnstratee (Thompson et al., 2021) that the accuracy of learning models exhibit diminishing performance improvement w.r.t. the model size. Therefore, the size of the learning model may become a potential bottleneck of the LBF if the overall space bud- get is limited. To quantitatively demonstrate this point, we build LBF for identifying malicious URLs from 200,000 URLs with backup BF of 500K bits. We tune the size of the oracle to vary the FPR, illustrated in Figure 1. We can observe that the size of the oracle occupies neg-iggle part of the total memory space and that the accuracy im- provement of the oracle paces down significantly with the increase of its size.
'School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou, China. 'Engineering Research Centre of Applied Technology on Machine Translation and Artificial In- telligence, Macao Polytechnic University, Macao SAR, China. Correspondence to: Lin Chen Michen@mpu.cdu.m..
Proceedings of the 4nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
The above observation resonates with the technical diffi-

---

Ensemble Learned Bloom Filters: Two Oracles are Better than One
-10-2
FPR
Oracle
Oracle 2
Oracle
Oracle
Oracle
3
150
200
2
BF
BF 4
BF
Model Size (Kb)
Figure 2. Overview of ELBF.
Figure 1. FPR of LBFs with an oracle under different sizes and BF of 500Kbits detect malicious URLs from 200,000 URLs.
works under practical data analysis tasks with real-world datasets. Our experiments demonstrate significant perfor- mance improvement of ELBFs against the state-of-the-art LBF and variants.
culty and the cost of building strong learning models in the generic machine learning context. One of the most cost-effective technique to boost the accuracy of learning models is ensemble learning (Polikar, 2012), which consists of strategically orchestrating a set of weak models usually of smaller size to form a much stronger model. Ensemble learning has demonstrated remarkable improvements va- riety of learning tasks (Gomes al., 2017; Mendes-Moreira et al., 2012; Vanerio & Casas, 2017).
2. Technical Preliminaries
In this section, we give brief introduction the standard BFs and LBFs, both of which solve the membership lookup problem, i.c., given a set I, outputting a binary answer whether a data item e belongs to I. Throughout the paper, we use calligraphic letters (e.g., X) to denote sets and bold- face letters (e.g., x) to denote vectors. Table summarizes major notations.
Inspired by the ensemble-be bueemble-based learning paradigm, we de- part from the state-of-the-art single-oracle structure of the LBF design to investigate the following research question.
Q: How to combine multiple smaller oracles to construct an ensemble learned BF (ELBF) to optimize the overall accuracy under given memory budget? More specifically, given pool of oracles, which subset of them choose and how to orchestrate them with backup filters to mini- mize the overall FPR?
2.1. Canonical Bloom Filters
BFs are space-efficient probabilistic data structures repre- senting a set I. Physically, BF contains an m-bit array B and family of independent hash functions denoted as H. {hi) Miji= where h,(e) maps an item to random bit in 0. When inserting item e, we set [[) to 1 for < i < k. To check whether an item e E I, we return true if h₂(e) = for 1 S i < k otherwise we return false.
B. Each bit of B is initialized to
In this paper, we give affirmative answer the question. We demonstrate that, by leveraging multiple learning oracles of smaller size and carefully optimizing the accompanied backup BFs, we can significantly boost the performance of the LBF under the same space budget. We technically LBF design termed
It is clear from the construction of BFs that they do not produce false negatives. However, due hash collisions. BF may wrongly return true for an item & I, causing false positive. Let n denote the number of items recorded in B, the probability that a specific bit of B is 0 is given by (1 (1-12 (1-mmm))m z e -kn/m Thus the probability of a false positive can computed as (1 -k./m)k.
achieve this by proposing semble learned BFs (ELBF), as depicted in Figure 2. We formulate the optimal design of ELBF as combinatorial optimization problem: given pool of oracles and the total space budget, the problem is to choose a subset of oracles and compute the sizes of the backup BF' so that the overall FPR minimized. We reveal the structural analogy be- tween our problem the Knapsack problem and develop Knapsack- baased approximate algorithm achieving proven (e, ooptimaally with tunable parameters and 5 trading off complexity against optimality. In the case of oracles are cor- related, we propose a generalized design, ELBF++, letting multiple correlated oracles share a common backup filter. We empirically evaluate our approaches against existing
Algebraically, the false positive rate is minimized when k equals In 2. The minimal value be computed as a m/n where 0.6185 (Broder & Mitzenmacher, 2004).
2.2. Learned Bloom Filters
LBFs exploit a learned model, termed as a learned oracle O, briefly denoted as oracle, to perform pre-filtering
2

---

Ensemble Learned Bloom Filters: Two Oracles are Better than One
Table Major notations.
Section 3: Ensemble Learned Bloom Filters with Independent Oracles
I
item set
number of items 0.6185
H
set of Hash functions
Fra
false positive rate of oracle i number of bits allocated backup BF number oracles set of chosen oracles Lagrangian function
FN,
false negative rate of oracle i of oracles
bm
O
no
L
size oracle in number of bits b./ Px.,
A
yi
(()
Lagrange multiplier
auxiliary variable total space budget number of bits scaling factors
F()
false positive rate of branch discretization stepsize of value of object discretized value of sum of 0s
Tn
A
01, O2
weight of object
discretized value wN
Section 4: Ensemble Learned Bloom Filters with Correlated Oracles
P(S)
partition of S group of oracles
([S))
set of all possible partitions of S auxiliary learned model
the learned oracle replies positively, the queried item is considered as a member of Z. Otherwise, a backup BF is then used to perform further check as standard BFs.
3.1. Design
Our ELBFs mobilize multiple learning oracles. To begin with, we assume the oracles are mutually independent, e.g., by learning mutually independent features. Each oracle backed up by backup BF, which stores the false negatives produced by the oracle. When an item is queried, the ELBF replies positively if all the oracles return positively or the oracles return negatively but their corresponding backup BFs return positively, otherwise replies negatively.
Suppose that the oracle takes Ln bits and the backup BF takes bn bits. Denote Fp and Fx as the false positive rate and false negative rate of the oracle. The backup BF only needs to hold FN n keys. Hence, the overall false positive rate for the LBF can be derived as
Fp + +1++11 F
(1)
It follows straightforwardly from its construction that our ELBFs do not have false negative, which is inline with the standard BFs. We now analyze its false positive rate. Let Fp, and FN, denote the false positive and false negative rate of oracle i. Suppose ber bits are allocated to the backup BF i. It follows that backup BF needs to hold Ex n items, with the corresponding optimal false positive rate b Fx.,, Thus, false positive rate for the branch i, i.e., the oracle i plus the backup BF is )a b//Fx, Therefore, let O denotes the of oracles used in the ELBF, which assumed be mutually independent. We create dumb oracle with size O. FPR + O and FNR 1, add it into O to include the degenerated case where adding an oracle will have negative impact on the overall performance. The overall FPR can be computed as follows:
(Mitzemmacher, 2018) also shows an estimation on what size the learning model required for an improvement for performance. Compared with a standard BF of the same to- tal space, whose false positive rate is a LLL the LBF makes an improvement in the following situations
Fp + (1 - //)a < a b+4.
which translates to the following condition on the size of
the learning model:
L < loga (Fr + (1 -Fr) bb.
II FP, (1 FP.))a/E.....
(3)
3. Ensemble Learned Bloom Filters with Independent Oracles
IEO
3.2. Optimization
This section presents design of Bloom filters augmented by ensemble learning. Inspired by ensemble learning, our key idea is to orchestrate multiple learning oracles of small size to replace the learning oracle in the LBF to obtain superior overall performance. In what follows, we first present the ELBF design and then optimization.
In this subsection, we optimize the design of ELBF by solving the following minimization problem.
Problem 1. Suppose we dispose a set O of independent oracles, from which we can choose to build our ELBF. Given total space budget T bits, the optimal design of ELBF
3

---

Ensemble Learned Bloom Filters: Two Oracles are Better than One
computes a subset of oracles A S O choose and the sizes of their backup BFs b _ (by hie so that the overall false positive rate is minimized. The problem is mathematically formalized as follows.
Noticing that b, and p() (0, 1]. we can bound c by <<c 1-Fes Fx.
Armed with the above analysis, we now proceed to consider the outer minimization problem. To this end, we define set of binary variables (ai to indicate whether we choose oracle After some straightforward algebraic operations, we rewrite the outer minimization problem as follows.
min min AgO b
II
FDa + (1 Fraj)a
iEA
subject to:
E(L, b;) S
(4)
ieA
max
Σ
In
1 CCFN.
FP
2,0 Vi
IEO
subject to
Σ Hj (L, + b,) ST
(11)
Consider the inner minimization problem for given A. De- note Y/ _ Fx, We can rewrite the inner minimization problem as below.
IEO
24 E {0, 13, Vi O.
min b
Σ In (Frs+ + +1 (1- -FP3)a))
By casting each oracle to an object with value In 1-eFx Fp.. and weight Lg +b, we observe that our problem has elegant analogy to the famous Knapsack problem, which is known to be NP-hard (Garey & Johnson, 1979). It then follows that our problem also NP-hard. However, being weakly NP-hard, the Knapsack problem with integer weights can be solved by dynamic programming in pseudo-polynomial time. Suppose we can invoke an oracle, termed as KNAP- SACK, that solves the canonical Knapsack problem with integer weights and values. We next develop a Knapsack- based algorithm augmented by the scaling technique find an (e, 8) opptimll solution of our problem, as formalized below. The rationale behind is to allow a small quantity of overflow the space budget to achieve near-optimal FPR.
iEA
subject to
Σ (Li y:FN,)) ST
(5)
EEA
y1 2 0, A.
Using augmented Lagrangian approach, we write the fol- lowing Lagrangian function for optimization:
L(v,, U2...., Yn, A)= = ΣEn In Frs +
+1 (1- -Fr,)an
iEA
-
Σ SEA
+ - -T )
(6)
Definition 3.1. The configuration of an ELBF is called (c, -ooptiall if its FPR is within to the optimal and its space is upper-bounded by (1 + 8)T.
where À S is the Lagrange multiplier. The partial deriva- tives with respect to y, and A can be derived as below.
dc (1- "k Ina
FNNAA
θy: Fp, + (1 - PR.))a
Algorithm ELBF optimization
OC
-T
-Eh
Input: oracles set O, space budget T, scaling factors 01, 02. stepsize
iEA
Output: selected oracle set A, backup BF setting b
We observe that the partial derivative for yi equals 0 when
Initialization: 0- + 1- 1-FP.s do
A4 + 0, c 0
(1 F
X
while S max 1E0 FN.
an c, A.
(8)
FP.s + (1- - Fp.) )
3: ct A
4: for each j E do
In the above equation, we define an auxiliary variable e, which serves as pivot in our analysis. Armed with e, we can derive the optimal by for branch as follows.
5:
ig max
0, 01 .nn 1-oFM.
}
Fe.
6:
i f 00 [L, + FNJ loga (I-CFx,)l-Fo))
cFN.
end for
FFN,FFs
b F log, (1 CF-CFN.)(C FP.))
99
(b, KNAPSACK(O, v, w, (O2TT)
if 6* then
from which we further get the minimal false positive rate for branch denoted by F(), as
10:
0* +- A" +
11:
6 + FN.s loga (I-eFx,)(1- (FFF) Vi ViE E A
oFw.Fes
12: end if
Fps
F Fry + (1 - Fr. ///x.
(10)
13: end while
1- C-FNN

---

Ensemble Learned Bloom Filters: Two Oracles are Better than One
The pseudo-code of our algorithm is given in Algorithm The core part of our algorithm is the while loop, in which we scan with stepsize A. For each discretized value of i.e., iA, we scale the values Uj and the weights wy for each oracle j E O. We then invoke the Knapsack algorithm by regarding each oracle as an object with the total weight constraint scaled up to 02T. Our algorithm returns the op- timal Knapsack solution among all discretized c, which is also an (c, oooptimll ELBF configuration, as presented in Theorem 3.2 and proved in Appendix A.
Oracle
Oracle
Oracke
Oracile
Oracle 5
BF
BF 3
Theorem 3.2. Under the condition 01 2 no and 02 2 not11 Algorithm/ I oulpuds an (e, -optimal ELBF configuration.
Figure 3. Overview of ELBF++.
We conclude this section by analyzing the time complex- ity of our algorithm. The complexity to calculate the val- ues and weights and solve a specific Knapsack problem is O(no + no [02T]] = (6) As the above operations are performed for each discretized value c, the overall (5(1-Fra) time complexity sums up O (maxjeo Fv,220 ...e.. asymptotically ((n)/(62)
O of oracles, some of which are correlated. Let S denote subset of O and P(S) denote partition of S. For each element of g E P(S) representing subset of oracles, we consider them sharing the same backup filter, thereby forming a branch. We define Fr.g and FN.g as the FPR and FNR of branch g. respectively. Assuming bn bits are allocated the backup filter, the FPR of branch g, denoted by F(9), given by
4. Ensemble Learned Bloom Filters with Correlated Oracles
Fl9) FP + (L-FPg)a"//NN)
(12)
In the previous section, the assumption of mutually indepen- dent oracles was made. Nevertheless, in real-world scenar- ios, oracles frequently exhibit correlations. In this section, we address this correlated case by devising generalized version of ELBF called ELBF++
For given partition P(S) consisting of m branches, denote (,())S), concisely denoted by X₁ when the context is clear, as the event that branch i returns false positively. The overall FPR is then Pr(N X2). Define
The design rationale of ELBF++ lies in allowing multiple correlated oracles to share a common backup filter, as il- lustrated in Figure 3. This is achieved through carefully selecting subset of oracles and optimizing the correspond- ing backup filter parameters. Specifically, ELBF++ operates as follows: Each backup filter stores the false negatives of all the selected oracles connected to it. When an item is queried, ELBF++ returns a positive response if all the selected oracles give positive results or, if some of them re- turn negatively, but their corresponding backup filters return positively. Otherwise, ELBF++ returns negative response.
T(P(S), b)
Pr X.)
Pr(X,)
We can express Pr ( (0 X,)
m
Pr
0 Xx I(P(S), b) II Pr(X.)
=I(P(S), b)
II gEP(S)
FP. + (1 (LFFP: FP.g)aa"/FN..
(13)
Before delving into the design of ELBF++, note that ELBF can be regarded as degenerated version of ELBF++ As proved in Appendix, when oracles are mutually indepen- dent, attributing a separate backup filter to each oracle leads to strictly lower FPR than letting multiple oracles sharing common backup filter, which justifies the ELBF design. However, when oracles are correlated, the situation is more complex such that sharing common backup filter among correlated oracles helps reduce FPR.
We can observe that computing the optimal value of Pr ( (n X2) requires evaluating (P)) b) for each par- tition P(S) and each possible size configuration of the backup filters b, whose complexity is super-exponential.
To reduce the above complexity, we adopt a learning- based approach. Specifically, we randomly sample subset of par- titions and configurations and then train an auxiliary learned model that, given any partition P(S) and any size con- figuration of the backup filters b. estimates Pr (N. Xi). Existing works have demonstrated the feasibility of learning effective models with small sample size (Loo et al., 2019; Lu et al., 2023; Sendera et al., 2021). In our work, we
The central research problem in the design of ELBF++ is to choose the appropriate set of correlated oracles for each backup filter. To formalize the problem, suppose we dispose
5

---

Ensemble Learned Bloom Filters: Two Oracles are Better than One
leverage the random forest model to learn ((P(S), b). The details of our training algorithm are given in Appendix C.
0g/Ina. We can derive the optimal by as
(c FN FP
Suppose our random forest model for learning ((P(S). b) takes Un bits. Let II(S) denote the set of all possible par- titions of S. We can formulate the problem of optimal ELBE++ design as follows.
6/g - FN.. loga (1 (1- (c (c) PN (1 Fpa)
(19)
Here, by can be solved iteratively. Specifically, we define an auxiliary variable
min min min SCO ((S) I(P(S),)) b) II (F - FP.)a FM)))
Ug - (t)
(c $ pg(()) FN, F.g
FN.g loga
(1 (1- (c (-- (t)) FN.s (1 Fr.s)
sEP(S)
subject to: U +
Σ
(Lg + b,) ST
where t denotes the corresponding iteration index. We em- ploy the secant method (Barnes, 1965) update by()) as follows:
gEP(S)
b 2 0, Vg E P(S)
(14)
Ug (t) by (t+1) = (t) Ug (t(t)= Ug (t (bg(t) - by - 1))
Considering the inner minimization problem for a given P(S), we can rewrite it as follows:
min InI(P(S),b) b) + Σ In (FF. + (1 F
Noticing that the derivative of u (t) is non-zero in the vicin- ity of by. and assuming that (P)(S), b) is continuous and differentiable, we can prove that b(() converges to by. armed with which we can derive the overall FPR, denoted by F(S) as follows:
gEP(S)
s. t: U + Σ
(Lg + bg)) T
(EP(S)
b 2 0, E(S))
(15)
F(5) ((P(()),b))
II DEP(S)
P
By introducing a multiplier X S O, we can write the aug-
(20)
mented Lagrangian
FP.
= =((((S),b') SEP(S)
II
1- (c - Fi)
[(b, A) = In(())))
Σ In (FP.
gEP(S)
By searching in (0, mingerrs))11 Fp.g)/ FN and find- ing the minimal corresponding overall FPR, we can solve the inner optimization problem. The detailed pseudo-code is given in Algorithm 3 of Appendix D.
+(1 +(1 (1-FFPgga////xii
Σ OEP(S)
E(,t (Lg by) T -
(16)
Next, we turn to solve the outer optimization problem by de- veloping greedy merging algorithm, described follows:
Denote 0y e ((PT)P b)/bhb. The partial derivatives of L w.r.t. by and can be derived as
Initialization. We set P as an empty set.
Augmenting P. We iteratively augment P using the following three strategies:
2C
(1- Fp.g)a FN. In 0, + FN (Fr + (1 Fr.g)aos/
0b,
Creating new branch: We pick an oracle not yet selected and create new branch.
=T - U Σ (Lg + by)
0x
Augmenting existing branch: We pick an oracle not yet selected and merge with one of existing branches in P.
SEP(S)
(17)
By imposing OC/0b, O, we obtain
Merging two existing branches: We pick two branches in P and merge them.
(1- F/
X
dg
For each of the above augmentation strategy, invoke algorithm to solve the inner optimization problem under the augmented partition P. We stop the augmentation when the overall FPR cannot be further improved. At this point, we output the final partition and the corresponding backup filter size to set the ELBF+++ parameters.
FN. Fryg + (1 - Fr
In
In
A c
Bg Vg E P(S). (18)
In the above equation, we define an auxiliary variable c as in the analysis of the previous section, and denote T A
6

---

Ensemble Learned Bloom Filters: Two Oracles are Better than One
We conclude this section by analyzing the time complexity of the greedy algorithm. Given the error bound 6s on finding bg. the number of iterations to execute the secant-based up- date O (loge (log (1/c))). where { = (1 + /2 (Diez, 2003). Hence, for a given P. the complexity of finding the minimal overall FPR among all discretized values of is O ((loge (log (1/e,))) / Given that the inner opti- mization procedure is invoked for each augmentation of the partition P. and considering that the augmentation steps may be executed up to no times, the overall time complexity sums up to (ni (logę (log (1/ea))) /A).
ignore the unlabeled files. The 2381 features of the files are included in the dataset, from which we randomly select 238 features. The features are exclusive for mutually inde- pendent case and somewhat duplicate for correlated case. Following the literature, we choose the random forest clas- sifier from sklearn (Pedregosa et al., 201 I) as oracles. We construct pool of oracles with a large oracle and a set of small oracles. The large oracle consists 10 decision trees and at most 20 leaf nodes for each tree; the oracle size is 262Kb. Each small oracle is single decision tree with at most 20 leaf nodes; the oracle size is 32Kb. We randomly sample 30% data for oracle training. The large oracle learns from all 238 features while each small oracle learns from 23 or 24 features selected randomly.
5. Extensions and Variants
In this section, we discuss several pertinent extensions and variants of our ELBF to demonstrate that our design is suffi- ciently generic to be applied in a large spectrum of data pro- cessing tasks: (1) We formulate and optimize sandwiched ELBF which is incorporated with initial filters prior to or- acles; (2) We consider an enhanced scenario where each oracle can be optimized as well; (3) We propose Ensemble Learned Bloomier Filter, which is inspired by Bloomier filters (Chazelle et al., 2004), a variant of BF, to solve key- value lookup. The details is presented in the Appendix.
6.2. Experiment Results
We compare ELBFs against major state-of-the-a arr proposi- tions, i.e., the canonical BF (Bloom, 1970), LBF (Kraska et al., 2018), Ada-BF (Dai & Shrivastava, 2020), PLBF (Vaidya al., 2021) and Fast PLBF+ (Sato & Mat- sui, 2023). As we have pool of oracles, we let LBF, Ada- BF, PLBF and Fast PLBF++ operate on the oracle achieving the lowest FPR. To put Ada-BF, PLBF and Fast PLBF++ along the same line of comparison with ELBF, we let Ada- BF, PLBF and Fast PLBF++ operate on two regions rep- resenting positive and negative responses from the oracle and optimize the corresponding backup BFs. Ada-BF exe- cutes under its aaper-parameter
6. Experiments
We perform empirical experiments evaluate the proposed designs. We conduct our experiments on three practical data analysis tasks: (1) virus signature scan, (2) malicious URLs detection, (3) universally unique identifier check. Due to space limit, we present the first task and defer the rest two to Appendix, which demonstrate similar results and thus lead to similar observations and conclusions. We also give more detailed evaluation of Algorithm 1 under different parameters using synthetic data. A aberration study pre- sented in Appendix compares Algorithm 1 against simpler approaches, highlighting the advantage of our proposition. Our experiments are conducted on a standard off-the-shelf desktop computer with an (Rt Core 17-12700F CPU @2.10 GHz and 16 GB RAM.
1 3 with 40 intervals and PLBB and Fast PLBF++ execute under its number of intervals N = 100. ELBF chooses the oracles by running Algorithm under the parameter setting A = 0.1, e = 0.01, = 0.01. We straightforwardly set theta 01 = [ and
02 = nattd T'8 1, which satisfies the condition in Theorem 3.2.
+LBF++ operates the greedy merging algorithm under the parameter setting A = 0.1, 6 0.01.
6.2.1. MEMORY BUDGET AND FPR
We first compare the central performance metric, FPR, of the evaluated solutions in Figure 4(a) and Figure 4(c) under dif- ferent memory budget. We make the following observations from the results. (I) Under stringent memory budget, the canonical BF has much higher FPR compared to its learning- augmented peers. This performance gap shrinks with the increase of the memory budget to the extent that, with abun- dant memory space, there no advantage to augment the BF with oracles. This can be explained as follows. The FPR of the canonical BF decreases exponentially in the memory al- located to it. In the LBF, Ada-LBF, PLBF and Fast PLBF++, the FPR depends not only on the size of the backup BF, but also on the FPR of the oracles. When the memory budget is not stringent, the FPR of the oracles dominates the global FPR, leading to the result that the canonical BF outperforms its
6.1. Experiment Setting
BFs are extensively utilized in virus signature scanning task, involving the verification of whether a suspect file's sig- nature exists in the virus signature database when the file is presented. In our experiments, we apply the proposed ELBFs to execute the task of virus signature scan and com- pare them against the state-of-tt ofte-of-theearr the solutions.
We use a real-world dataset EMBER (Anderson & Roth, 2018), an open-source collection of IM sha256 file hashes. There are 400K malicious, 400K benign and 200K unla- beled files, which were scanned by VitusTotal in 2018. We
peers, except our solution ELBFs,
7

---

Ensemble Learned Bloom Filters: Two Oracles are Better than One
Adi-RF ELOF
LAF
AdaRF
PLBF
Fast PLBP++
PLBF
Fast PLBF++
ELBF++
Palse Positve Roie
11.3
Time Overhead (s)
Palse Rositier Rate
0.3
Overhead
0.2
11.1
1,000
2,000
5,000
1,000
2,000
5,000
Memory Budget (Kb)
Memory Budget (Kb)
Figure Performance comparison: mutually independent case (left), correlated case (right).
Fulse Posilve Rate
0.1
0.5
Palse Positive Rote
0.1
0.005
Palse Faise Posiive Kate
0.1
0.08
0.1
0.011
A 0.01
0.001
5-10-2
5-10-2
5-10-2
2,500
2,500
Memory Budget (Kbb
Memory Budget
Memory Budget (Kb)
(a) Varying A, 0001 5=0.01
(b) Varying 1=0.1, 6=0.01
(c) Varying 6, A=0.1, e00.1
Figure 5. Performance of Algorithm under different parameter settings.
as integrating multiple different oracles eliminate the dimin- ishing effect of single oracle and we have included dumb oracle allowing to cover the where adding oracle has negative impact on the final FPR; (2) ELBFs outperform the other solutions for all the memory budget, confirming our finding that orchestrating multiple small oracles instead of relying on a single large oracle holistically can effectively reduce the FPR. The performance gain is more pronounced with large memory budget because this allows more space to optimize the orchestration of different oracles, leading to better performance. (3) The performance of Ada-BF, PLBF, and Fast PLBF++ is unrelated to the correlation of oracles, as they only use single oracle. ELBF performs better than ELBF+ in their respective situations, as ELBF achieves guaranteed optimality while ELBF++ relies on heuristies.
ELBF, because both of them require multiple-dimensoone search for the parameters, outweighing the Knapsack-basee search in ELBF. Though Fast PLBF+ diminishes the con- struction time of PLBF, its time overhead remains higher than that of ELBF. ELBF++ is more time-consuming than ELBF due to the heuristics.
6.2.3. ABLATION STUDY W.R.T. ALGORITHM
We conclude our experiment analysis by evaluating Algo- rithm under different parameter settings regarding c, and 8. The results, depicted in Figure 5, lead to the following observations. The FPR increases in A and demonstrating the trade-off between the optimality and complexity of our algorithm. Our experiments indicate that setting A to 0.1 seems sufficient to achieve near-optimal FPR. On the other hand, the FPR decreases in 6, as larger indicates larger memory budget and hence better performance. The impact of 5 decreases the memory budget increases, to the ex- tent that, when the memory budget reaches 3000 Kb, d has virtually no impact on the FPR.
6.2.2. TIME OVERHEAD
We then compare the time overhead of different solutions, by time overhead we mean the time to compute the op- timal configuration of the entire data structure including the backup filter size, the oracles to use, etc, excluding the times to train models and insert all the items into the BF and backup BFs. In our experiments, we report that the time overhead for BF and LBF negligible and hence have not included them in the figure. This is because BF does not need choose any oracle and LBF chooses the best oracle with minimal overall FPR, both with almost no computation overhead. Therefore, we concentrate on the comparison among ELBFs, Ada-BF, PLBF and Fast PLBF++, as de- picted in Figure 4(b) and Figure 4(d). We observe that both Ada-BF and PLBF incur significantly higher overhead than
7. Conclusion
In this paper, we have presented a new design of LBFs based ensemble learning, termed as ELBFs. We demonstrate that by orchestrating multiple oracles of smaller size, the ELBFs outperform the existing LBFs. The main technicality to build the optimal ELBFs in our designs is Knapsack- based algorithm solving a combinatorial optimization prob- lem for mutually independent learning oracles and greedy approach solving a more complex combinatorial optimiza-
8

---

Ensemble Learned Bloom Filters: Two Oracles are Better than One
tion problem for correlated learning oracles. The empirical experiments in real-world datasets demonstrate the perfor- mance gain of our approaches.
Garey, M. R. and Johnson, D. S. Computers and intractabil-
ity, volume 174. Freeman San Francisco, 1979.
Gomes, H. M., Barddal, P., Enembreck, F,, and Bifet, A. A
survey ensemble learning for data stream classification.
Acknowledgements
ACM Computing Surveys, 50(2):1-36, 2017.
This work is supported in part by National Science Foun- dation of China under Grant 62172455, Pearl River Tal- ent Program under Grant 2019Q X140000X100, and Guangdong Provincial Key Laboratory of Information Security Technol- ogy (No. 2023B 121 21660662).. Part of the work of Lin Chen is done when he was with School of Computer Science and Engineering, Sun Yat-sen University.
Goodrich, M. T. and Mitzenmacher, M. Invertible bloom lookup tables. In Proc. Allerton Conference, pp. 792-799, 2011.
Kraska, T., Beutel, A., Chi, E. H., Dean, J., and Polyzotis. N. The case for learned index structures. In Proc. SIGMOD, pp. 489-504, 2018.
Loo, Y., Lim, S. K., Roig, G., and Cheung, N.-M. Few-shot regression via learned basis functions. In Proc. ICLR, 2019.
Impact Statement
This paper presents work whose goal is advance the field of Machine Learning. There are number of potential societal consequences of our work, none which we feel must be specifically highlighted here.
Lu, J., Gong, P., Ye, J., Zhang, J., and Zhang, C. survey on machine learning from few samples. Pattern Recognition, 139:109480, 2023.
Mendes-Moreira, J., Soares, C.,, Jorge, A. M., and Sousa, J. F. D. Ensemble approaches for regression: A survey, ACM Computing Surveys, 45(1):1-40, 2012.
References
Anderson, H. S. and Roth, P. EMBER: an open dataset for training static PE malware machine learning models. arXiv preprint arXiv: 1rXiv:1804. 0003,0467, 21003,22011 2018.
Mitzenmacher, M. A model for learned Bloom filters and optimizing by sandwiching. Advances in Neural Informa- tion Processing Systems, 31, 2018.
Barnes, J. G. P. An algorithm for solving non-linear equa- tions based on the secant method. The Computer Journal, 8(1):66-72, 1965.
Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., al. Scikit-leam: Machine learn- ing in python. Journal of Machine Learning Research, 12:2825-288 2830, 2011.
Bloom, B. H. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7): 422-426, 1970.
Polikar, R. Ensemble learning. Ensemble machine learning: Methods and applications, pp. 1-34, 2012.
Bonomi, F., Mitzenmacher, M., Panigrahy, R., Singh, S., and Varghese, G. An improved construction for counting Bloom filters. In Proc. ESA, pp. 684-695, 2006.
Sato, A. and Matsui, Y. Fast partitioned learned bloom filter. In Proc. NeurIPS, 2023.
Broder, A. and Mitzenmacher, M. Network applications of bloom filters: A survey. Internet Mathematics, 1(4): 485-509, 2004.
Sendera, M., Tabor, J., Nowak, A., Bedychaj, A., Patacchi- ola, M., Trzcinski, T., Spurek, P., and Zieba, M. Non- gaussian gaussian processes for few-shot regression. Ad- vances in Neural Information Processing Systems, 34: 10285-10298, 2021.
Chazelle, B., Kilian, J., Rubinfeld, R., and Tal, A. The bloomier filter: an efficient data structure for static sup- port lookup tables. In Proc. SODA, pp. 30-39, 2004.
Thompson. N. C., Greenewald, K., Lee, K., and Manso, F. Deep learning's 's diminishing returns: The cost of improvement becoming unsustainable. IEEE Spectrum, 58(10)50-55, 2021.
Dai, Z. and Shrivastava, A. Adaptive learned Bloom fil- (Ada-BF): Efficient utilization of the classifier with application to real-time information filtering the web. Advances in Neural Information Processing Systems, 33: 11700-11710, 2020.
Vaidya, K., Knorr, E., Mitzenmacher, M., and Kraska, T. Partitioned learned bloom filters. In Proc. ICLR, 2021.
Vanerio, J. and Casas, P. Ensemble-learinn approaches for network security and anomaly detection. Proc. Workshop on Big Data Analytics and Machine Learning for Data Communication Networks, pp. 1-6, 2017.
Díez, P. A note on the convergence of the secant method for simple and multiple roots. Applied mathematics letters, 16(8):1211 1211-1 2003.

---

Ensemble Learned Bloom Filters: Two Oracles are Better than One
A. Proof of Theorem 3.2
Proof. Let (A*,b") and (AOPT, bOPT) denote the output of Algorithm and the optimal solution of PT, respectively, Let c* and COPT denote the associated values of correspondingly.
We consider the discretized Knapsack formulation of P denoted by P, in which v and w computed using scaling factors 0 and 02 as shown in Algorithm 1. Recall the scaling of W we can check that (AOPI, b') is feasible solution of P. where b' is as follows
C FN..PR.
8/ = =Fv, loga (1 -0PPT
CPT FN.FPF
FN, loga
(1 (1- (1 (1
where COPT
OPT A
A COOT OPT
Hence, we have
1 - c' F'F
1 1 COTT ENd
FND
01 In
2
01 In
Fpá
Fp.
iEA
iEA
1 COPT FNA
Σ
In
Fr.s
EE
The second inequality follows from 2PPT SPP It then follows that
1 FN.
1 OPT FNA
Σ
1+0,
Σ
0,
Fraa
Fr.
EEA
Let no denote the number of oracles. We have
Σ iE
In
1 1- C
In
OPT
FN:
110
Fri
FP
01
SEAA
Recall that the false positive rates corresponding to (A",b") and (AOPT, (OPT)) are Il I-e" and
Fr.
Fp. Il. I-coPY respectively. With some straightforward algebraic operations, we prove that, under the con-
dition 01 2 na/c, it holds that
Fpá c FN.
FPi OPT FNL
II BESA
(1++))
II $ESA
We have now proved the false positive rate of the solution output by our algorithm is within e to the optimal solution. We then prove that the total space of our solution upper- bound-b by (1 8YT.
follows from our algorithm that
Σ 10 (L: + +,) S [02T *EA4
Therefore, have
Σ Bg b,) no - 0.T 1.
The space overhead of our algorithm can then be bounded as follows.
Σ (1++b)
+
62
SE
Therefore, if 00 2 to To
the total space of our solution is upper-bounder by (1 + 8)T.
10

---

Ensemble Learned Bloom Filters: Two Oracles are Better than One
B. Optimality of ELBF with Non-correlated Oracles
Theorem B.1. Given any set of independent oracles and any space budget, allocating separate backup filter for each oracle leads to strictly lower FPR than letting multiple oracles sharing common backup filter.
We consider the oracles are divided into a set 9 of ng _ [g] groups, with the oracles belonging the same group sharing a single backup filter, i.c., the filter of group g & stores the false negatives of all the oracles in this group.
We now derive the FPR by first deriving the FPR of each group and then deriving the overall FPR. For each group g E G, once at least one of the oracles in the group returns negatively, the backup filter will store the corresponding item. Hence, the FNR of group y oracles whole, denoted by p(a) can be computed
( N
=1 - II (1- -1.N,),, IEO,
(21)
where Og denotes the set of oracles in group g. The number of keys the backup filter of group g needs to hold F(2) n. To derive the FPR for group first give the FPR for the oracles in the group, denoted by F(9) as follows.
F
II FPS iEO,
(22)
We then can derive the FPR for the whole branch including the backup filter as
F + (1 - )a )a /
600)
Since the groups are independent each other, we can conclude the FPR for this group-based design as
II geg
( +1 F(s) )a bl0) (
(23)
We next prove that for any configuration of this group-based design, there always exists corresponding ELBF configuration achieving lower FPR with the same space budget.
Suppose we have in total n oracles, with FP,, and FN,, denoting the FPR and the FNR of oracle and Lg denoting its size. The space budget is T. We start from the case n 2. The FPR the group containing both oracles can be computed as
Fg Fr. (1 FP2) (/ F Fx.a),
where - T T1 L2. The FPR of the corresponding ELBB F1 F2 that given by
(FP] + (1 / (Fr2 + (1 22Fx2)
where b, + b2 = b.
Now, we need to prove Fi F2 < Fg. Imposing Fv. FN. be rewrite below.
by
b2_ yields bi = "yaifNaa b2
FN.
Fw.ab
The inequality can
PN.
(FP) (1 FP.)) FM.1FFx))) (FP2 (1 FP (M. FP1FP.2 + F1.1P...Pll Fx.t FN, FN,
+ *Fr. + Fp2 - 1822-Fpp1 F FN.1 FN. + (1 Fp.1((1 - FD2) PM.IFNN < <1 Fr. Fr Px.1 PN.I
+ (FP11 + + -2FP.
+ +(1 FP1)(1 - FP2)a
2(1- PNIT
< 1 FP1
PNI "N
Since 1
Ex,1Ex.2 E (0,1), we have PN.++NN2
< 1. The LHS of the above inequality is strictly smaller than
Fra + Fr.2 2F Fr.)(1 Fr2) Fr.1 Fr

---

Ensemble Learned Bloom Filters: Two Oracles are Better than One
The inequality is thus proven. We carry the proof by mathematical induction.
Suppose n k. 3b, where by = Ex=1 Lis s.t. IT F, Fo..
For k: 1, the false positive rate of group Gk+1 is
k+1
F
II Fp
II
FPS FP Fp... FPR+1
(24)
2m
and the false negative rate of that is
k+1
EN = =1
II (1 FN.))
1=1
=1 1 (1 II (N.))) (1 FN
(25)
=1 (1 (w FN
FN..u + FN,,+1 FN.G, FN
from which we can write the FPR of groups consisting oracles as
Fr.g. Fr + Fr,9, Fr Fx.0, Fx
FN.o. FN,4+1
(26)
That is, the ahead oracles that compose the group can be treated an alternative oracle. We need to prove there exists an allocation of BFs for multiple oracles which behaves better than the group case.
Recall T Σ L. Imposing Fx.0z
FN.KI Fv.o. +xx Taking the assumption for k. know that there exists allocation for BFs for the ahead oracles under budget bg, satisfies the following inequality.
bog be+1 FN.A-I yields bg, Fv.9, FN,441 bx+1
Fx.c.
1+1
II 2=1
F.
II F. Fo+1 < Fgg Fx+1
FPP. + (1- (1-FPal Fp
bor /Fme))))))))))))) (FRA+I + (1- FP,441)a be- ////attt)))
(27)
(FPS. + (1- FP.g. "N.,, (xen-(x)t))) (FP,441 (1- Fp,+tiaa +
This inequality is smaller than (26) by similar analysis for the case n 2. Then, we have FGg, Fk+1 < Fe which leads
to
A+1
II 1=1
& < FG
Thus, given mutually independent oracles, for any configuration of the group-based design, there always exists correspond- ing ELBF configuration achieving lower FPR with the same space budget.
C. Algorithm 2: Training Auxiliary Learned Model
D. Algorithm 3: Inner Optimization of ELBF++
E. Algorithm 4: Greedy Merging Algorithm for Outer Optimization of ELBE++
The pseudo-code of our greedy merging algorithm for the outer optimization of ELBF+ is given in Algorithm 4. Our three augmentation strategies correspond to three for loops, respectively. The procedure INNER defined Algorithm solves the inner optimization problem. For conciseness, an internal procedure UPDATE updates the current optimal configuration.
12

---

Ensemble Learned Bloom Filters: Two Oracles are Better than One
Algorithm 2 Training auxiliary learned model
Input: oracles set O, space budget T, data scaler M
Output: auxiliary model r Initialization:
2: while 1 Si S M do
3:
j
1
4: while 1 و - no do
5: 8 + (andom/nllij.n
6:
Randomly divide O into a partition P(O) containing & groups
7:
P(S)= + Randomly select subset containing j groups P(O)
8:
t (b1, b2. bnn)) +-
9:
Randomly allocate T to by, b2,
Pr(X1, 12, X2,..., . .x,)
10:
R
IPP Pr(X.)
11: X 4 Extract features from P(S)
Add ((x, b) R) dataset
13: end while
14:
end while
15: I x Train Random Forest on dataset
Algorithm 3 Inner Optimization of ELBF++
1: procedure INNER partition P, stepsize A, space budget T, auxiliary model T, iteration threshold N)
2: Ff 1,c + 0, U size of r
- FP.s do
3: while 0 s min gEP(S)
FN.g
4: c+ A
5:
for g E do
6: Initialize b randomly
7: Compute (0), Vg P
8:
t
9:
while convergence not reached and < N do
(c g (t)) FN. Fr.g
(t) (t) FN.g loga
(1 - (e (1)) FN.g) - Fr.g)
11:
if > 0 then
ug(t)
12:
by(l (| + h1(() ug ug (t 1) (b)(1) - ly(1 1))
13:
end if
14:
+- +++1
end while
b9 - (t), 45 + (t)
17:
end for
Fr.g
F - [(P.b") II
Σ by
18:
w &
(c 03 FN.g
9EP
9CP
if F(P < F and < T U then
19:
F (P)) t (P)
20:
21:
end
22:
end while
return b* F(P)- (
end procedure
13

---

Ensemble Learned Bloom Filters: Two Oracles are Better than One
Algorithm 4 Greedy Merging Algorithm for Outer Optimization of ELBF+
Require: Oracles set O, space budget 7, stepsize A, iteration threshold N Ensure: Optimal partition pd and corresponding b*
1: Initialization: PP + 1, +-
2: procedure UPDATE(P new, nee P
3: pa f- Prew
4: b' bnew
5: Fp- 4- PPw
6: return True, p' Fp
7: end procedure
8: while True do
9: imp e False
10: for each oracle o not in P do
Pnew PU {o}
by Dnows Fr. P.
INNER (PNER new A, N)
13:
if Fr P.new < Fp then
14:
(imp, ,=, Fp) t UPDATE(P new b Fp. P.new)
15:
end if
16:
end for
17:
for each branch g E P do
for each oracle not in do
P Pnew~ & {g) U {g (b" Deew: Fi.ew f- INNER (PNER. new, A,T,I,N)
20:
21:
if Fx Pnew < Fp then (imp, "p,"", F,) UPDATE(P new biews F.P. PPPn
22:
23:
end end for
24:
end for
for each pair of branches (g1, 92) E P do
27:
Poew < P f91.99 92) {91 92
28:
(brcw: Fr.nww) + INNER (P new: A N)
29:
if FP. P.aew < Fp then
30:
(imp, P= b.. FP) + UPDATE(P new, b
31:
end if
32:
end for
33:
if not imp then
34:
Break
35:
end if
36:
P +-*7 P'
37:
end while
38: return Pr, ,", Fp
14

---

Ensemble Learned Bloom Filters: Two Oracles are Better than One
F. Details of Extensions and Variants
F.. Optimizing Learned Oracles
Referring to Problem 1, we consider an enhanced scenario where each oracle possesses variable size and performance characteristics. For instance, decision tree oracle might incorporate additional leaf nodes reduce its false positives and false negatives, albeit the expense of increased memory consumption. In this context, the objective is to select optimal configuration for each oracle such that the resultant ELBF achieves the minimal FPR.
Assume that each oracle E O has a set J, of potential configurations. Each configuration j E Ti is associated with specific parameters: Lij denotes the memory size, Fp. represents the false positive rate, and FN.,j represents the false negative rate the oracle under configuration j. The challenge is to determine the most appropriate configuration for each oracle to optimize the overall FPR of the ELBF.
Problem has evolved in complexity, now encompassing the optimization of individual configurations for each oracle i within the chosen subset A. Reflecting on Algorithm it is capable of addressing this intricate optimization challenge. Given that the values of Fp,, and FN.: fluctuate with the configuration j E T. oracle i, the variables bş in (9) and F in (10) redefined bi, and F respectively.
In the context of the Knapsack Problem formulation (11), each oracle's 's value now ranges over the set {In o.. |j E J.). Fr.s and its weight is recalculated over the set (Ii + bī E J.). This reformulation suggests that the problem can be cast Grouped Knapsack Problem, a derivative of the classic Knapsack Problem, solvable pseudo-polynomias time via dynamic programming. In this framework, each oracle is no longer single object but group of objects, with each object corresponding to specific configuration. We aim to select at most one object from each group to maximize the value of the objective function.
Within the for loop of Algorithm 1, we iterate over each configuration j of oracle i, refining the KNAPSACK oracle to address the Grouped Knapsack Problem and thus arriving at the optimal solution for the optimization problem. The time complexity of the adapted algorithm is asymptotically (ng)/(6A)) where I denotes the number of configurations accessible per oracle.
F.2. Sandwiched Ensemble Learned Bloom Filters
In sandwiched ELBF, we allocate BF before each oracle to filter data items before injecting them into the oracle. Suppose allocate p,n bits for each pre-filter i, whose FPR is then aP,, compute the overall FPR follows:
II IEO
a. (Fr. - (1 FP::)a(-DD/FN
(28)
Thus, the sandwiched ELBF can be optimized by solving the following minimization problem.
II II a: (FPs + (1- FFF))) (k:))// -n)/FN.)
min min ACO b.p
SEA
subject to:
(L. bb) <T
(29)
iEA 6,2p 2 Vi A.
For each branch i, we compute the derivatives with respect to as below:
Fr In - (1 -1 Fp.)) (1-Fp,) FN.
b/ 1)a b, FFx,
(1 PN. lps In
(30)
The above derivative equals 0 when
Fr.
Pi = b, FNN loga
(31)
(1 F1,:)(1 FN,))'
15

---

Ensemble Learned Bloom Filters: Two Oracles are Better than One
where we require Fp, + FN 1 to ensure Ps that the backup BF is not empty.
Thus, the minimum FPR of branch can be derived as
FpS )1 FN.
FP P a A Q a
(32)
FN
Consider the inner minimization problem for given A. We can rewrite the inner minimization problem as below:
min b
Inft, + b, Ina)
EEA
subject to
Σ (L: + 6,)55 ST
EA
(33)
FNJENa
b, z FN, loga (1 PP (x,,)) ViEA
Fps + FN. 1,, ViEA
By following the same analysis as in Section 3, we can rewrite the outer minimization problem as the following Knapsack problem.
max x
Σ rs
In Ωi
+L, Ina) Thn
IE0
Fp,FN. (1=Fp))(1 - -FN.)) )ST
subject to
Σ S: (L, + FN, loga
(34)
IE0
Fp, + FN, < 1, ViEO
3 E (0, 1}, ViEo
The above problem can be solved by adapting Algorithm after removing oracles with FpA + FN. 2 1.
E.3. Ensemble Learned Bloomier Filter
Bloomier filters (Chazelle et al., 2004) variant of BF solve key-value lookup: each item in S has associated value; given an queried item e, the corresponding Bloomier filter outputs the value associated with or 1 if & S. We now extend our ELBF to the ensemble learned Bloomier filters by taking the following steps. First, each oracle is trained by regression to output a value or 1. once queried by an input item. If all the oracles output the same value, this value the final output. Second, we replace the each backup BF in ELBFs by a Bloomier filter to resolve the case where the oracles output inconsistent values. suffices to record the items with inconsistent oracle outputs with corresponding values in the backup Bloomier filters. In this way, our ELBF design can be extended to support key-value lookup.
G. Addiionna Experiments
G.1. Malicious URLs Detection
The main technical challenge in malicious URLs detection (MUD) is to quickly check whether a URL belongs to those flagged as malicious with limited memory overhead, to which BFs offer an efficient probabilistic solution.
In our experiments on the MUD task, we downloaded the dataset from Kaggle, including 1,682,213 URLs, 21.5% of which malicious, others are benign. 56 numerical features are extracted from these URLs, from which we use 26 features such URL length, URL unique character ratio, path's 'ss length and so on.
In our experiments, we use the same settings for oracles as in the first task of virus signature scan. The size of the large and small oracles are 268Kb and 30-34Kb, respectively. Each small oracles learns from 2 or 3 features.
The experiment results are shown in Figure 6. As in task 1, armed with mutually independent oracles, our proposition ELBF outperforms the ttate-of-the-art solutions traced in the experiments in terms of the FPR and time overhead. For the correlated case, our ELFF++ has the lowest FPR with less time overhead than Ada-BF and PLBB.
16

---

Ensemble Learned Bloom Filters: Two Oracles are Better than One
RF
LBF
BF
BF
18F
BF
ELBP
PLBP++
ELBF+4
0.3
0.3
Palie Postive Rtie
Time Overhead (3)
Fales Postine Rame
Time Overhead
0.1
1,0000
2,000
3,000
1,100
2,000
3,000
MMmorry Budger (Kb)
Memory Budget (Kb)
Figure 6. Performance comparison: mutually independent case (left), correlated case (right).
G.2. Universally Unique Identifier Check
In the third task of our experiments, we consider scenario where the features are independent with each other, by generating 100K Universally Unique Identifiers (UUID). UUID is a 128-bit number used to uniquely identify an entity. UUIDs are widely used in software systems to avoid maintaining a central naming system. BFs can be used to efficiently check the existence of UUIDs, when dealing with large volume of identifiers and when small number of false positives is acceptable.
In our experiments, we build synthetic dataset with 20 extracted features such as sum of digits, sum of characters, etc., and include the UUIDs whose number and sum of digits are greater than the overall average into the existence. Again, the setting of learning models we use is same as before. The size of the large and small oracles are 267Kb and 34Kb, respectively. Each small oracle learns from features.
The experiment results are shown in Figure 7. Again, our proposition ELBF outperforms the sate-of-the-as solutions traced in the experiments in terms of the FPR and time overhead, while ELBF++ outperforms the others in terms of the FPR with smaller time overhead than Ada-BF and PLBF.
PLBE
Fist PLBFee
ELBP
PLHP
Past P
BLBFet
0.33
Fabie Postive Rite
Time Overhead (8)
Fablr Photivv Rate
Overhead (6)
0.2
0.1
2.000 Memory Budget (Kb)
3,000
Memory Hudget (KCb)
Po:P1 BLB
Figure Performance comparison: mutually independent case (left), correlated case (right).
G.3. Time Overhead for Different Sizes of Oracles Pool
We compare the time overhead given a pool of different number of oracles under the space budget 2000Kb. Again, by time overhead we mean the time compute the optimal configuration of the entire data structure including the backup filter size, the oracles use, etc. The experiment results, depicted in Figure 8, show that the time overhead of ELBF is lower than Ada-BF, PLBF and Fast PLBF++ whenever the size of the pool, while that of EI BLB is lower than Ada-BF and PLBF. We observe that the time overhead of ELBF++ does not increases significantly, as its heuristic search does not traverse all situations practically.
G.4. Aberration Study w.r.t. Algorithm
Given a set of oracles, Algorithm 1 selects the optimal subset. In this subsection, we take aberration study that compares Algorithm against simpler approaches: (1) RS: random selection, (2) HA: selecting the oracles with the highest accuracy, (3) SM: selecting the oracles with the smallest memory consumption, and (4) HP: selecting the oracles with the highest product of the ratio of accuracy to memory and a factor 7. Without loss of generality, we default y to For each
17

---

Ensemble Learned Bloom Filters: Two Oracles are Better than One
compared approach, optimize the size of backup BF which ensures that each approach fully the memory budget. The experimental results is shown in Table 2, where budget as expected.
see that proposed approach yields the minimal FPR under each
I Ade-BF I OPLBF Ir Fast PLBF++ OE ELBE ELBF++
20
15
Time Overhead
10
Size of Oracles Pool
Figure 8. Time overhead for different sizes of oracles pool.
Table FPR comparison with simpler approaches.
Budget
RS
HA
SM
HP
Algorithm
1000Kb
0.1316
0.1326
0.1251
0.1248
0.1053
1500Kb
0.0706
0.0626
0.0657
0.0655
0.0596
2000Kb
0.0663
0.0352
0.0353
0.0354
0.0333
2500Kb
0.0305
0.0260
0.0258
0.0261
0.0251
3000Kb
0.0202
0.0181
0.0182
0.0179
0.0173
18


Reviews:
[{"review_id": "y6rTzfY0rf", "reviewer": "Reviewer_xEpC", "summary": "This problem examines whether combining multiple learned oracles can generate a system of lower false positive. In the first case, where each learned oracle is paired with a separate filter, the authors provide theoretical analysis to formulate the problem as a knapsack problem and use dynamic programming to select a configuration minimizing the final false positive rate. In the second case, where a few oracles correspond to one filter, the authors design a greedy algorithm to select the configuration.\n\nupdate after rebuttal:\n\nI noticed that both ELBF and ELBF++ are evaluated in section 6, so I have removed my previous comment on weaknesses. My score remains unchanged.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for the positive feedback. Our greedy algorithm developed in Section 4 is tested and evaluated in our primary experiments in Section 6 on Experiments, where it outperforms baselines under various memory constraints. More in-depth experiments are presented in Appendix due to page limit for the main text.", "claims_and_evidence": "The authors provide theoretical analysis and experiments to support their claims.", "methods_and_evaluation_criteria": "The experimental part is done by comparing false positive rate under limited memory budget, which makes sense to me.", "theoretical_claims": "I have checked the theoretical proof in section 3, which looks good.", "experimental_designs_or_analyses": "Yes, the experiment setup in section 6 looks good.", "relation_to_broader_scientific_literature": "n/a", "essential_references_not_discussed": "I am only familiar with one previous work Mitzenmacher 2018, which is listed in the paper, so the discussion of related work looks good to me.", "other_strengths_and_weaknesses": "Strength:\n1. The idea of ensembling learned bloom filters seems to be new to me and the idea is supported by both theoretical and empirical evidence.\n2. The theoretical analysis which uses lagrange multiplier to transform the configuration selection into a knapsack problem seems very nice and clean.\n3. The proposed method is compared with many other baselines in a very straightforward experiment setup.\n\nWeakness:\n1. It seems that there is no theoretical guarantee for the correlated oracle case", "other_comments_or_suggestions": "no", "questions_for_authors": "I wonder why the authors don't perform experiments to test their algorithm in section 4, as I understand that it may be too hard to derive theoretical guarantees for their greedy algorithm.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uwuJp6F7U8", "reviewer": "Reviewer_H5xL", "summary": "This paper studies Learned Bloom Filters (LBF), which enhance traditional Bloom Filters with a learned model (oracle) as a pre-filter. A key challenge in single-oracle LBFs is that the oracle’s size can become a bottleneck when the overall space budget is limited. To address this, the authors propose an ensemble approach that leverages multiple smaller learning oracles and optimizes the associated backup filters. They design and optimize ensemble LBFs for both independent and correlated oracles, demonstrating empirical performance improvements across three practical data analysis tasks. The main technical challenge of the paper is solving the combinatorial optimization problems required for LBF design. For independent oracles, they develop an approximate solution, while for correlated oracles, they propose a greedy heuristic.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for the positive feedback. We envision at least two future research directions related to this work: (1) developing theoretically proven algorithms for the correlated case, either exact or approxiation algorithms, ideally with low complexity, (2) extending our idea of orchestrating multiple oracles to other data structure design to improve compactness.", "claims_and_evidence": "The theorems are mathematically proved, and the performance of the proposed algorithms is empirically examined against state-of-the-art baselines.", "methods_and_evaluation_criteria": "The proposed algorithms are empirically compared to baselines in terms of memory usage, false positive rate, and time overhead, which are standard evaluation metrics for Bloom filters.", "theoretical_claims": "I did not verify the correctness of the proofs, but the proposed algorithms for the optimization problems are reasonable.", "experimental_designs_or_analyses": "The experimental setup, baselines, performance measures, and datasets appear reasonable. Moreover, the experimental results align with the theoretical expectations.", "relation_to_broader_scientific_literature": "The paper empirically compares the proposed Ensemble Learned Bloom Filters (ELBFs) with state-of-the-art baselines, including the canonical Bloom Filter (BF) without learning (Bloom, 1970) and several learned Bloom filters: LBF (Kraska et al., 2018), Ada-BF (Dai & Shrivastava, 2020), PLBF (Vaidya et al., 2021), and Fast PLBF++ (Sato & Matsui, 2023). The authors demonstrate improvements over these baselines in almost all experiments.", "essential_references_not_discussed": "I am not aware of any related works that are essential to understanding the key contributions of the paper but are not currently cited.", "other_strengths_and_weaknesses": "The idea of combining smaller oracles to overcome memory limitations is intuitive yet interesting and appears effective in practice. This approach offers a novel way to balance model size and accuracy in learned Bloom filters, which could inspire future research in space-efficient data structures.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LxW1BTPkZx", "reviewer": "Reviewer_YvD7", "summary": "This paper introduces Ensemble Learned Bloom Filters (ELBF), an approach to improving the performance of Learned Bloom Filters (LBF) by leveraging multiple learning oracles of smaller size instead of a single large oracle. The authors formulate the ELBF design as a combinatorial optimization problem: given a pool of oracles and a total space budget, the goal is to select a subset of oracles and determine the sizes of their backup Bloom filters to minimize the overall false positive rate (FPR). The paper draws structural analogies between this problem and the Knapsack problem, developing a Knapsack-based approximate algorithm with proven (ε,δ)-optimality. The authors also propose an extended design, ELBF++, for scenarios with correlated oracles sharing a common backup filter.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your comments. They are mostly insightful and make us step backwards to rethink several design issues of our algorithm. Please find our response below.\n\n**Answer to Q1.**\n- **Performance of ELBF w.r.t. number of oracles $n_o$:** Theoretically (worst-case complexity bound), in the case of independent oracles, ELBF scales as $O(n_o^2)$; in the case of correlated oracles ELBF++ scales as $O(n_o^3)$; Empirically we observe that the running time scales slightly more linearly in $n_o$. In our opinion, this does not bring significant burden, given that usually the number of available oracles is rather limited.\n- **Number of oracles to use:** There are two parameters/variables here. \n  * If the number of available oracles is fixed, the number of oracles to use as well as which oracles to use are both computed by our algorithms. In fact, when we are provided a pool of oracles, our algorithm computes the set of oracles to use, which implicitly computes the number of oracles to use. \n  * If your comment regards the number of oracles available, our response is that it depends on the quality of the available oracles. We provide the following intuitive analysis. We can define the notion of dominance such that, for a pair of oracles $i$ and $j$, $i$ dominates $j$ if the size of $i$ is not larger than the size of $j$ and the false potive rate of $i$ is not larger than that of $j$ and the false negative rate of $i$ is not larger than that of $j$. Given a pool of oracles, we can first perform pre-processing by removing all the oracles dominated by any other oracle in the pool. This pre-processing operation leaves us with only those oracles that are \"pareto\" with each other. And it is the number of such pareto oracles that has real impact on the performance of our algorithm. As the parameters of oracles can vary one to another, it is generically difficult to give an answer how many pareto oracles in the pool are \"sufficient\". To provide a reasonable quantitative response to your question, what we do is as follows: we randomly set oracles with reasonable parameters (in terms of size, false positive and negative rates) in practice and run our algorithm; we observe that in most cases no more than $20$ pareto oracles are enough; beyond this limit, we do not have significant performance gain.\n\n**Answer to Q2.** \n\nThis is a very pertinent comment that is typically posed regarding multiple-objective optimization. We have thought about this formulation in our research, which is symmetric to ours. Basically in this formulation we interchange objective and constraint in this formulation. We make two clarifications.\n- The main reason of analyzing the formulation of optimizing FPR by regarding space as constraint is simply because most related work, against which we compare our algorithm, also analyzed this formulation. It is thus fair and easy to perform comparison.\n- The second formulation can be addressed by our algorithm. An intuitive, not necessarily optimal, approach is to gradually increase the space (we discretize the space) and invoke our algorithm to compute the minimal FPR corresponding to the space. Once the FPR reaches the target FPR constraint, we output the corresponding space and the result. This adapted algorithm solves the new formulation of the problem, subject to small error caused by discretization.", "claims_and_evidence": "The claims made in the submission are generally supported by evidence:\n\n1. The claim that ELBFs outperform standard LBFs under the same space budget is convincingly demonstrated through theoretical analysis and empirical results across multiple datasets.\n\n2. The (ε,δ)-optimality claim for their Knapsack-based algorithm is supported by formal proofs in Theorem 3.2 and Appendix A.\n\n3. The claim about ELBF++ being more effective for correlated oracles is supported by the theoretical analysis in Section 4 and corresponding experimental results.", "methods_and_evaluation_criteria": "I am not familiar with this specific area, so I am unable to evaluate whether the evaluation criteria are appropriate.", "theoretical_claims": "As mentioned above, I am unable to evaluate the correctness of any proofs for the theoretical claims. If possible, I would suggest seeking the expert opinion of other reviewers who are familiar with this specific area.", "experimental_designs_or_analyses": "As mentioned above.", "relation_to_broader_scientific_literature": "The paper effectively positions itself within the broader literature on:\n\n1. Bloom filters and their variants - Building on the original work by Bloom (1970) and subsequent extensions.\n\n2. Learned Bloom filters - Acknowledging the foundational work by Kraska et al. (2018) and Mitzenmacher (2018).\n\n3. Ensemble learning - Drawing connections to the broader machine learning literature on ensemble methods.", "essential_references_not_discussed": "1. Recent work on adaptive Bloom filters that dynamically adjust their parameters\n2. Connections to other probabilistic data structures like Count-Min Sketch and their learned variants, which would provide broader context.", "other_strengths_and_weaknesses": "Strengths:\n1. The formulation of ELBF design as a combinatorial optimization problem is elegant and insightful.\n2. The theoretical analysis is rigorous, with formal optimality guarantees.\n3. The connection to the Knapsack problem provides a solid foundation for the algorithm design.\n\nWeaknesses:\n1. The experimental evaluation could include more diverse application domains beyond the specific data analysis tasks presented.\n2. The discussion of practical implementation considerations, such as training the multiple oracles efficiently, could be expanded.\n3. The hyperparameter sensitivity analysis could be more comprehensive, particularly regarding how to set optimal values in practice.", "other_comments_or_suggestions": "I am not familiar with this specific area, and I will adjust my rating based on the feedback from other reviewers. If other reviewers possess more expertise in this field and provide more technically thorough reviews, their perspectives should take precedence over mine.", "questions_for_authors": "1. How does the performance of ELBF scale with the number of available oracles? Is there a point of diminishing returns, and if so, how can practitioners determine the optimal number of oracles to use? This would help understand the practical limits of the ensemble approach.\n\n2. The paper focuses on minimizing FPR under a fixed space budget. Have you explored other optimization objectives, such as minimizing space usage under a fixed FPR constraint? This alternative formulation might be more relevant for certain applications.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper introduces Ensemble Learned Bloom Filters (ELBF), a framework that improves the efficiency of learned Bloom filters (LBF) by replacing a single large oracle with a combination of multiple smaller learned oracles. The authors formulate the ELBF design problem as a combinatorial optimization task and solve it using a dynamic programming approach based on the Knapsack problem for independent oracles, and a greedy heuristic for correlated oracles (ELBF++). The goal is to minimize the false positive rate (FPR) under a fixed space constraint. The authors support their claims with theoretical guarantees and comprehensive experiments across several benchmark tasks.

Most of the reviewers recommended acceptance. The reviewers appreciated the novelty of the solution, theoretical insights and experimental results.  They also suggested expanding the discussion on training multiple oracles, hyperparameter tuning, and practical deployment consideration, as well as expanding related work section. The authors should take this into account when preparing the final version of the paper.
Decision: Accept (poster)