Year: 2019

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.

heading: 1 INTRODUCTION
text: 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 ∈ S or otherwise. Several applications, in particular caching in memory constrained systems, have benefited tremendously from BF (Broder et al., 2002).
Bloom filter ensures a zero false negative rate (FNR), which is a 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 is a known theoretical limit to this reduction. To achieve a FPR of , BF costs at least n log2(1/ ) log2 e bits (n = |S|), which is log2 e ≈ 44% off from the theoretical lower bound (Carter et 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. (2006) has made use of the query frequency 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 a 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 a machine learning model (Hsu et al., 2019). Rae et al. (2019) further proposed Neural Bloom Filter that learns to write to memory using a 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 a pre-filter to give each query x a score s(x). s(x) is usually positively associated with the odds that x ∈ S. The assumption is that in many practical settings, the membership of a query in the set S can be figured out from observable features of x and such information is captured by the classifier assigned score s(x). The proposal of Kraska et al. uses this score and treats query x with score s(x) higher than a pre-determined threshold τ (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). Mitzenmacher (2018) further provided a formal mathematical model for estimating the performance of LBF. In the same paper, the author proposed a generalization named sandwiched learned Bloom filter (sandwiched
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 a 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 τ , the information in the score s(x) is never used. Thus, there is a clear waste of information. For instance, consider two elements x1 and x2 with τ > s(x1) s(x2). In the existing solutions, x1 and x2 will be treated in the exact same way, even though there is enough prior to believing that x1 is more likely positive compared to x2.
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, is 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 τ , is 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 a different trend for elements in the set and outside the set S. We observe that for keys, f(s(x)|x ∈ S) shows ascending trend as s(x) increases while f(s(x)|x /∈ S) has an 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 tuning 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 a 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-BF 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 x as a key if x ∈ S, or a non-key if x /∈ S. Let n denote the size of keys (n = |S|), and m denote the size of non-keys. We denote K as the number of hash functions used in the Bloom filter.

heading: 2 REVIEW: BLOOM FILTER AND LEARNED BLOOM FILTER
text: Bloom Filter: Standard Bloom filter for compressing a set S consists of an R-bits array and K independent random hash function h1, h2, · · · , hK , taking integer values between 0 and R− 1, i.e., hi : S ⇒ {0, 1, · · · , R − 1}. The bit array is initialized with all 0. For every item x ∈ S, the bit value of hi(x) = 1, for all i ∈ {0, 1, · · · ,K}, is set to 1.
To check a membership of an item x ′ in the set S, we return true if all the bits hi(x ′ ), for all i ∈ {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, x ′ may be wrongly identified to be positive when x ′ /∈ S while all the hi(x ′ )s are set to 1 due to random collisions. It can be shown that if the hash functions are independent, the expected FPR can be written as follows
E (FPR) = ( 1− ( 1− 1
R
)Kn)K .
Learned Bloom filter: Learned Bloom filter adds a 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 to classify whether any given query x belongs to S or not based on its observable features. LBF sets a threshold, τ , where x is identified as a key if s(x) ≥ τ . Otherwise, x will be inserted into a Bloom filter to identify its membership in a further step (Figure 1). 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|x /∈ S) ≥ τ ) or that of the Bloom filter.
It is clear than when the region s(x) ≥ τ contains large number of keys, the number of keys inserted into the Bloom filter decreases which leads to favorable FPR. However, since we identify the region s(x) ≥ τ as positives, higher values of τ is better. At the same time, large τ decreases the number of keys in the region s(x) ≥ τ , increasing the load of the Bloom filter. Thus, there is a clear trade-off.

heading: 3 A STRICT GENERALIZATION: ADAPTIVE LEARNED BLOOM FILTER
text: (ADA-BF)
With the formulation of LBF in the previous section, LBF actually divides the x into two groups. When s(x) ≥ τ , x 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 to no hash function at all, based on s(x) ≥ τ or not. Continuing with this mindset, we propose adaptive learned Bloom filter, where x is divided into g groups based on s(x), and for group j, we use Kj hash functions to test its membership. The structure of Ada-BF is represented in Figure 1(b).
More specifically, we divide the spectrum into g regions, where x ∈ Group j if s(x) ∈ [τj−1, τj), j = 1, 2, · · · , g. Without loss of generality, here, we assume 0 = τ0 < τ1 < · · · < τg−1 < τg = 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,
E (FPRj) = ( 1− ( 1− 1
R
)∑g t=1 ntKt )Kj = αKj (1)
where nt = ∑n t=1 I(τt−1 ≤ s(xi|xi ∈ S) < τt) is the number of keys falling in group t, and Kj is the number of hash functions used in group j. By varying Kj , E (FPRj) 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 Kj for groups with large number of keys nj , while decrease Kj for groups with small nj . It should be noted that f(s(x)|x ∈ S) shows an opposite trend compared to f(s(x)|x /∈ S) as s(x) increases (Figure 2). Thus, there is a need for variable tuning, and a spectrum of regions gives us the room to exploit these variability efficiently. Clearly, Ada-BF generalizes the LBF. When Ada-BF only divides the queries into two groups, by setting K1 = K, K2 = 0 and τ1 = τ , Ada-BF reduces to the LBF.

heading: 3.1 SIMPLIFYING THE HYPER-PARAMETERS
text: To implement Ada-BF, there are some hyper-parameters to be determined, including the number of hash functions for each group Kj and the score thresholds to divide groups, τj (τ0 = 0, τg = 1). Altogether, we need to tune 2g − 1 hyper-parameters. Use these hyper-parameters, for Ada-BF, the expected overall FPR can be expressed as,
E (FPR) = g∑ j=1 pjE (FPRj) = g∑ j=1 pjα Kj (2)
where pj = Pr(τj−1 ≤ s(xi|xi /∈ S) < τj). Empirically, pj can be estimated by p̂j = 1 m ∑m i=1 I(τj−1 ≤ s(xi|xi /∈ S) < τj) = mj m (m is size of non-keys in the training data and mj is size of non-keys belonging to group j). It is almost impossible to find the optimal hyperparameters that minimize the E (FPR) in reasonable time. However, since the estimated false positive items ∑g j=1mjα Kj = O(maxj(mjα Kj )), we prefer mjαKj to be similar across groups when E (FPR) is minimized. While αKj decreases exponentially fast with larger Kj , to keep mjαKj stable across different groups, we require mj to grow exponentially fast with Kj . Moreover, since f(s(x)|x /∈ S) increases as s(x) becomes smaller for most cases,Kj should also be larger for smaller s(x). Hence, to balance the number of false positive items, as j diminishes, we should increase Kj linearly and let mj grow exponentially fast.
With this idea, we provide a strategy to simplify the tuning procedure. We fix pjpj+1 = c and Kj − Kj+1 = 1 for j = 1, 2, · · · , g − 1. Since the true density of s(x|x /∈ S) is unknown. To implement the strategy, we estimate pjpj+1 by p̂j pj+1 = mj mj+1
and fix mjmj+1 = c. This strategy ensures p̂j to grow exponentially fast with Kj . Now, we only have three hyper-parameters, c, Kmin and Kmax (Kmax = K1). By default, we may also set Kmin = Kg = 0, equivalent to identifying all the items in group g as keys.
Lemma 1: Assume 1) the scores of non-keys, s(x)|x /∈ S, are independently following a distribution f ; 2) The scores of non-keys in the training set are independently sampled from a distribution f . Then, the overall estimation error of p̂j , ∑ j |p̂j − pj |, converges to 0 in probability as m becomes
larger. Moreover, if m ≥ 2(k−1) 2 [√ 1 π + √ 1−2/π δ ]2 , with probability at least 1 − δ, we have∑
j |p̂j − pj | ≤ .
Even though in the real application, we cannot access the exact value of pj , which may leads to the estimation error of the real E (FPR). However, Lemma 1 shows that as soon as we can collect enough non-keys to estimate the pj , the estimation error is almost negligible. Especially for the large scale membership testing task, collecting enough non-keys is easy to perform.

heading: 3.2 ANALYSIS OF ADAPTIVE LEARNED BLOOM FILTER
text: 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 pj/pj+1 = cj ≥ c > 1 and Kj −Kj+1 = 1, the expected FPR follows,
E (FPR) = g∑ j=1 pjα Kj =
∑g j=1 c
g−jαKj∑g j=1 c g−j ≤  (1− c)(1− (cα)g) ( 1α − c)(αg − (cα)g) αKmax , cα 6= 1
1− c 1− cg
· g, cα = 1 (3)
where Kmax = K1. To simplify the analysis, we assume cα > 1 in the following theorem. Given the number of groups g is fixed, this assumption is without loss of generality satisfied by raising c since α will increase as c becomes larger. For comparisons, we also need τ of the LBF to be equal to τg−1 of the Ada-BF. In this case, queries with scores higher than τ 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 τ .
Theorem 1: For Ada-BF, given pjpj+1 ≥ c > 1 for all j ∈ [g − 1], if there exists λ > 0 such that cα ≥ 1+λ holds, and nj+1−nj > 0 for all j ∈ [g−1] (nj is the number of keys in group j). When g is large enough and g ≤ b2Kc, then Ada-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 nj 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, f(s(x)|x /∈ S) decreases very fast while f(s(x)|x ∈ 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 g to divide the spectrum into more groups and get better FPR. The LBF is sub-optimal as it only has two regions. Our experiments clearly show this trend. For figure 3(a), Ada-BF achieves 25% of the FPR of the LBF when the bitmap size = 200Kb, while when the budget of buckets = 500Kb, Ada-BF achieves 15% of the FPR of the LBF. For figure 3(b), 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 of Ada-BF by dividing the spectrum into more small groups. On the contrary, when g is small, Ada-BF is more similar to the LBF, and their performances are less differentiable.

heading: 4 DISJOINT ADAPTIVE LEARNED BLOOM FILTER (DISJOINT ADA-BF)
text: Ada-BF divides keys into g groups based on 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 1(c). 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 j are inserted into j-th Bloom filter whose length is Rj (R = ∑g j=1Rj). Then, during the look up stage, we just need to identify a query’s group and check its membership in the corresponding Bloom filter.

heading: 4.1 SIMPLIFYING THE HYPER-PARAMETERS
text: Analogous to Ada-BF, disjoint Ada-BF also has a lot of hyper-parameters, including the thresholds of scores for groups division and the lengths of each Bloom filters. To determine thresholds τj , we use similar tuning strategy discussed in the previous section of tuning the number of groups g and mjmj+1 = c. 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 Rj buckets, the optimal number of hash functions Kj can be approximated as Kj =
Rj nj log(2), where nj is the number of keys in group j. And the corresponding optimal expected
FPR is E (FPRj) = µRj/nj (µ ≈ 0.618). Therefore, to enforce the expected number of false items being similar across groups, Rj needs to satisfy
mj · µ Rj nj = m1 · µ R1 n1 ⇐⇒ Rj nj − R1 n1 = (j − 1)log(c) log(µ)
Since nj is known given the thresholds τj and the total budget of buckets R are known, thus, Rj can be solved accordingly. Moreover, when the machine learning model is accurate, to save the memory usage, we may also set Rg = 0, which means the items in group j will be identified as keys directly.

heading: 4.2 ANALYSIS OF DISJOINT ADAPTIVE LEARNED BLOOM FILTER
text: The disjoint Ada-BF uses a 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-BF changes the buckets allocation, both methods share the same core idea to lower the overall FPR by reducing the FPR of the groups dominated by non-keys. Disjoint Ada-BF allocates more buckets for these groups to a achieve smaller FPR. In the following theorem,
we show that to achieve the same optimal expected FPR of the LBF, disjoint Ada-BF consumes less buckets. Again, for comparison we need τ of the LBF is equal to τg−1 of the disjoint Ada-BF.
Theorem 2: If pjpj+1 = c > 1 and nj+1 − nj > 0 for all j ∈ [g − 1] (nj is the number of keys 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.

heading: 5 EXPERIMENT
text: 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.

heading: 5.1 TASK1: MALICIOUS URLS DETECTION
text: We explore using Bloom filters to identify malicious URLs. We used the URLs dataset downloaded 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) to train the malicious URL classification model. 17 lexical features are extracted from URLs as the classification features, such as “host name length”, “path length”, “length of top level domain”, etc. We used “sklearn.ensemble.RandomForestClassifier1” to train a random forest model. After saving the model with “pickle”, the model file costs 146Kb in total. “sklearn.predict_prob" was used to give scores for queries.
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 a 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 to 646Kb. To implement the LBF, we tuned τ between 0 and 1, and picked the one giving the minimal FPR. The number of hash functions was determined by K = Round( Rn0 log 2), where n0 is the number of keys hashed into the Bloom filter conditional τ . To implement the sandwiched LBF, we searched the optimal τ and calculated the corresponding initial and backup filter size by the formula in Mitzenmacher (2018). 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 to 0 by default. Thus, we only need to tune the combination of (Kmax, c) that gives the optimal FPR. Similarly, for disjoint Ada-BF, we fixed Rg = 0 and searched for the optimal (g, c).
Result: Our trained machine learning model has a classification accuracy of 0.93. Considering the non-informative frequent class classifier (just classify as 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 as s(x) increases, the empirical density of s(x) 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 4(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 ≈ 0.9%, Ada-BF and disjoint Ada-BF only require 200Kb, while both LBF and the sandwiched LBF needs more than 350Kb. And to get a FPR ≈ 0.35%, Ada-BF 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 LBF.
1The Random Forest classifier consists 10 decision trees, and each tree has at most 20 leaf nodes.

heading: 5.2 TASK 2: VIRUS SCAN
text: Bloom filter is widely used to 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 a 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 a binary classification model using Random Forest model 2. We used “sklearn.ensemble.RandomForestClassifier” 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_prob” in “sklearn” library) is used as the score s(x). Other implementation details are similar to that in Task 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 to 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
2The Random Forest classifier consists 15 decision trees, and each tree has at most 5 leaf nodes.
by over 80%. To achieve a 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.

heading: 5.3 SENSITIVITY TO HYPER-PARAMETER TUNING
text: Compared with the LBF and sandwiched LBF where we only need to search the space of τ to optimize the FPR, our algorithms require to tune a series of score thresholds. In the previous sections, we have proposed a simple but useful tuning strategies where the score thresholds can be determined by only two hyper-parameters, (K, c). Though our hyper-parameter tuning technique may lead to a 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 5 shows that for both Ada-BF and disjoint Ada-BF, tuning c while fixing K has already achieved similar FPRs compared with optimal case by tuning both (K, c), which suggests our algorithm does not require very accurate hyper-parameter tuning to achieve significant reduction of the FPR.

heading: 5.4 DISCUSSION: SANDWICHED LEARNED BLOOM FILTER VERSUS LEARNED BLOOM FILTER
text: Sandwiched LBF is a generalization of LBF and performs no worse than LBF. Although Mitzenmacher (2018) has shown how to allocate bits for the initial filter and backup filter to optimize the expected FPR, their result is based on the a 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 is optimized when τ 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 as the bitmap size becomes larger, sparing more bits to the initial filter is clever, and the sandwiched LBF shows the its advantage over the LBF (Figure 6(b)).

heading: 6 CONCLUSION
text: 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 compared with the previously proposed LBF and sandwiched LBF even when the learner’s discrimination power . We envision that our work will help and motivate integrating machine learning model into probabilistic algorithms in a more efficient way.

heading: APPENDIX A SENSITIVITY TO HYPER-PARAMETER TUNING

heading: APPENDIX B MORE COMPARISONS BETWEEN THE LBF AND SANDWICHED
text: LBF

heading: APPENDIX C COMPARING THE BLOOM FILTER TO HIERARCHICAL
text: 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 in identifying keys in some cases. To show its unique role, we replaced the machine learning model with another Bloom filter such that it becomes a hierarchical Bloom filter (learner is replaced by an initial filter). To implement the hierarchical Bloom filter, we spare 50% of the bit budget to the initial filter and use the other bits to build the backup filter.
Figure 7 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 a memory efficient approach.

heading: APPENDIX D PROOF OF THE STATEMENTS
text: Proof of Lemma 1: Let Zj(x) = ∑m i=1 1(s(x) ∈ [τj−1, τj)|x /∈ S), then Zj(x) ∼
Bernoulli(pj), and mj = ∑m i=1 Zj(xi) counts the number of non-keys falling in group j and p̂j = mj m . To upper bound the probability of the overall estimation error of pj , first, we need to
evaluate its expectation, E (∑K j=1|p̂j − pj | ) .
Since mj is a binomial random variable, its exact cdf is hard to compute. But with central limit theorem, when m is large, mj−mpj√
mpj(1−pj) −→ N(0, 1). Thus, we can approximate E (|p̂j − pj |) = E ( | mj−mpj√ mpj(1−pj) | ) · √ pj(1−pj) m ≈ √ 2 π · √ pj(1−pj) m (if Z ∼ N(0, 1), E (|Z|) = √ 2 π ). Then, the ex-
pectation of overall error is approximated by E (∑K j=1|p̂j − pj | ) ≈ √ 2 mπ · (∑K j=1 √ pj(1− pj) ) , which goes to 0 as m becomes larger.
We need to further upper bound the tail probability of ∑K j=1|p̂j − pj |. First, we upper bound the
variance of ∑K j=1|p̂j − pj |,
Var  K∑ j=1 |p̂j − pj |  ≤ K K∑ j=1 Var (|p̂j − pj |) = K K∑ j=1 ( Var (p̂j − pj)− E (|p̂j − pj |)2 )
≈ K m K∑ j=1 pj(1− pj)− 2 π ( K∑ i=1 √ pj(1− pj) )2 , K m V (p)
Now, by envoking the Chebyshev’s inequality,
P  K∑ j=1 |p̂j − pj | ≥  = P  K∑ j=1 |p̂j − pj | − E  K∑ j=1 |p̂j − pj |  ≥ − E  K∑ j=1 |p̂j − pj |  ≤ Var (∑K j=1|p̂j − pj | )
( − E (∑K j=1|p̂j − pj | ))2 = KV (p)
m ( − E (∑K j=1|p̂j − pj | ))2 −→ 0 as m −→∞
Thus, ∑K j=1|p̂j − pj | converges to 0 in probability as m −→∞.
Moreover, since we have
E  K∑ j=1 |p̂j − pj |  ≈ √ 2 mπ ( K∑ j=1 √ pj(1− pj)) ≤ √ 2 mπ (K − 1) (4)
V (p) = K∑ j=1 pj(1− pj)− 2 π ( K∑ i=1 √ pj(1− pj) )2 ≤
K∑ j=1 ( pj(1− pj) ( 1− 2 π ))
≤ ( 1− 2
π
)( 1− 1
K
) (5)
Then, by Eq 4 and Eq 5, we can upper bound P [∑K j=1|p̂j − pj | ≥ ] by,
P  K∑ j=1 |p̂j − pj | ≥  ≤ KV (p) m ( − E (∑K j=1|p̂j − pj |
))2 ≤ (1− 2π )(K − 1)
m ( − √ 2 mπ (K − 1) )2 (6) When m ≥ 2(k−1) 2 [√ 1 π + √ 1−2/π δ ]2 , we have m ( − √ 2 mπ (K − 1) )2 ≥ (K−1)(1− 2 π ) δ , thus,
P [∑K j=1|p̂j − pj | ≥ ] ≤ δ.
Proof of Theorem 1: For comparison, we choose τ = τg−1, for both LBF and Ada-BF, queries with scores larger than τ are identified as keys directly by the same machine learning model. Thus, to compare the overall FPR, we only need to evaluate the FPR of queries with score lower than τ .
Let p0 = P [s(x) < τ |x /∈ S] be the probability of a key with score lower than τ . Let n0 denote the number of keys with score less than τ , n0 = ∑ i:xi∈S I(s(xi) < τ). For learned Bloom filter using K hash functions, the expected FPR follows,
E (FPR) = (1− p0) + p0 ( 1− ( 1− 1
R
)Kn0)K = 1− p0 + p0βK , (7)
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 determineKmax andKmin = Kmax−g+1. Let pj = Pr(τj−1 ≤ s(x) < τj |x /∈ S) The expected FPR of the Ada-BF is,
E (FPRa) = g∑ j=1 pj
( 1− ( 1− 1
R
)∑g−1 j=1 Kjnj )K j = g−1∑ j=1 pjα Kj , (8)
where ∑g−1 j=1 nj = n0. Next, we give a strategy to select Kmax which ensures a lower FPR of Ada-BF than LBF.
Select Kmax = bK + g2 − 1c. Then, we have
n0K = g−1∑ j=1 njK = K n1 + g−1∑ i=2 (n1 + j−1∑ i=1 Ti) = n1(g − 1) + g−2∑ j=1 Tj(g − j − 1)  = 2K
g − 2  (g − 1)(g − 2) 2 n1 + g−2∑ j=1 (g − 2)(g − 1− j) 2 Tj  ≤ 2
g − 2  (g − 1)(g − 2) 2 n1 + g−2∑ j=1 (g + j − 2)(g − 1− j) 2 Tj  = 2
g − 2 g−1∑ j=1 (j − 1)nj (9)
By Eq 9. we further get the relationship between α and β.
g−1∑ j=1 Kjnj = g−1∑ j=1 (Kmax − j + 1)nj ≤ n0 ( Kmax − g 2 + 1 ) ≤ n0K =⇒ α ≤ β.
Moreover, by Eq. 3, we have,
E (FPRa) = (1− c)(1− (cα)g) ( 1α − c)(αg − (cα)g) αKmax ≤ (1− c)(1− (cα) g) ( 1α − c)(αg − (cα)g) βKmax
≤ βKmax α(c− 1) cα− 1
< E (FPR) ( 1 + λ
λ βKmax−K ) ≤ E (FPR) ( 1 + λ
λ βbg/2−1c
) .
Therefore, as g increases, the upper bound of E (FPRa) decreases exponentially fast. Moreover, since 1+λ λ is a constant, when g is large enough, we have 1+λ λ β
bg/2−1c ≤ 1. Thus, the E (FPRe) is reduced to strictly lower than E (FPR).
Proof of Theorem 2: Let η = log(c)log(µ) ≈ log(c) log(0.618) < 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
p1 · µR1/n1 = pj · µRj/nj =⇒ Rj = nj ( R1 n1 + (j − 1)η ) , for j ∈ [g − 1]
where Rj is the budget of buckets for group j. For group j, since all the queries are identified as keys by the machine learning model directly, thus, Rg = 0. Given length of Bloom filter for group 1, R1, the total budget of buckets can be expressed as,
g−1∑ j=1 Rj = g−1∑ j=1 nj n1 R1 + (j − 1)njη
Let p0 = Pr(s(x) < τ |x /∈ S) and pj = Pr(τj−1 ≤ s(x) < τj |x /∈ S). Let n0 denote the number of keys with score less than τ , n0 = ∑ i:xi∈S I(s(xi) < τ), and nj be the number of keys in group
j, nj = ∑
i:xi∈S I(τj−1 ≤ s(xi) < τj). Due to τ = τg−1, we have
∑g−1 j=1 nj = n0. Moreover, since
τg−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 τ . If LBF and Ada-BF achieve the same optimal expected FPR, we have
p0 · µR/n0 = g−1∑ j=1 pj · µRj/nj = g · p1 · µR1/n1
=⇒ R = n0 n1 R1 − n0 log(p0/p1)− log(g) log(µ)
= g−1∑ j=1 [ nj n1 R1 − nj log(1− ( 1 c ) )g − log (1− 1c )− log(g) log(µ) ] ,
where R is the budget of buckets of LBF. Let Tj = nj+1 − nj ≥ 0. Next, we upper bound ∑g−1 j=1 nj
with ∑g−1 j=1(j − 1)nj .
g−1∑ j=1 nj = n1 + g−1∑ i=2 (n1 + j−1∑ i=1 Ti) = n1(g − 1) + g−2∑ j=1 Tj(g − j − 1)
= 2
g − 2  (g − 1)(g − 2) 2 n1 + g−2∑ j=1 (g − 2)(g − 1− j) 2 Tj  ≤ 2
g − 2  (g − 1)(g − 2) 2 n1 + g−2∑ j=1 (g + j − 2)(g − 1− j) 2 Tj  = 2
g − 2 g−1∑ j=1 (j − 1)nj
Therefore, we can lower bound R,
R ≥ g−1∑ j=1 [ nj n1 R1 − (j − 1)nj 2(log(1− ( 1 c ) )g − log (1− 1c )− log(g)) (g − 2) log(µ) ] .
Now, we can lower bound R− ∑g−1 j=1 Rj ,
R− g−1∑ j=1 Rj ≥ g−1∑ j=1 (j − 1)nj
[ −η − 2(log(1− ( 1 c ) )g − log (1− 1c )− log(g)) (g − 2) log(µ) ] .
Since η is a negative constant, while 2(log(1−( 1c )) g−log(1− 1c )−log(g)) (g−2) log(µ) approaches to 0 when g is large. Therefore, when g is large, η − 2(log(1−( 1 c ))
g−log(1− 1c )−log(g)) (g−2) log(µ) < 0 and R − ∑g−1 j=1 Rj is strictly
larger than 0. So, disjoint Ada-BF consumes less memory than LBF to achieve the same expected FPR.

Review summaries:
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. 

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.