Adaptive Learned Bloom Filter (Ada-BF): Efficient Utilization of the Classifier
Authors: Zhenwei Dai
Anshumali Shrivastava
Venue:  (2020)
Keywords: Ada-BF
Bloom filter
machine learning
memory efficient

Abstract: Recent work suggests improving the performance of Bloom filter by incorporating a machine learning model as a binary classifier. However, such learned Bloom filter does not take full advantage of the predicted probability scores. We proposed new algorithms that generalize the learned Bloom filter by using the complete spectrum of the scores regions. We proved our algorithms have lower False Positive Rate (FPR) and memory usage compared with the existing approaches to learned Bloom filter. We also demonstrated the improved performance of our algorithms on real-world datasets.

Under review as a conference paper at ICLR 2020
ADAPTIVE LEARNED BLOOM FILTER (ADA-BF): EFFICIENT UTILIZATION OF THE CLASSIFIER
Anonymous authors Paper under double-blind review
ABSTRACT
Recent work suggests improving the performance of Bloom filter by incorporating a machine learning model as a binary classifier. However, such learned Bloom filter does not take full advantage of the predicted probability scores. We proposed new algorithms that generalize the learned Bloom filter by using the complete spectrum of the scores regions. We proved our algorithms have lower False Positive Rate (FPR) and memory usage compared with the existing approaches to learned Bloom filter. We also demonstrated the improved performance of our algorithms on real-world datasets.
INTRODUCTION
Bloom filter (BF) is a widely used data structure for low-memory and high-speed approximate membership testing (Bloom 1970). Bloom filters compress a given set S into bit arrays, where we can approximately test whether a given element (or query) x belongs to a set S, i.e., x E S or otherwise. Several applications, in particular caching in memory constrained systems, have benefited tremendously from BF (Broder et al. 2002).
Bloom filter ensures zero false negative rate (FNR), which is critical requirement for many applications, However, BF does not have a non-zero false positive rate (FPR) (Dillinger and Manolios 2004) due to hashing collisions, which measures the performance of BF. There known theoretical limit to this reduction. To achieve a FPR of BF costs at least n 1og,(1/e /c) log, e bits (n [S)), which is log2
44% off from the theoretical lower bound (Carter al., 1978). Mitzenmacher (2002) proposed Compressed Bloom filter to address the suboptimal space usage of BF, where the space usage can reach the theoretical lower bound in the optimal case.
To achieve a more significant reduction of FPR, researchers have generalized BF and incorporated information beyond the query itself to break through the theoretical lower bound of space usage. Bruck et al. (2066) has made use of the query frrquency and varied the number of hash functions based on the query frequency to reduce the overall FPR. Recent work (Kraska et al. 2018 Mitzenmacher 2018) has proposed to improve the performance of standard Bloom filter by incorporating machine learning model. This approach paves a new hope of reducing false positive rates beyond the theoretical limit, by using context-specific information in the form of machine learning model (Hsu al. 2019). Rac et al. (2019) further proposed Neural Bloom Filter that learns to write to memory using distributed write scheme and achieves compression gains over the classical Bloom filter.
The key idea behind Kraska et al. (2018) is to use the machine learning model as pre-filter to give each query score s(x). s(x) is usually positively associated with the odds that æ S. The assumption is that in many practical settings, the membership of query in the set S can be figured out from observable features of x and such information is captured by the classifier assigned score (ar). The proposal of Kraska et al. uses this score and treats query with score s(x) higher than pre-determined threshold r (high confidence predictions) as a direct indicator of the correct. membership. Queries with scores less than are passed to the back-up Bloom filter.
Compared to the standard Bloom filter, learned Bloom filter (LBF) uses a machine learning model to answer keys with high score s(x). Thus, the classifier reduces the number of the keys hashed into the Bloom filter. When the machine learning model has a reliable prediction performance, learned Bloom filter significantly reduce the FPR and save memory usage (Kraska et al. 2018). Mitzenmachhr (2018) further provided a formal mathematical model for estimating the performance of LBF. In the same paper, the author proposed generalization named sandwiched learned Bloom filter (sandwiched

---

Under review as a conference paper at ICLR 2020
LBF), where an initial filter is added before the learned oracle to improve the FPR if the parameters are chosen optimally.
Wastage of Information: For existing learned Bloom filters to have a lower FPR, the classifier
score greater than the threshold should have small probability of wrong answer. Also, a significant fraction of the keys should fall in this high threshold regime to ensure that the backup filter is small. However, when the score s(x: is less than T, the information in the score s(x) is never used. Thus, there is a clear waste of information. For instance, consider two elements I1 and 22 with т >> s(x1)) > sx2g). In the existing solutions, 2ι and 22 will be treated in the exact same way, even though there is enough prior to believing that æ is more likely positive compared to Ø2.
Strong dependency on Generalization: It is natural to assume that prediction with high confidence implies a low FPR when the data distribution does not change. However, this assumption is too strong for many practical settings. First and foremost, the data distribution is likely to change in an online streaming environment where Bloom filters are deployed. Data streams are known to have bursty nature with drift in distribution (Kleinberg] 2003). As a result, the confidence of the classifier, and hence the threshold, not completely reliable. Secondly, the susceptibility of machine learning oracles to adversarial examples brings new vulnerability in the system. Examples can be easily created where the classifier with any given confidence level T, incorrectly classified. Bloom filters are commonly used in networks where such increased adversarial false positive rate can hurt the performance. An increased latency due to collisions can open new possibilities of Denial-of-Service attacks (DoS) (Feinstein et al. 2003).
Motivation: For a binary classifier, the density of score distribution, f(s(x:)) shows different trend for elements in the set and outside the set S. We observe that for keys, f(s(x) E S) shows ascending trend as s(x) increases while (s(()]] & S) has opposite trend. To reduce the overall FPR, we need lower FPRs for groups with a high f (s(x) x & S). Hence, if we are tuming the number of hash functions differently, more hash functions are required for the corresponding groups. While for groups with a few non-keys, we allow higher FPRs. This variability is the core idea to obtaining a sweeter trade-off.
Our Contributions: Instead of only relying on the classifier whether score s(x) is above single specific threshold, we propose two algorithms, Ada-BF and disjoint Ada-BF, that rely on the complete spectrum of scores regions by adaptively tuning Bloom filter parameters in different score regions. 1) Ada-BF tunes the number of hash functions differently in different regions to adjust the FPR adaptively; disjoint Ada-Bi dda-FFann allocates variable memory Bloom filters to each region. 2) Our theoretical analysis reveals a new set of trade-offs that brings lower FPR with our proposed scheme compared to existing alternatives. 3) We evaluate the performance of our algorithms on two datasets: malicious URLs and malware MD5 signatures, where our methods reduce the FPR by over 80% and save 50% of the memory usage over existing learned Bloom filters.
Notations: Our paper includes some notations that need to be defined here. Let [g] denote the index set (1, 2, ... .g). We define query as key if x E S, or a non-key if x & S. Let denote the size of keys (n = (S), and m denote the size of non-keys. We denote as the number of hash functions used in the Bloom filter.
2 REVIEW: BLOOM FILTER AND LEARNED BL.OOM FILTERR
Bloom Filter: Standard Bloom filter for compressing set S consists of R-bits array and K independent random hash function h1, h2.... ... hug. taking integer values between and R - 1, i.e. h4 : S = {0,1, value of h2 = 1, for all E (0, 1, ... K]. is set to 1.
R 1}. The bit array is initialized with all 0. For every item x E S, the bit
To check membership of an item x in the set S. we return true if all the bits h, ) for all i E (0. 1............... K} have been set to 1. It is clear that Bloom filter has zero FNR (false negative rate). However, due to lossy hash functions, æ may be wrongly identified to be positive when x $ S while all the h (z') )s are set to due to random collisions. It can be shown that if the hash functions are independent, the expected FPR can be written follows
Kn K
(1
E (FPR)- =
1
R
2

---

Under review as a conference paper at ICLR 2020
Learned Bloom filter: Learned Bloom filter adds binary classification model to reduce the effective number of keys going to the Bloom filter. The classifier is pre-trained on some available training data classify whether any given query z belongs to S not based its observable features. LBF sets a threshold, т, where x is identified as a key s(x) 2 т. Otherwise, a will be inserted into Bloom filter identify its membership in further step (Figure I Like standard Bloom filter, LBF also has zero FNR. And the false positives can be either caused by that false positives of the classification model (s(x)2 $ S) 2 T) or that of the Bloom filter.
It is clear than when the region s(z) 2 contains large number of keys, the number of keys inserted into the Bloom filter decreases which leads favorable FPR. However, since we identify the region s(r) 2 as positives, higher values of T is better. At the same time, large decreases the number of keys in the region s(x: 2 т, increasing the load of the Bloom filter. Thus, there is a clear trade-off.
3 A STRICT GENERALIZATION: ADAPTIVE LEARNED BLOOM FILTER (ADA-BF)
With the formulation of LBF in the previous section, LBF actually divides the ø into two groups. When s(x) 2 T. will be identified as a key directly without testing with the Bloom filter. In other words, it uses zero hash function to identify its membership. Otherwise, we will test its membership using K hash functions. In other view, LBF switches from K hash functions no hash function at all, based on s(x) 2 T or not. Continuing with this mindset, we propose adaptive learned Bloom filter, where divided into y groups based on (ar), and for group j. we Kj hash functions to test its membership. The structure of Ada-BF is represented in Figure[[b
AA
[8]
Dendity
Densty
Dencity
clko
012
G12
Gil
4043
Eaccion
Seatirn
0
Figure 1: Panel A-C show the structure of LBF, Ada-BF and disjoint Ada-BF respectively.
More specifically, we divide the spectrum into g regions, where x E Group j if s(x) [T T,), j = 1, ... .g. Without loss of generality, here, we assume 0 = < <... Tg-1 < Tg 1. Keys from group j are inserted into Bloom filter using Kj independent hash functions. Thus, we use different number of universal hash functions for keys from different groups.
For a group j. the expected FPR can be expressed as,
Eis meKe) m K,
1
1
E (FPR,))
1
k
(1)
R
where n, = Ex T(T--1 S s<xg/1r ES < Tt) the number of keys falling in group I, and K₃ is the number of hash functions used in group j. By varying Kj, E (FPR,) can be controlled differently for each group.
Variable number of hash functions gives us enough flexibility to tune the FPR of each region. To avoid the bit array being overloaded, we only increase the K, for groups with large number keys nj. while decrease K, for groups with small n2.. It should be noted that f fs)()) E S) shows an opposite trend compared to f<(x)) |æ & S) as s(x) increases (Figure 2). Thus, there is a need for variable tuning, and a spectrum of regions gives the room exploit these variability efficiently.
Clearly, Ada-BF generalizes the LBF. When Ada-BF only divides the queries into two groups, by
setting K₁ K, K₂ 0 and 71 T, Ada-BF reduces to the LBF.
3

---

Under review as a conference paper at ICLR 2020
3.1 SIMPLIFYING THE PEEEER-PRRAMTERSS
To implement Ada-BF, there are some hyper-paramene parameters to be determined, including the number of hash functions for each group K and the score thresholds to divide groups, T (7o- = 0, Tg 1). Altogether, we need to tune 2g hyper-parameters, Use these hyper-parameters, for Ada-BF, the expected overall FPR can be expressed as,
(FPR)
Σ (FPR)) ==1
= Σ p,a j=1
(2)
where Pj = Pr(ts-1 I s(ailt & 5) < Tj)- Empirically, Pj can be estimated by P3 m -i=1 I(T,-1 I s(z;/2; & S) < 72) = my (m is size of non-keys in the training data and my is size of non-keys belonging to group j). It almost impossible to find the optimal hyper- parameters that minimize the E (FPR) in reasonable time. However, since the estimated false positive (imaxy(mja
1
items Σj=1 myak;
we prefer mya*, to be similar across groups when
E (FPR) is minimized. While ax; decreases exponentially fast with larger Kj. to keep mya Ks stable across different groups, we require my to grow exponentially fast with Ky. Moreover, since [(((x)]< & 5) increases as s(r) becomes smaller for most cases, K2 should also be larger for smaller s(x). Hence, to balance the number of false positive items, as j diminishes, we should increase K3 linearly and let m, grow exponentially fast.
With this idea, we provide strategy to simplify the tuming procedure. We fix Py = c and Pi-1
Kj- Kj+1 1 for j 1,2, ... .9 Since the true density of s(a|æ & 5) is unknown. To implement the strategy, we estimate Pi_ by Pi. my and fix _y c. This strategy ensures parameters, c, Kmin and Kmax maaaz K2). By default, may also set Kmin Kg 0, equivalent to identifying all the items in group as keys.
Pj+1 Py+1 my+1
my++
Pj to grow exponentially fast with Ky. Now, we only have three
Assume 1) the scores of non-keys, s(x) & S, are independently following distribu- tion f: The scores of non-keys in the training set are independently sampled from distribution Then, the overall estimation error of Pú. E,10; Pjl. converges to 0 in probability as m becomes
Lemma 1:
larger. Moreover, if m 2
2(k
V 1-2
2/
with probability at least - 8, we have
E,li- pp5 S.
Even though in the real application, we cannot access the exact value of Pj. which may leads the estimation error of the real E (FPR). However, Lemma shows that as soon as we can collect enough non-keys estimate the py. the estimation error is almost negligible. Especially for the large scale membership testing task, collecting enough non-keys is easy to perform.
3.2 ANALYSIS OF ADAPTIVE LEARNED BLOOM FILTER
Compared with the LBF, Ada-BF makes full use the of the density distribution s(x: and optimizes the FPR in different regions. Next, we will show Ada-BF can reduce the optimal FPR of the LBF without increasing the memory usage.
When Ps/P/41
Cj 2 c and K2- Kj+1 = 1, the expected FPR follows,
c) - (ca)s)
9
piak E
0 a
c)(3 (ca)o) a Kmas ca + 1
E (FPR)=
Σ j=l
(3)
c--j
c9 g.
ca
where Kmaz K1. To simplify the analysis, we assume ca in the following theorem. Given the number of groups g is fixed, this assumption is without loss of generality satisfied by raising c since a will increase as e becomes larger. For comparisons, we also need T of the LBF be equal to T9-1 of the Ada-BF. In this case, queries with scores higher than 7 are identified as keys directly by the machine learning model. So, to compare the overall FPR, we only need to compare the FPR of queries with scores lower than
4

---

Under review as a conference paper at ICLR 2020
Theorem 1: For Ada-BF, given Pi <>> 1 for all [g 1], if there exists À >> 0 such that
Py+1
ca 2. 1+ holds, and Rj+11 R2 > 0 for all j E [g - 1] (nz is the number of keys in group j). When g is large enough and g - ]. then Ada-Bu BF has smaller FPR than the LBF. Here K is the number of hash functions of the LBF.
Theorem 1 requires the number of keys n, keeps increasing while Pj decreases exponentially fast with j. As shown in figure 2 on real dataset, we observe from the histogram that as score increases, [()(2))(2 & S) decreases very fast while (<((x) |ar E S) increases. So, the assumptions of Theorem 1 are more or less satisfied.
Moreover, when the number of buckets is large enough, the optimal K of the LBF is large as well. Given the assumptions hold, theorem 1 implies that we can choose a larger 9 to divide the spectrum into more groups and get better FPR. The LBF sub-optimal as only has two regions. Our experiments clearly show this trend. For figure a), Ada-BF BF achieves 25% of the FPR of the LBF when the bitmap size 200Kb, while when the budget of buckets 500Kb, Ada-BI BF achieves 15% of the FPR of the LBF. For figure ()), Ada-BF only reduces the FPR of the LBF by 50% when the budget of buckets 100Kb, while when the budget of buckets 300Kb, Ada-BF reduces 70% of the FPR of the LBF. Therefore, both the analytical and experimental results indicate superior performance Ada-BF by dividing the spectrum into more small groups. On the contrary, when g is small, Ada-BF is more similar the LBF, and their performances are less differentiable.
4 DISIOINT ADAPTIVE LEARNED BL.OMM FILTER (DISIOINT ADA-BF)
Ada-BF divides keys into g groups based their scores and hashes the keys into the same Bloom filter using different numbers of hash functions. With the similar idea, we proposed an alternative approach, disjoint Ada-BF, which also divides the keys into g groups but hashes keys from different groups into independent Bloom filters. The structure of disjoint Ada-BF is represented in Figure ( Assume we have total budget of R bits for the Bloom filters and the keys are divided into g groups using the same idea of that in Ada-BF. Consequently, the keys from group are inserted into j-th Bloom filter whose length R2 (R = - R2). Then, during the look up stage, we just need to identify a query's 's group and check its membership in the corresponding Bloom filter.
4.1 SIMPLJFFING THE HYPER-PARAMETER
Analogous Ada-BF, disjoint Ada-BB also has a lot of ttyper-paammeten including the thresholds of scores for groups division and the lengths of each Bloom filters. To determine thresholds Tj we use similar tunigg strategy discussed the previous section of tuning the number of groups To find Rj that optimizes the overall FPR, again, we refer to the idea in the previous section that the expected number of false positives should be similar across groups. For a Bloom filter with Rg buckets, the optimal number of hash functions Kj can be approximated as Kj R2 12)(2), where ny is the number of keys in group j. And the corresponding optimal expected ny FPR is EE (FPR,) Ry/n (u & 0.618). Therefore, to enforce the expected number of false items being similar across groups, R2 needs to satisfy
g and m, mi
R
R n2
R
G - 1)log(e)
my
log(/))
Since ny is known given the thresholds tj and the total budget of buckets R are known, thus, Rý be solved accordingly. Moreover, when the machine learning model is accurate, memory usage, we may also set Rg = O, which means the items in group j will be identified as keys directly.
the
4.2 ANALYSIS OF DISJOINT ADAPTIVE LEARNED BLOOM FILTER
The disjoint Ada-BF uses group of shorter Bloom filters to store the hash outputs of the keys. Though the approach to control the FPR of each group is different from the Ada-BF, where the Ada-BF varies K and disjoint Ada-BE -F changes the buckets allocation, both methods share the same core idea to lower the overall FPR by reducing the FPR the groups dominated by non-keys. Disjoint Ada-BF allocates more buckets for these groups to achieve smaller FPR. In the following theorem,
5

---

Under review as a conference paper at ICLR 2020
show that to achieve the same optimal expected FPR of the LBF, disjoint Ada-BF consumes less buckets. Again, for comparison we need T of the LBF is equal to T--1 of the disjoint Ada-BF.
Theorem 2: If Ps = c and Rz+1 - nj > 0 for all j E [g - 1] (nz is the number of keys
p5+1
in group j), to achieve the optimal FPR of the LBF, the disjoint Ada-BF consumes less buckets compared with the LBF when g is large.
5 EXPERIMENT
Baselines: We test the performance of four different learned Bloom filters: 1) standard Bloom filter, 2) learned Bloom filter, 3) sandwiched learned Bloom filter, 4) adaptive learned Bloom filter, and 5) disjoint adaptive learned Bloom filter. We use two datasets which have different associated tasks, namely: 1) Malicious URLs Detection and 2) Virus Scan. Since all the variants of Bloom filter structures ensure zero FNR, the performance is measured by their FPRs and corresponding memory usage.
5.1 TASKI: MALICIOUS URLS DETECTION
We explore using Bloom filters to identify malicious URLs. We used the URLs dataset down- loaded from Kaggle, including 485,730 unique URLs. 16,47% of the URLs are malicious, and others are benign. We randomly sampled 30% URLs (145,719 URLs) URL classification model. 17 lexical features are extracted from URLs as the classification fea- tures, such "host name length", "path length". "length of top level domain", etc. We used .ww.eaar..esembee..... Trnsemble.RandomFooo SandoomForsaCllsssffee to train random forest model. After saving the model with "pickle", the model file costs 146Kb in total. akklear..reedct_pne pprob was used to give scores for queries.
train the malicious
We tested the optimal FPR for the four learned Bloom filter methods under the total memory budget 200Kb to 500Kb (kilobits). Since the standard BF does not need machine learning model, to make a fair comparison, the bitmap size of BF should also include the machine learning model size (146 Kb in this experiment). Thus, the total bitmap size of BF is 346Kb 646Kb, To implement the LBF, we tuned r between 0 and 1, and picked the one giving the minimal FPR. The number of hash functions was determined by K- Round It no 2)g where Bop is the number of keys hashed into the Bloom filter conditional т. To implement the sandwiched LBF, calculated the corresponding initial and backup filter size by the formula in Mitzenmacher (2018) I).. When the optimal backup filter size is larger than the total bits budget, sandwiched LBF does not need a initial filter and reduces to a standard LBF. For the Ada-BF, we used the tuning strategy described in the previous section. Kmin was set by default. Thus, we only need to tune the combination of K Keazs c) that gives the optimal FPR. Similarly, for disjoint Ada-BF, BF, we fixed R. O and searched for the optimal (g, c).
searched the optimal т and
Result: Our trained machine learning model has a classification accuracy of 0.93. Considering the non-informative frequent class classifier (just classify benign URL) gives accuracy of 0.84, our trained learner is not a strong classifier. However, the distribution of scores is desirable (Figure 2 where s(x) increases, the empirical density of szz) decreases for non-keys and also increases for keys. In our experiment, when the sandwiched LBF is optimized, the backup filter size always exceeds the total bitmap size. Thus, it reduces to the LBF and has the same FPR (as suggested by Figure a)).
Our experiment shows that compared to the LBF and sandwiched LBF, both Ada-BF and disjoint Ada-BF achieve much lower FPRs. When filter size 500Kb, Ada-BF reduces the FPR by 81 % compared to LBF or sandwiched LBF (disjoint FPR reduces the FPR by 84%). Moreover, to achieve a FPR z 0.9%, Ada-Bo BF and disjoint Ada-BF only require 200Kb, while both LBF and the sandwiched LBF needs more than 350Kb. And to get a FPR x 0.35%, Ada-Bo ida-BFodd and disjoint Ada-BF reduce the memory usage from over 500Kb of LBF to 300Kb, which shows that our proposed algorithms save over 40% of the memory usage compared with LBF and sandwiched L.F..
'The Random Forest classifier consists 10 decision trees, and each has at 20 leaf nodes.

---

Under review as a conference paper at ICLR 2020
Score Distribution Malicious URLs
Score Distribution of Benign URLs
Malicious
Benig
16F
Chart
107
16
(a)
(b)
Figure 2: Histogram of the classifier's score distributions of keys (Malicious) and non-keys (Benign) for Task 1. We can see that ny (number of keys in region j) is monotonic when score > 0.3. The partition was only done to ensure
+1 2
Pr
5.2 TASK 2: VIRUS SCAN
Bloom filter is widely used match the file's signature with the virus signature database. Our dataset includes the information of 41323 benign files and 96724 viral files. The virus files are collected from VirusShare database (Vir). The dataset provides the MD5 signature of the files, legitimate status and other 53 variables characterizing the file, like "Size of Code", "Major Link Version" and "Major Image Version". We trained machine learning model with these variables to differentiate the benign files from the viral documents. We randomly selected 20% samples as the training set to build binary classification model using Random Forest model D We used "sklearn.c www.eeeneeee...adnooo. SandomForestClasiifee to tune the model, and the Random Forest classifier costs about 136Kb. The classification model achieves 0.98 prediction accuracy on the testing set. The predicted the class probability (with the function "predict_pproe in "sklearn" library) is used as the score s sxx). Other implementation details are similar to that Task 1.
Score Distribution of Files
Score Distribution Benign Files
Benign
Count
Count
16a
0.1
0.2
0.3
6.4
0.5
0.6
0.7
0.2
0.3
0.4
0.5 Score
0.6
0.7
0.5
0.9
Store
(a)
(b)
Figure 3: Histogram of the classifier score distributions for the Virus Scan Dataset. The partition was only done to ensure
2 c.
+1+
Result: As the machine learning model achieves high prediction accuracy, figure 4 suggests that all the learned Bloom filters show huge advantage over the standard BF where the FPR is reduced by over 98%. Similar the previous experiment results, we observe consistently lower FPRs of our algorithms although the the score distributions are not smooth or continuous (Figure 3 Again, our methods show very similar performance. Compared with LBF, our methods reduce the FPRs
TThe Random Forest classifier consists 15 decision trees, and each has leaf nodes.

---

Under review as a conference paper at ICLR 2020
False Pocitive Rates Comparison
False Rates Comparison
15.0%
43.0%
16.0%
LBF
20.0%
5.0%
sandwiched LBF
sard sardwiched LBF
Positive Rate
2.50%
Ada BF
False Pasitive Rate
0.80%
Ada-BF
0.70%
0.60%
1.50%
0.50%
0.40%
1.00%
0.50%
0.10%
0.00%
0.00%
100
150
200
Biomap
Bitmap (Kb)
(a)
(b)
Figure 4: FPR with memory budget for all the five baselines (the bit budget of BF = bitmap size + learner size). (a) FPRs comparison of Malicious URL detection experiment; (b) FPRs comparison of Virus scan experiment.
by over 80%. To achieve 0.2% FPR, the LBF and sandwiched LBF cost about 300Kb bits, while Ada-BF only needs 150Kb bits, which is equivalent to 50% memory usage reduction compared to the previous methods.
5.3 SENSITIVITY TO HYPER-PARAMETER TUNING
Compared with the LBF and sandwiched LBF where we only need search the space of optimize the FPR, our algorithms require to tune series of score thresholds. In the previous sections, we have proposed simple but useful tuming strategies where the score thresholds can be determined by only two sub-optimal choice, our experiment results have shown we can still gain significantly lower FPR compared with previous LBF. Moreover, if the number of groups K is misspecified from the optimal choice (of K), we can still achieve very similar FPR compared with searching both K and c. Figure shows that for both Ada-BF and disjoint Ada-BI, tuning while fixing K has already achieved similar FPRs compared with optimal case by tuming both (K, c), which suggests our algorithm does not require very accurate perammer tuning to achieve significant reduction of the FPR.
(K,c) Though our hyper-parametee tuning technique may lead to
5.4 DISCUSSION: SANDWICHED LEARNED BLOOM FILTER VERSUS LEARNED BLOOM FILTER
Sandwiched LBF is a generalization of LBF and performs no worse than LBF. Although Mitzen macher (2118) has shown how allocate bits for the initial filter and backup filter to optimize the expected FPR. their result is based on the fixed FNR and FPR. While for many classifiers, FNR and FPR are expressed as functions of the prediction score т. Figure 4 a) shows that the sandwiched LBF always has the same FPR as LBF though we increase the bitmap size from 200Kb to 500Kb. This is because the sandwiched LBF optimized when 7 corresponds to a small FPR and a large FNR, where the optimal backup filter size even exceeds the total bitmap size. Hence, we should not allocate any bits to the initial filter, and the sandwiched LBF reduces to LBF. On the other hand, our second experiment suggests the bitmap size becomes larger, sparing more bits to the initial filter is clever, and the sandwiched LBF shows the its advantage over the IBFF (Figure 6 (b))
6 CONCLUSION
We have presented new approaches to implement learned Bloom filters. We demonstrate analytically and empirically that our approaches significantly reduce the FPR and save the memory usage com- pared with the previously proposed LBF and sandwiched LBF even when the learerr' discrimination power. We envision that our work will help and motivate integrating machine learning model into probabilistic algorithms in more efficient way.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Virusshare 2018.
attps://wirushaare..oo//eeeeesss 4n6
Burton H Bloom. Space/time trade-offs in hash coding with allowable errors. ACM, 13(7):422-466, 1970.
Commuiccations of the
Andrei Broder, Michael Mitzenmacher, and Andrei Broder Michael Mitzenmacher. Network applications of bloom filters: A survey. In Interner Mathematics. Citeseer, 2002.
Jehoshua Bruck, Jie Gao, and Anxiao Jiang. Weighted bloom filter. In 2006 IEEE International Symposium on Information Theory, pages 2304-2308. IEEE, 2006.
Larry Carter, Robert Floyd, John Gill, George Markowsky, and Mark Wegman. Exact and approximate membership testers. Proceedings of the tenth annual ACM symposium on Theory of computing. pages 59 59-65. ACM, 1978.
Peter C. Dillinger and Panagiotis Manolios. Bloom filters in probabilistic verification. In Alan J. Hu and Andrew K. Martin, editors, Formal Methods in Computer-Aided Design, page 370, Berlin, Heidelberg, 2004. Springer Berlin Heidelherg. ISBN 978-3-540-3049444.
Laura Feinstein, Dan Schnackenberg, Ravindra Balupari, and Darrell Kindred. Statistical approaches to ddos attack detection and response. In Proceedings DARPA information survivability conference and exposition, volume pages 303-314. IEEE, 2003.
Chen-Yu Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. Learning-based frequency estimation algorithms. In International Conference on Learning Representations, 2019. URL https /openrevieww net 2oee//fmmmdddd1ooooo0
Jon Kleinberg. Bursty and hierarchical structure in streams. Data Mining and Knowledge Discovery, 7(4):373-397, 2003.
Tim Kraska, Alex Beutel, Ed H Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. In Proceedings of the 2018 International Conference on Management of Data, pages 489-504 ACM, 2018.
Michael Mitzenmacher. Compressed bloom filters. IEEE/ACM Transactions on Networking (TON), 1065):604-612, 2002.
Michael Mitzenmacher. A model for learned bloom filters and optimizing by sandwiching. In Advances in Neural Information Processing Systems, pages 464-473, 2018.
Jack W Rae, Sergey Bartunov, and Timothy P Lillicrap. Meta-learning neural bloom filters. arXiv preprint arXiv: 04304, 2019.

---

Under review as a conference paper at ICLR 2020
APPENDIX A
SENSITIVITY TO HYPER-PARAMETER TUNING
Ada-BF: FPRs with different K
Disjoint Ada-BF: FPRs with different
1.20%
K=10
1.20%
K=10
K=11
1.00%
K-12
1.00%
K-12
Faise Positive Rate
False Positive Rate
Optimal
Optimal
0.80%
0.80%
0.60%
0.60%
0.40%
0.40%
0.20%
0.20%
0.00%
0.00%
200
250
300
350
400
450
500
200
250
300
350
400
450
500
Budget buckets (Kb)
Budget buckets (Kb)
(a)
(b)
Figure 5: FPR comparison of tuning e while fixing the number of groups K and tuning both (K, e)
APPENDIX B
MORE COMPARISONS BETWEEN THE LBF AND SANDWICHED LBF
LBF sandwiched LBF
LBF sandwiched LBF
2.50%
LBF
0.70%
LBF
sandwiched LBF
sandwiched LBF
False Positive Rate
False Positive Rate
0.50%
1.50%
0.40%
1.00%
0.30%
0.20%
0.50%
0.00%
0.00%
200250300350400450
600 800
700
100
150
200
250
300
350
400
450
500
Budget buckets (Kb)
Budget
(Kb)
(b)
Figure 6: FPR comparison between LBF and sandwiched LBF under different bitmap sizes. (a) malicious URL experiment; (b) malware detection experiment
APPENDIX C COMPARING THE BLOOM FILTER TO HIERARCHICAL HASHING
The machine learning model used in the learned Bloom filters is critical because it has discrimination power between the keys and non-keys and is more efficient identifying keys in some cases. To show its unique role, we replaced the machine learning model with another Bloom filter such that becomes hicrarchical Bloom filter (learner is replaced by an initial filter.. To implement the hierarchical Bloom filter, spare 50% of the bit budget to the initial filter and use the other bits to build the backup filter.
Figure Souure7shhre shows that the hierarchical BF does not outperform the original BF under all the budget of buckets, and in some cases, it even achieves a worse FPR. Hence, using a random hash function to replace the learner is not memory efficient approach.
10

---

Under review as a conference paper at ICLR 2020
Comparison to Hierarchical Bloom filter
10.0%
BF
..... Hierarchical
False Positive Rate
8.0%
6.0%
4.0%
2.0%
0.0%
200
250
300
350
450
Budget of buckets (Kb)
Figure 7: FPR comparison between LBF and sandwiched LBF under different bitmap sizes. (a) malicious URL experiment; (b) malware detection experiment
APPENDIX D PROOF OF THE STATEMENTS
Proof of Lemma 1: Let (z( Σ [(s(x) E [T)- & S), then Zz(x) ~ Bernoulli(p)). and my = Σi=1 (2;) counts the number of non-keys falling in group j and pj = my To upper bound the probability of the overall estimation error of py. first, we need to evaluate its expectation, E EE pjl)
Since my is binomial random variable, its exact edf is hard compute. But with central limit theorem, when m is large,
my mpp
N 1). Thus, we can approximate E (1p, p,l) =
(1 Pp)
my- my-mpy mmpp(L-p))
p2(1=ps) (if 1(0.1).E((Z)) ادーمك - p3l) ~
/ Then, the ex-
m
m
pectation of overall error is approximated by E which goes to 0 becomes larger.
2
[E VPJ (1-))))) p9)
MAST
We need to further upper bound the tail probability of ΣK pyl. variance of Σ>= 16q Pyl.
First, we upper bound the
K
Var
Σ
10 psl
S K
Var (1p, -P;)) K
Σ
VVar (Ø) Pp) (EE -Ee; p31)²)
j=1
V py(1 ps)) )
K
2
a K
p,(1 (p,)
Σ
V(p)
π
m
Now, by envoking the Chebyshev's inequality,
K
P
Σ 10
26
P
Σ D0 Ppyl-B -E
Σ 1=1
Di psl
Σ
p3j Pjl
j=1
Var
5 Σ==1 16g psl)
6 E
E los - -Pjl)
KV(p)
0 as m 0
E 10 1:50-P1)) p11))²
m
c- E

---

Under review as a conference paper at ICLR 2020
Thus, Σj=10 pyl converges to 0 in probability -> D
Moreover, since we have
2
2 (K 1)
E
Σ Pj
pyl
pj --;)) S
MIT
==1
P₂(1 P.) 2 Σ
V(p)
Σ
V pj(1 -0-ppp))) pU)
K
Pj(1 - -pj) (1 π
(1-2))
<
2
(1
1
1
-
(5)
K
Then, by Eq 4 and Eq
5
we can upper bound P
PDl 2 by,
K
KV(p)
P
10
26
m
IE
(1 2 )) -1)
(6)
2
2 (K - 11
m
V
mxt
2
When m 2
2(h-1)
1 +
2/a
we have m
6 V
2. (K - 1)
(K
(K-1)(1-2) thus,
mes
P - ps1 2
$ 6.
Proof of Theorem 1: For comparison, we choose 7 = Tg for both LBF and Ada-BF, queries with scores larger than are identified keys directly the same machine learning model. Thus, to compare the overall FPR, we only need to evaluate the FPR of queries with score lower than 7.
Let Po = P [s(x)) < T/x & 5] be the probability of a key with score lower than r. Let nop denote the number of keys with score less than 7, no Σ (s(x;;) 7). For learned Bloom filter using K
hash functions, the expected FPR follows,
E (FPR) = (1 po) + po (1- (1-(1-
Kno
K
= =1 + Po,3
(7)
R
where R is the length of the Bloom filter. For Ada-BF, assume we fix the number of groups g. Then, we only need to determine K Kmaz and Kmin Kmaz 1. Let = Pr(r,-1 S s(x) < Tylæ $ S) The expected FPR of the Ada-Bo MFa-BFin is.
9
(1-(1-1)
1 E K,ng
g-1 Σ
E (FPRR))
Σ
Pj
1-
1
(8)
j=1
where Σ n1 no- Next, we give strategy select Kmaz which ensures lower FPR of Ada-BF than LBF.
12

---

Under review as a conference paper at ICLR 2020
Select Kmaz
K + - 11.
Then, we have
9-1
g
1-1
8-2
noK
2
niK K
11
71
Σ
Ti)
nilg 1) + Σ
Tz و - --
i=1
2K
[g (g
2)
9-2
(g 2) - 1111-1111 -
11
9
2
j=1
(g 1)
2)
9-2
(g + 22 - 1 1- -))))
11
+
9 2
2
j=1
2
Σ
(j 1)ng
9
By Eq 9
we further get the relationship between a and B.
g-1
9-1
(Kmar -+ 1)n S no (marx- 9 +11 S ngK = asp
Kynj
1=1
j=1
Moreover, by Eq.
we have,
(1 - c)(1 (ca)3)
c) (ca)))
E (FPR.)
a Kmaz
ca (cax) gk
(2 c) (a9 - (cor)0)
8 KKaa a(c - 1)
00 1
1 + X gKmux Kuu K
E (FPR)
(1 X 8la/2-11
E (FPR)
Therefore, increases, the upper bound of E (FPR,) decreases exponentially fast. Moreover, since - is constant, when y is large enough, we have 1 31o/2-11 < 1. Thus, the E (FPR.) is reduced to strictly lower than E (FPR). 0
0. By the tuning strategy described in the previous section, we require the expected false positive items should be similar across the groups. Thus, we have
Proof of Theorem 2: Let "
log(c)
logíe)
log(a)
1og(0.618)
P1 p R1/m1 = Pý pp By/m; = Rg =
+ (j -1m)m for j E lg -1]
n1
where Rí is the budget of buckets for group For group j. since all the queries are identified keys by the machine learning model directly, thus, R. 0. Given length of Bloom filter for group 1, Ri, the total budget of buckets can be expressed as,
g-1
g
Σ 1=1
R
nl
Ri + 1)n,m
n1
j=1
Let po = Pr(s(x) < 7/ & 5) and pj = Pr(ti-1 S ((x) < <Tyle & S). Let no denote the number
of keys with score less than T, 14g
Σ
[8((1)) T), and n, be the number of keys in group
13

---

Under review as a conference paper at ICLR 2020
n. Σ I(r-11 (((z)) Ty). 12;E88
Due Tg-1, we have Σ}=1 n2 ng. Moreover, since
Ty-1 queries with score higher than have the same FPR for both disjoint Ada-BF and LBF. So, we only need to compare the FPR of the two methods when the score is lower than 7. LBF and Ada-BF achieve the same optimal expected FPR, we have
g
Po 1 R/mo
By/ng = -9 p1 11 B1/ns
Pj
1
j=1
no
log(po/pi) log(g)
R
=
Ri
n20
log(1))
log(1 - (1)) log (1 2 - log(g)
m R1
n2
111
log(u)
where R is the budget of buckets of LBF. Let T3 = ni++1 nj 2 O. Next, we upper bound Σ3 nz
with Ej 1)mg.
2
nj
n1+
(n1
Σ
T:)
n1 1)+ + Σ T9 - j- -1 1)
j=1
2=2
[=1
2
(g 1)(g 2)
9-2
[g (1-2)g--1-i)
11
+
9 - 2
2
1=1
2
1)(g
2)
g-2
(g + - 2)(g 2)
11 +
Σ
9 -
2
j=1
2 8-1
1)n,
9-2 2 j=1
Therefore, we can lower bound R,
2(log(1 (1)) log (1 - ()) log(g))
R P
R - -j 11n
(g log(H)
Now, can lower bound R EE= Rj.
-11 2(log(1 - (2)) - log (1 - 2) - log(g)) 2) log(
R
1)ng
Since 17 is negative constant, while 2[log[1 (1)) -log( 1- 2) -log(g) approaches when g is large. and - E Ry is strictly larger than 0. So, disjoint Ada-BF consumes less memory than LBF to achieve the same expected FPR.
(8 2) log(
Therefore, when g is large, 7 2(log(1 - ( loggl111111 -oog
(g Ing(a)
14


Reviews:
[{"review_id": "SkgM4JEJcH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes two new bloom filter algorithms that incorporate a learnt model for estimating if an input is in the set or not. These methods blend the space between pure BF and learnt BF with one threshold by creating regions over the score and having varying number of hash functions for each region.\n\nI really like the paper and the approach taken. However, the experiments are on such small datasets that the true impact of these models aren't as impressive as they could be. In practice, BFs are used when dealing with millions/billions of entries to achieve real-time performance in real-world. For such applications, not only the memory is of concern but also the run-time part of the equation. In other words, if we have a learnt classifier for BF, how much will it impact the execution time vs memory usage as both are needed to be traded-off. It would have been great if the authors had experimented with larger datasets and had practical considerations for run-time and memory vs FPR investigated.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Byx9PWQ6tH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposed an adaptive learned bloom filter. Rather than setting a threshold of prediction score, the paper partitions the score into several intervals; for query insider each interval, the paper either uses a group of independent hash functions to hash the query in one unified bloom filter or introduce an independent bloom filter. The paper proposes efficient ways to tune the hyper-parameters, and provides the analysis of the error. Experiments on two applications show the effectiveness of the proposed methods. \n\nThe idea seems useful. However, I have a few concerns/questions. My decision depends on the responses of the author(s). \n\n(1) Although the paper claims the score information can be fully exploited, the paper seems to do hashing for all possible queries. Why not set up a tau such that only when the score is below tau, we conduct the adaptive hashing? When the score is bigger than tau, we still claim an identification of the key? In this way, a bunch of keys can still be saved and without extra hashing. \n\n(2) The proposed method seems to be a hierarchical hashing strategy.  The first level is to hash the queries into different intervals through a score function learned from data. Why not compose another group of random hash to do the first level hashing? What is the major benefit of collecting training examples to run a machine learning model? Accordingly, why not compare with such a baseline using a group of random hashing to do the first level? ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "ByeFmAOpYr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper extends the Bloom filter learning by using the complete spectrum of the scores regions. It uses multiple thresholds and then varies the number of hash functions among different scores regions to obtain better trade-off. Detailed theoretical analysis provides guaranteed superiority over learned Bloom filter under some conditions. The experiments also show the two proposed methods outperform learned Bloom filter in FPR and memory usage.\n\nThe motivation is based on the observation that the keys' score distribution density has an opposite trend to the non-keys. Though the experiment results support this observation, some theoretical analysis on this and its relationship with the final FPR could be provided. ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper improves the Bloom filter learning by utilizing the complete spectrum of the scores regions. 

The paper is nicely written with strong motivation and theoretical analysis of the proposed model. The evaluation could be improved: all the experiments are only tested on the small datasets, which makes it hard to assess the practicality of the proposed method. The paper could lead to a strong publication in the future if the issue on evaluation can be addressed. 

Decision: Reject