Partitioned Learned Bloom Filters
Authors: Kapil Vaidya
Eric Knorr
Michael Mitzenmacher
Tim Kraska
Venue: ICLR 2021 Poster (2021)
Keywords: optimization
data structures
algorithms
theory
learned algorithms

Abstract: Bloom filters are space-efficient probabilistic data structures that are used to test whether an element is a member of a set, and may return false positives.  Recently, variations referred to as learned Bloom filters were developed that can provide improved performance in terms of the rate of false positives, by using a learned model for the represented set.  However, previous methods for learned Bloom filters do not take full advantage of the learned model.  Here we show how to frame the problem of optimal model utilization as an optimization problem, and using our framework derive algorithms that can achieve near-optimal performance in many cases.

Published as a conference paper at ICLR 2021
PARTITIONED LEARNED BLOOM FILTER
Kapil Vaidya
Eric Knorr
CSAIL
School of Engineering and Applied Sciences
MIT
Harvard University
kapilvemit.es
w.w.cr..norreeeg com.
Tim Kraska
Michael Mitzenmacher
CSAIL
School of Engineering and Applied Sciences
MIT
Harvard University mi chae lm@eecs haarvrrd.edu
kraska@mit.ent edu
ABSTRACT
Bloom filters are space-efficient probabilistic data structures that are used to test whether element is member of set, and may return false positives. Recently, variations referred as learned Bloom filters were developed that can provide improved performance in terms of the rate of false positives, by using learned model for the represented set. However, previous methods for learned Bloom filters do not take full advantage of the learned model. Here show how frame the problem of optimal model utilization as an optimization problem, and using our framework derive algorithms that can achieve near-optimal performance in many cases. Experimental results from both simulated and real-world datasets show significant performance improvements from our optimization approach over both the original learned Bloom filter constructions and previously proposed heuristic improvements.
INTRODUCTION
Bloom filters are space-efficient probabilistic data structures that are used to test whether an element a member of a set [Bloom] 1970)]. Bloom filter compresses given set S into an array of bits. Bloom filter may allow false positives, but will not give false negative matches, which makes them suitable for numerous memory-constrained applications in networks, databases, and other systems areas. Indeed, there are many thousands of papers describing applications of Bloom filters [Dayan et al. 2018), Dillinger& & Manolios (2004). Broder & Mitzenmacheri (2003)].
There exists trade off between the false positive rate and the size of Bloom filter (smaller false positive rate leads to larger Bloom filters). For a given false positive rate, there are known thcoretical lower bounds on the space used (Pagh et al.] (2005)] by the Bloom filter. However, these lower bounds assume the Bloom filter could store any possible set. If the data set or the membership queries have specific structure, it may be possible to beat the lower bounds in practice [Mitzenmacher (2002). Bruck et al. (2006), Mitzenmacher et al. (2020)]. In particular, [Kraska et al. (2018)] and Mitzenmacher (20t)) propose using machine learning models reduce the space further, by using learned model to provide suitable pre-filter for the membership queries. This allows one to beat the space lower bounds by leveraging the context specific information present in the learned model. Rae et al, (2019) propose 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 of learned Bloom filters is that in many practical settings, given query input, the likelihood that the input is in the set S can be deduced by some observable features which can be captured by machine learning model. For example, a Bloom filter that represents a set of malicious URLs can benefit from a learned model that can distinguish malicious URLs from benign URLs. This model can be trained on URL features such length of hostname, counts of special characters, etc. This approach is described in (Kaska et al. (2018)), which studies how standard index structures can be improved using machine learning models; we refer their framework the original learned

---

Published as a conference paper at ICLR 2021
Bloom filter, Given imput and its features, the model outputs score s(x) which is supposed to correlate with the likelihood of the input being in the set. Thus, the elements of the set, or keys, should have higher score value compared to non-keys. This model is used pre-filter, so when score s(x) of an input & is above a pre-determined threshold i, it is directly classified as being in a smaller backup Bloom filter built from only keys with score
the set. For inputs where s(x) below the threshold (which are known) is used. This maintains the property that there are no false negatives. The design essentially uses the model to immediately answer for inputs with high score whereas the rest of the inputs are handled by the backup Bloom filter as shown in Fig D A). The threshold value t used to partition the space of scores into two regions, with inputs being processed differently depending on in which region its score falls. With sufficiently accurate model, the size of the backup Bloom filter can reduced significantly over the size of a standard Bloom filter while maintaining overall accuracy. (Kraska et al. (2018)] showed that, in some applications, even after taking the size of the model into account, the learned Bloom filter can be smaller than the standard Bloom filter for the same false positive rate.
The original learned Bloom filter compares the model score against a single threshold, but the framework has several drawbacks.
Choosing the right threshold:
The choice of threshold value for the learned Bloom filter is critical, but the original design uses heuristics to determine the threshold value.
Using more partitions: Comparing the score value only against a single threshold value wastes information provided by the learning model. For instance, two elements I1, I2 with s(x1) >> s(22) > t, are treated the same way but the odds of z1 being a key are much higher than for 22- Intuitively, we should be able to do better by partitioning the score space into more than two regions.
Optimal Bloom filters for each region: Elements with scores above the threshold are directly accepted as keys. A more general design would provide backup Bloom filters in both regions and choose the Bloom filter false positive rate of each region so as to optimize the space/false positive trade-off as desired. The original setup can be interpreted as using a Bloom filter of size 0 and false positive rate of above the threshold. This may not be the optimal choice; moreover, as we show, using different Bloom filters for each region(as shown in Fig [C)) allows further gains when we increase the number of partitions.
Follow-up work by Miizenmacchr (2018) and [Dai & Shrivastava (219) improve on the original design but only address a subset of these drawbacks. In particular, Mitzenmacher (2018) proposes using Bloom filters for both regions and provides method find the optimal false positive rates for each Bloom filter. But [Mitzenmacher] (2018)] only considers two regions and does not consider how to find the optimal threshold value. [Di & Shrivastava (2019) [0]9)] propose using multiple thresholds to divide the space of scores into multiple regions, with a different backup Bloom filter for each score region. The false positive rates for each of the backup Bloom filters and the threshold values chosen using heuristics. Empirically, we found that these heuristics might perform worse than Miizenmacher [ in some scenarios.
A general design that resolves all the drawbacks would, given target false positive rate and the learned model, partition the score space into multiple regions with separate backup Bloom filters for each region, and find the optimal threshold values and false positive rates, under the goal of minimizing the memory usage while achieving the desired false positive rate as shown in Fig [C). In this work, we show how to frame this problem as an optimization problem, and show that our resulting solution significantly outperforms the heuristics used in previous works. Additionally, we show that our maximum space saving is linearly proportional to the KL divergence of the key and non-key score distributions determined by the partitions. We present a dynamic programming algorithm to find the optimal parameters (up to the discretization used for the dynamic programming) and demonstrate performance improvements over synthetic dataset and two real world datasets: URLs and EMBER. We also show that the performance of the learned Bloom filter improves with increasing number of partitions and that in practice a small number of regions (= 4 - 6) suffices to get a very good performance. We refer to our approach as partitioned learned Bloom filter (PLBF). Experimental results from both simulated and world datasets show significant performance improvements. We show that to achieve a false positive rate of 0.001, [Mitzenmacher (018)) uses
ssaace saved by using our approach instead of Bloom filter
2

---

Published as a conference paper at ICLR 2021
8.8x, 3.3x and 1.2x the amount of space and (Dai & Shrivastava (2019) uses 6x, 2.5x and 1. the amount of space compared to PLBF for synthetic, URLs and EMBER respectively.
2
BACKGROUND
Input
Input
Inpur (X)
Negative
Bloem fiterr
Model
8(x) S
Model
s(x) t
Learned Modal
Positive
6 50 s(x)
1,5 s(x) 4t
S(x) $ 11
Bloom filar
Positive
s(x)
s(x)
Bloom
fiter
Bloom fiter
Positive
Neg5live
Positive
Negilive
Pozitive
Negative
Postive Negative
Posttive
Negative
Positive
(A)
(B)
(C)
hi())
g(x)
D(A): keys
hox)
Input (x)
hod): Diat. non-kaya
Mtegion alo0
1"Rogloon
Region
s mle) +
tt sD0) 1
"Rogion 1.00
Region 904)
s(x) s
8(x) >
Scores 500
Bloom fitte
Bloom filter
Scores *(*)
-.....
0
011 1100
1
Nagalive
Postivn Negitiioe
Positiw
f
(D)
(F)
Figure I: (C) represent the original LBF, LBF with sandwiching, and PLBF designs, respectively. Each region in (C) is detined by score boundaries t,, t.41 1 and a false positive rate f. of the Bloom Filter used for that region. (D),EE show the LBF and PLBF with score space distributions. (F) represents PLBF design equivalent
to the sandwiching approach used in Appendix D.I
2.1 STANDARD BLOOM FILTERS AND RELATED VARIANTS
standard Bloom filter, as described in Bloom's original paper [Bloom (970 ]. is for set S = {21, (2, ................................ 2.,) } of n keys. It consists of an array of m bits and uses i independent hash functions (h1, h2. with the range of each h2 being integer values between 0 and m 1. We assume the hash functions are fully random. Initially all m bits are O. For every key x E S, array bits (x) set to 1 for all i E (1,
A membership query for y returns that y E S hv This ensures that the Bloom filter has no false negatives but non-keys might result in a false positive. This false positive rate depends on the space m used by the Bloom Filter. Asymptotically (for large m, n with m/n n held constant), the false positive rate is given by
for all i (1,2...kk and y & S otherwise.
kn k
1 -
(I)
m
See Broder & Mitzenmacher 22003; Bose et al. (2088) for further details.
Bloom 1970 proved a space lower bound of |.S] log2(+) for Bloom filter with false positive
rate F. The standard construction uses space that is asymptotically log, e( 1.44) times more
than the lower bound. Other constructions exist, such Cuckoo filters et al. (2014), Morton filters(Graf GGrf & Lemire (2020) and Vacuum filters Wang al.) [2019)]. These variants achieve slightly better space performance compared to standard Bloom filters but still are a constant factor larger than the lower bound. (Pagh et al. (2005) presents Bloom
filters Breslow & Jayasena [, XOR filters
filter design that achieves this space lower bound, but it appears too complicated to use in practice.
2.2 LEARNED BLOOM FILTER
Learned Bloom filters make use of learned models to beat the theoretical space bounds. Given learned model that can distinguish between keys and non-keys, learned Bloom filters use it as a pre-filter before using backup Bloom filters. The backup Bloom filters can be any variant including the standard, cuckoo, XOR filters, etc. If the size of the model is sufficiently small, learned models can be used enhance the performance of any Bloom filter variant.
3

---

Published as a conference paper at ICLR 2021
We provide the framework for learned Bloom filters. We given set of keys S = {x1, T2, ... znl from a universe U for which to build a Bloom filter. We are also given a sample of the non-keys Q which is representative of the set U - S. Features that can help in determining if an element is member of S are determined. The learned model is then trained on features of set U Q for a binary classification task and produces a score s(x) [o, 1.. This score s(x) can be viewed (intuitively, not formally) as the confidence of the model that the element I' is in the set S. So, a key in $ would ideally have a higher score value than the non-keys. An assumption in this framework is that the training sample distribution needs to match or be close to the test distribution of non-keys; the importance of this assumptions has been discussed at length in [Mitzemmacher (2018)). For many applications, past workloads or historical data can be used to get appropriate non-key sample.
As discussed above, |Kassk et al. [018)] set a threshold & and inputs satisfying s(x) > are classified as a key. A backup Bloom filter is built for just the keys in S satisfying s(x) S t. This design represented in [i.. [Mitzenmacher (2018)) proposes using another Bloom filter before the learned model along with a backup Bloom Filter. As the learned model is used between two Bloom filters as shown in Fig BB), this is referred to as the 'sandwiching" approach. They also provide the analysis of the optimal false positive rates for a given amount of memory for the two Bloom filters (given the false negative rate and false positive rate for the learned model, and the corresponding threshold). Interestingly, the sandwiching approach and analysis can be seen special case of our approach and analysis, as we describe later in Appendix [D.] (Dai & Shrivastava (2019)] use multiple thresholds to partition the score space into multiple regions and use backup Bloom filter for each score region. They propose heuristics for how to divide up the score range and choose false positive rate per region.
PARTITIONED LEARNED BLOOM FILTER (PLBF)
3.1 DESIGN
As discussed before, the general design segments the score space into multiple regions using multiple thresholds, as shown in Fig[]Cr and uses separate backup Bloom filters for each region. We can choose different target false positive rates for each region" The parameters associated with each region are its threshold boundaries and its false positive rate. Setting good values for these parameters is crucial for performance. Our aim is to analyze the performance of the learned Bloom filter with respect to these parameters, and find methods to determine optimal or near-optimal parameters.
The following notation will be important for our analysis. Let (()) be the fraction of keys with scores falling below We note that since the key set is finite, Gtt) goes through discrete jumps. But is helpful (particularly in our pictures) to think of G(t) as being continuous function, corresponding to a cumulative probability distribution, with a corresponding "density" function g(t). For non keys, we assume that queries involving non-keys come from some distribution D, and we define H(t) to be probability that a non-key query from D has a score less than or equal to t. Note that non key query distribution might be different from non key distribution. If non key queries are chosen uniformly at random, non key query distribution would be the same as non key distribution. We assume that (L) is known in the theoretical analysis below. In practice, we expect a good approximation of (() will be used, determined by taking samples from D or a suitably good approximation, which may be based on, for example, historical data (discussed in detail in [Mitzenmacher (2018))). Here H (t) can be viewed as cumulative distribution function, and again in our pictures we think of it as having a density (t).. Also, note that if queries for non-keys are simply chosen uniformly at random, then (t) is just the fraction of non-keys with scores below t. While our analysis holds generally, the example of (1) being the fraction of non-keys with scores below i may be easier to keep in mind. Visualization of the original learned Bloom filter in terms of these distributions is shown in Fig DD).
As we describe further below, for our partitioned learned Bloom filter, we use multiple thresholds and separate backup Bloom filter for each region, as show in Fig [E). In what follows, we formulate the problem of choosing thresholds and backup Bloom filter false positive rates (or equivalently, sizes) as an optimization problem in section 3.2 In section 3.3. we find the optimal solution of relaxed problem which helps us gain some insight into the general problem. We then propose an approximate solution for the general problem in section 3.3.3
The different false positive rates per region can he achieved in multiple ways. Either by choosing separate Bloom filter per region or by having common Bloom filter with varying number of hash functions per region.
4

---

Published as a conference paper at ICLR 2021
We find in our formulation that the resulting parameters correspond to quite natural quantities in terms of G and H. Specifically, the optimal false positive rate of region is proportional to the ratio of the fraction of keys to the fraction of non-keys in that region. If we think of these region- fractions for keys and non-keys as probability distributions, the maximum space saving obtained is proportional to the KL divergence between these distributions. Hence we can optimize the thresholds by choosing them to maximize this divergence. We show that we can find thresholds to maximize this divergence, approximately, through dynamic programming. We also show that, naturally, this KL divergence increases with more number of regions and so does the performance. In our experiments, we find small number(=* 4 6) of partitions suffices to get good performance.
3.2 GENERAL OPTIMIZATION FORMULATION
To formulate the overall problem optimization problem, consider the variant which minimizes the space used by the Bloom filters in PLBF in order to achieve an overall target false positive rate (F). We could have similarly framed it minimizing the false positive rate given fixed amount of space. Here we are assuming the learned model is given.
We assume normalized score values in [0, 1] for convenience. We have region boundaries given by i values 0 = to S 4 S -..Ik-1 S t 1, with score values between [[:-1,4] 4 falling into the 7t region. We assume the target number of regions & is given. We denote the false positive rate for the Bloom filter in the jth region by f;- We let G and be defined as above. As state previously, Fig I EE) corresponds this setting, and the following optimization problem finds the optimal thresholds 4 and the false positive rates fi:
EE
|S] (G(L)) G(t+-1)) x clog2 (t)))
min f.fi
Size of Learned Model
(2)
constraints
Σ
HH (4) - H((;-1)) x S F
(3)
$ 11 1..k
(4)
(t, f 2 1 to
0,
(5)
The minimized term (Eq(2) represents the total size of the learned Bloom filter, the size of backup Bloom filters is obtained by summing the individual backup Bloom filter sizes. The constant in the equation depends on which variant of the Bloom filter is used as the backur as it happens, its value will not affect the optimization.
The first constraint (Eq()) ensures that the overall false positive rate stays below the target F. The overall false positive rate is obtained by summing the appropriately weighted rates of each region. The next constraint 4 encodes the constraint that false positive rate for each region is at most 1. The last set of constraints 5 ensure threshold values are increasing and cover the interval [o, 1].
3.3
SOLVING THE OPTIMIZATION PROBLEM
3.3.1 SOLVING RELAXED PROBLEM
If we remove the false positive rate constraints (Eq giving f: S 1), we obtain relaxed problem shown in 6 This relaxation is useful because it allows to use the Karush- Kuhn-Tucke (KKT) conditions to obtain optimal fi values in terms of the t, values, which we used to design algorithms for finding near-optimal solutions. Throughout this section, we assume the the relaxed problem yields a solution for the original problem; we return to this issue in subsection 3.3.3
E |S| (G(t:) G(t:-1)) clog2 (1))) + Size of Learned Model
min f=2...k 1
constraints
Σ (Hat)) H(: f F; (t: 4-1
k. to tz
(6)
'The sizes of Bloom filter variants are proportional to |S| x log, (1/f), where S is the set it represents, and f is the false positive rate it achieves. See e.g. (Mitzenmacher (2088 for related discussion. The constant depends on which type of Bloom filter is used as backup. For example, logz(e) for standard Bloom filter.
5

---

Published as a conference paper at ICLR 2021
The optimal fi values obtained by using the KKT conditions yield Eq (as derived in Appendix A giving the exact solution in terms t s.
G(tt)-Gitt J (IG)) ((6))-((-1)
The numerator ((t,) ((1,-1) is the fraction of keys in the ith region and the denominator (t,) (tt---1) is the probability of non-key query being in the ith region. In intuitive terms, the false positive rate for a region is proportional to the ratio of the key density (fraction of keys) to non-key density (fraction of non-key queries). Since we have found the optimal fi in terms of the ts. we can replace the f. in the original problem to obtain a problem only in terms of the 4. In what follows, use g(t) to represent the discrete distribution given by the k values of G(t,) G(t+-1) for I..... k, and similarly we use h(t) for the distribution corresponding to the (t.) - H (t,1)) values. Eq shows the rearrangement of the minimization term(excluding model size) after substitution.
H(4+) 11 (ti-i)) (G(L)) G((+-1)) x
Min. Term-
Σ |S| (G(L)) G(l=-1)) x clogge
(8)
Σ S x (G(t+) - G(t+-1)) x clogs
- cx |S| x DEL h(t)
where DKr. is the standard KL divergence for the distributions given by g(t) and lt(t)
B represents the space occupied by the backup Bloom filters; the total space includes this and the space occupied by the learned model.
c (IS) log2 (+) (S] DKL ((t)),(()) + Size Of Learned Model
(9)
The space occupied by the Bloom filter without the learned model is c x |S] x (1gE( Thus, the space saved by PLBF in comparison the normal Bloom filter is:
c x (Is) x DKL (o(t),(t) Size Of Learned Model
(10)
The space saved by PLBF is therefore linearly proportional to the KL divergence of key and non-key distributions of the regions given by gt) and ht(t) of the regions.
This derivation suggests that the KL divergence might also be used as a loss function to improve the model quality. We have tested this empirically, but thus far have not seen significant improvements over the MSE loss we use in our experiments; this remains an interesting issue for future work.
3.3.2 FINDING OPTIMAL THRESHOLLDS FOR RELAXED PROBLEM
We have shown that, given set of thresholds, we can find the optimal false positive rates for the relaxed problem. Here we turn to the question of finding optimal thresholds. We assume again that we are given k the number of regions desired. (We consider the importance choosing & further in our experimental section.) Given results above, the optimal thresholds correspond to the points that maximize the KL. divergence between (t( (()). The KL divergence of (g(t), h(t)) is the sum of the terms 9i log2 h2 one term per region. (Here = G(ta) G(t:-1) and h Ht,)) H (t:-1).) Note that each term depends only on the proportion of keys and non-keys in that region and is otherwise independent of the other regions. This property allows a recursive definition of KL divergence that suitable for dynamic programming.
Si
We divide the score space [0, 1] into N consecutive small segments for chosen value of N; this provides us a discretization of the score space, with larger N more closely approximating the real interval. Given k. we can find a set of k approximately optimal thresholds using dynamic programming, where the solution is approximate due to our discretization of the score space. Let DPKi(n,j) denote the maximum divergence one can get when you divide the first n segments into j regions. Our approximately optimal divergence corresponds to DP (P. A). The idea behind the algorithm is that the we can recursively define DP (n, as represented in Eq [1 Here g' h' represent the fraction of keys and the fraction of non-key queries, respectively, in these N segments.

---

Published as a conference paper at ICLR 2021
n Σ log2
Pe (m.j) = max
1)+
(II)
The time complexity of computing DP is (()2k). One can increase the value of N to get more precision in the discretization when finding thresholds, at the cost of higher computation time.
3.3.3 THE RELAXED PROBLEM AND THE GENERAL PROBLEM
We can find near-optimal solution to the relaxed problem by first, obtaining the threshold values that maximize the divergence and then, getting the optimal fa values using Eq 7 In many cases, the optimal relaxed solution will also be the optimal general solution, specifically if F (G(t,-1) (tt,)) (t.)) < 1 for all i. Hence, if we are aiming for a sufficiently low false positive rate F, solving the relaxed problem suffices.
To solve the general problem, we need to deal with regions where f; 2 1, but we can use the relaxed problem as a subroutine. First, given a fixed set of i; values for the general problem, we have an algorithm (Alg [ as discussed in Appendix B to find the optimal fi's, Briefly summarized, we solve the relaxed problem, and for regions with ft > 1, the algorithm sets fi 1, and then re-solves the relaxed problem with these additional constraints, and does this iteratively until region with fi >> 1 remains. The problem is that we do not have the optimal set of t, values to begin; as such, we use the optimal t; values for the relaxed solution as described in Section B.3.2] This yields solution to the general problem (psuedo-code in Alg2. but we emphasize that it is not optimal in general, since we did not start with the optimal 44. We expect still that it will perform very well in most cases.
In practice, we observe that keys are more concentrated on higher scores, and non non-key queries are more concentrated on lower scores. Given this property, if region with Si (no backup Bloom filter used) exists in the optimal solution of the general problem, it will most probably be the rightmost region. particular, if (G((t-1)- is, the ratio of the fraction of keys to the fraction of non non-key queries over regions is increasing then indeed without loss of generality the last (kth) region will be the only one with f& 1. (We say only one region because any two consecutive regions with fi = 1 can be merged and an extra region can be made in the remaining space which is strictly better, as adding an extra region always helps as shown in Appendix D.2) It is reasonable to believe that in practice this ratio will be increasing or nearly so.
(t+)) increasing as f t, increase that
Hence if we make the assumption that in the optimal solution all the regions except the last satisfy the ft < 1 constraint, then if we identify the optimal last region's 's boundary, we can remove the f. < 1 constraints for i * A and apply the DP algorithm to find near optimal t, 's. To identify the o optimal last region's 's boundary, we simply try all possible boundaries for the kth region (details discussed in Appendix C As it involves assumptions on the behavior of G and H, we emphasize again that this will not guarantee finding the optimal solution. But when the conditions are met it will lead to a near-optimal solution (only near-optimal due the discretization of the dynamic program).
4 EVALUATION
We compare PLBF against the theoretically optimal Bloom filter (Bloom| 1970) 4 the sandwiching approach [Mitzenmacher (2018)), and AdaBF DDai Shrivastava (2019)) Comparisons against standard Bloom filter appear in Appendix E. We excluded the original learned Bloom filter [raska et al. [2018) as the sandwiching approach was strictly better. We include the size of the learned model with the size of the learned Bloom filter. To ensure fair comparison, used the optimal Bloom filter as the backup bloom filter for all learned variants. We use different datasets:
URLs: As in previous papers Kraska et al. (018)) Dai & Shrivastava 2019h], used the URL data set, which contains 103520 (23%) malicious and 346646 (77%) are benign URLs. We used 17 features from these URL's such as host name length, use of shortening, counts of special characters.etc.
Forr the space of theoretically optimal Bloom filter, take the standard Bloom filter of same false positive rate and divide it's space used by log, e, obtaining near-optimality in practice difficult. This the fact that the standard Bloom filter asymptotically log, e times suboptimal than the optimal as discussed Sec 2.T $ BP.BF performs hetter against standard Bloom filters, as discussed in Appendix D.3 Section 4.1 conservative estimates of gains possible in practice using a PL.B.
7

---

Published as a conference paper at ICLR 2021
[h!]
37
Optinel Socc fhr Adae
30
190 Oplera Suues
Srauelle Aeprash N3Y
False Positive Rate
False Posiiive Rate
False Positive Rate
Better
Better
Batter
Space Usedlin Kbj
1200
4a0 vie Space Usedtin Kb)
3008
Space Used(in Kb)
Key
(A) Symthetic
Non-Key
Key
URLs
Non-Key
Kay
EMBER
Non- Non-Key
Spece Seved (In KD)
Space Saved (In Kb)
1200
Space Saved (in
1000
603-
323
PLBF with 25 regions
PLOT with regions
322
PLBP
Number of Regions (K)
Number of Regions (K)
Number of Regions (F) EMBER
(D) Synthelic
(E) URLs
Figure 2: FPR vs Space for the (A) Synthetic (B) URLs (C) EMBER datasets for various baselines along with key and non-key score distributions. Space Saved as we increase number of regions for the (D) Synthetic (E)
URLs (F) EMBER datasets for PLBF compared to the optimal Bloom filter
Bloom filters are widely used to match file signatures with the virus signature database. Ember (Endgame Malware Benchmark for Research) [Anderson & Roth (2018) is open source collection of 1.IM sha256 file hashes that were scanned by VirusTotal in 2017. Out of the 1.1 million files, 400K are malicious, 400K are benign, and we ignore the remaining 300K unlabeled files. The
EMBER:
features of the files are already included in the dataset.
Synthetic:
An appealing scenario for our method is when the key density increases and non-key density decreases monotonically with respect to the score value. We simulate this by generating the key and non-key score distribution using Zipfian distributions as in [.g Since we directly work on the score distribution, the size of the learned model for this synthetic dataset is zero
4.1 OVERALL PERFORMANCE
Here, we compare the performance of PLBF against other baselines by fixing the target F and measuring the space used by each methods. We use PLBF Alg with DP algorithm discretization(N) set to 1000. We train the model on the entire key set and 40% of the non-key set. The thresholds and backup Bloom filters are then tuned using this model with the aim of achieving the fixed target F. The rest of the non-keys are used to evaluate the actual false positive rate.
While any model can be used, we choose the random forest classifier from sklearn (Pedregosa et for its good accuracy. The Fl scores of the learned models used for synthetic, URLs and EMBER were 0.99, 0.97, and 0.85, respectively. We consider the size of the model be the pickle file size on the disk (a standard way of serializing objects in Python). We use five regions (k 5) for both PLBF and AdaBF as this is usually enough to achieve good performance as discussed in Using higher l would only improve our performance.
The results of the experiment are shown in the Fig 2ig2.0 A-C) along with the distribution of the scores of keys and non-keys for each dataset. As we can see from the figure, PLBF has better Pareto curve than the other baselines for all the datasets. On the synthetic dataset and URLs dataset we observe a significantly better performance, In contrast, for the EMBER dataset our performance is only slightly better indicating that the model here is not as helpful. The difference between space used by PLBF and optimal Bloom filter first increases with decreasing false positive rate but converges to constant value for all datasets, as given in Eq [0 For the same amount of space used space for synthetic, URI.s EMBER, respectively), PLBF achieves 22x, 26x, and 3x smaller false .MBER,
8

---

Published as a conference paper at ICLR 2021
positive rates than the sandwiching approach, and 8.5x, 9x, and 1.9x smaller false positive rates than AdaBF for synthetic, URLs, and EMBER, respectively. To achieve a false positive rate 0.001, the sandwiching approach uses 8.8x. 3.3x, and 1.2x the amount of space and AdaBF uses 6x, 2.5x, and 1.1x the amount of space compared to PLBF for synthetic, URLs, and EMBER datasets respectively.
4.2 PERFORMANCE AND THE NUMBER OF REGIONS
The maximum space savings obtained by using PLBF is linearly proportional to the KL diver- gence of the (estributions(F(T1 and this KI. divergence strictly increases with the number of regions(Appende) D.2p. 2 (DF) show the space saved w.r.t the optimal Bloom filter as we increase the number of regions for target false positive rate of 0.001. The red line in the figure shows the savings when using 25 regions; using more regions provides no noticeable improvement on this data. Our results suggest using 4-6 regions should be sufficient to obtain reasonable performance. We have additional experiments in Appendix that shows PLBF performance against standard Bloom filters and PLBF performance w.r.t model quality.
CONCLUSION
Our analysis of the partitioned learned Bloom filter provides formal framework for improving on learned Bloom filter performance that provides substantially better performance than previous heuristics. As Bloom filters are used across thousands of applications, we hope the PLBF may find many uses where the data set is amenable to a learned model.
Acknowledgments
This research was supported in part by NSF grants CCF-1563710 and CCF-1535795, and by a gift to the Center for Research Computation and Society Harvard University.

---

Published as a conference paper at ICLR 2021
REFERENCES
Hyrum S. Anderson and Phil Roth. Ember: An open dataset for training static pe malware machine learning models, 2018.
Burton H. Bloom. Space/time trade-offs in hash coding with allowable errors. Commun. ACM, 13(7):422-426, July 1970. ISSN 0001-0782. doi: 10.1145/362666.662222. URL https
bloom filter. Python bloom filter. URL UtL/tttpss//ppp...r///p////////p
Prosenjit Bose, Hua Guo, Evangelos Kranakis, Anil Maheshwari, Pat Morin, Jason Morrison, Michiel Smid, and Yihui Tang. On the false-positive rate of bloom filters. Information Processing Letters, 108(4):210-213, 2008.
Alex D. Breslow and Nuwan Jayasena. Morton filters: Faster, space-efficient euckoo filters via biasing, compression, and decoupled logical sparsity. Proc. VLDB Endow. 11(9):1411-1055 May 2018. ISSN 2150-8097. doi: 10. 11878//311880.321111 URL inttps://dee wtt.//o.oooo///1/
14778/3213 3213880 3213884
Andrei Z. Broder and Michael Mitzemmacher. Survey: Network applications of bloom filters: A doi: 10. https://doi.oom /00 1080 0et.:1000111222110 54759422111.1 2004. 00129996
survey. Internet Math., 1(4):485-509, 2003.
URL
Jehoshua Bruck, Jie Gao, and Anxiao Jiang. Weighted bloom filter. In Proceedings 2006 IEEE International Symposium Information Theory, ISIT 2006, The Westin Seattle, Seattle, Washing- ton, USA, July 9-14, 2006, pp. 2304 2308. IEEE, 2006. doi: 10. 10.11099//T.22002261998 URL https: doi org. 10 110111119110011 ISIT 2006. 221978861888
Zhenwei Dai and Anshumali Shrivastava. Adaptive learned bloom filter (ada-bf); Efficient utilization of the classifier. arXiv preprint 1910009110091133 2019.
Niv Dayan, Manos Athanassoulis, and Stratos Idreos. Optimal bloom filters and adaptive merging for Ism-trees. ACM Trans. Database Syst., 43(4). December 2018. ISSN 0362-5915. doi:
10. 10.1145/3276980. URL https: org 10
Peter C. Dillinger and Panagiotis Manolios. Bloom filters in probabilistic verification. In Alan J. Hu and Andrew K. Martin (eds.), Formal Methods Computer-Aided Design, Sth International Confer- ence, FMCAD 2004, Austin, Texas, USA, November 15-17, 2004, Proceedings, volume 3312 of Lec- ture Notes in Computer Science, pp. 367 Springer, 2004. doi: 10. 1007/9777 3-588-3-3-0----0 3-540-33044 (000000444-44 _26. URL https:///o. www.oogg//.0... 100000009900 3 540 30494-44222
Bin Fan, Dave G. Andersen, Michael Kaminsky, and Michael D. Mitzenmacher. Cuckoo filter: Practically better than bloom. In Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies, CoNEXT 14, pp. 75-88, New York, NY, USA, 2014. Association for Computing Machinery. ISBN 9781450332798.. doi: 10.1145/2674005. 2674994. URL htt.ttttt:///otm www.aoo.....o..ooooooooooooo...e 1ttp://...111122571101 2674499945022299994
Thomas Mueller Graf and Daniel Lemire. Xor filters. ACM Journal of Experimental Algorithmics, 25(1):1-16 Jul 2020. ISSN 1084-6654, doi: 10.1145/337612.. URL http: doi. ado..ooe org 10. 2
Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. In Proceedings the 2018 International Conference on Management of Data, SIGMOD 18, pp. 489-504. New York, NY. USA, 2018. Association for Computing Machinery. ISBN 4784403477377. doi: 10.1145/31837133319690 31 3183713 96909
Michael Mitzenmacher. Compressed bloom filters. IEEE/ACM Trans. Netw., 10(5):604-612. 2002. doi: 10.11099TNET.22222533344, URL BRL/httss::/dbl www.:ii..rrr100 1109 2002 803864
10

---

Published as a conference paper at ICLR 2021
Michael Mitzenmacher. A model for learned bloom filters and optimizing by sandwich- ing. In S. Bengio, H. Wallach, H. Larochelle. K. Grauman, N. Cesa-Bianchi and
R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 464 473. Curran Associates, Inc., 2018. URL http:/ /tapers/ppprs.oom httppperr..iis.cc..eeeeee 328-a-model-foo lear-leerned-bbbe wwoeedd--oooo---oo filters wwwtterr-add-pttiieae by
pdf
Michael Mitzenmacher, Salvatore Pontarelli, and Pedro Reviriego, Adaptive cuckoo filters.
Exp. Algorithmics, 25(1), March 2020. ISSN 1084-6654. doi: 10. 10.1145/3339504 URL https
Anna Pagh, Rasmus Pagh, and Srinivasa Rao. An optimal bloom filter replacement. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '05, pp. 823-829, USA, 2005. Society for Industrial and Applied Mathematics. ISBN 0898715857.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion. O. Grisel. M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-288 2830.
Jack Rae, Sergey Bartunov, and Timothy Lillicrap. Mean-nga neural bloom filters. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 5271-5280, Long Beach, California, USA, 09-15 Jun 2019. PMLR. URL http:::/://prr/eeee/
mlr
Exess/v97/rae1
Minmei Wang, Mingxun Zhou, Shouqian Shi, and Chen Qian. Vacuum filters: More space-efficient and faster replacement for bloom and cuckoo filters. Proc. VLDB Endow, 13(2)117-210,, October 2019. ISSN 2150-8097.
doi: 10.14778/336424.333333 URL /ttttss://oii..rr/////
14776/3364324.336 3364333
A SOLVING THE RELAXED PROBLEM USING KKT CONDITIONS
As mentioned in the main text, we relax the constraint of fa S 1, using the stationary KKT conditions we can obtain the optimal fa values. Here we show this work. The appropriate Lagrangian equation is given in [2 [2 this case, the KKT coniditions tell us that the optimal solution is a stationary point of the Lagrangian. Therefore, we find where the derivative of the Lagrangian with respect to fi is zero.
L [t,, A,) Et (G(tt) - G(ti-1)) clog2 (1)) + Axx (Ci= (H((.) ((t+-1)) 81) -F) +
Σ V/ X (t;-1 - tx)
(12)
(13)
8/.
G(t ())-:)))00 1ogz
(+)
((H(bs) - Mx
(14)
0/.
A
(15)
H((1)-)((--))
X 2ln(2)x (G(t.) G(t--1))
(16)
clu2
ft (G(t)) JPR
(17)
H(())-((-)))
exprresss for; in terms of A. Summing Eq 13 over all and using the relationship between F and H get Eq 16 Thus the optimal ʃa values turn out be given in Eq 17
11

---

Published as a conference paper at ICLR 2021
Algorithm Finding optimal fpr's given thresholds
Imput G" the aray containing key density of each region
Input H/ army containing non key density each region
Input F- -targget overall false positive rate
Input numberr of regions
Output f the aray of false posstive rate of each region
1: procedure OPTMALFPRIG", H',
2: Gaum +-
b- sum of key density of regions with f sum of non-key density regions with fi
3: Haum
4:
for in 1, ...k do
5:
[[A] [P]
G'(x)FF
Assign relaxed problem
6:
white some flil
7:
for i in 1. 2.....k do
8:
(f
then f[
P Cap false positive rate of region one
9:
Gaum f-
10:
Haum
11:
for in k..
12:
if(](i]]
Goum Gram + (i]: Hoam Houm [+) Calculate key.non key density regions
with no Bloom (ilter((]]
13:
For in 1, k do
14:
if(( < then f[1]
G' Haum) H6 Gaum) Modifying the f: regions ensure target false positive rate is
15:
return for Ammy
Algorithm 2 Using relaxed solution for the general problem
Imput Gata the arry containing discretized key demsity of euch region Input Hais the army containing discretized key density each region Input F- target overall false positive rate
Input number of regions
Output (- the arry of thresbold boundaries of each region Output f the army of false positive rate each region
Algorithum ThresMaxDivDP DP algorithm that returns the thresholds maximicing the divergence between and non-key distribation. Algorilhu CaleDensity returms the region demsity given thresholds of regions
Algorithm OptimalFPR returns optimal false positive mit of the regions thresholds
Algorithm SpaceUsed returns space used by the back-up Bloom filters given thrchsolds and false positive rate per region.
1: procedure SoLvE(G Maiv: F.
2:
ThresMaxDivDP (Gai Hav., k)
P. Getting the optimal thresholds relaxed problem
3:
G', H' CaleDensity (aaanssstyyGyaaaaaaa Hase.
4:
f OptimalFPR(GG H', FF.)
D Obtaining optimal false positive rales the general problem for given thresholds
5:
6:
return f. Array
B OPTIMAL FALSE POSITIVE RATE FOR GIVEN THRESHOLDS
We provide the pseudocode for the algorithm to find the optimal false positive rates if threshold values are provided. The corresponding optimization problem is given in T8 As the boundaries for the regions already defined, one only needs to find the optimal false positive for the backup Bloom filter of each region.
min fisn...k
- G(4-1)) x clogg(+))
(18)
constraints
Σts (H(I)) H(4- f== A5li= L...k
Alg gives the pseudocode. We first assign false positive rates based on the relaxed problem but may find that fi > for some regions. For such regions, we can set f; 1, re-solve the relaxed problem with these additional constraints (that is, excluding these regions), and use the result as a solution for repeat
the general problem. Some regions might again have false positive rate above one, the process. The algorithm stops when there is no new region with false positive rate greater than one. This algorithm finds the optimal false positive rates for the regions when the thresholds are fixed.
12

---

Published as a conference paper at ICLR 2021
Algorithm 3 Solving the general problem
Input Gata the array containing discretized key density each region
Input Has. - the aray containing discretized koy density of each rogion Input F- larget overall false positive rale
Input number of regions
Output (- the urray of threshold boundaries of each region Output f- the arry
positive
each region
Algorithm ThresMaxDDvDDP DP algorithm that returns the thresholds maximizing the divergence hetween key and non-key distribution. Algorithm CaleDensity - returns the region donsity given thresholds regions
Algoritium OptimalFPR returns the optimal false positive rate of the regions given thresbolds
1: procedure SOLVE Haivi F.
2: S sed + 0c
D Stores minimum space used uptil now corresponding to
3: inder
space Key density of the current last region Non-key density of the current last region
4: Giast
5: Hinst +
6:
7:
for in I. do
D. Iterate over possibilities last region Calculate the key donsity last region
8:
Giazt ΣN Ge
9:
Hiast + Ez=i Hes bil
10:
t ThesMMxDDDDD(G(1... 13], H(I..(t 1)], Lappendls)
Find the optimal thresholds for the rest of the array
12:
G',H'' + CaleDensiyy H)...)
13:
f= OptimaltPR(G"" H', F.
D Find optimal false positive rates for the current configuration
14:
iraMin sed Spweeueed Hais b, f))
15:
then M MinSpacelUsaa sed t- SpaceUUsed(Gavaa Haiss bo inide e-
b. Remember the best performance uptil now
16:
17:
Giast < Ex Ga
18:
Haase +- Ez Ez-indez Has Lil
19:
MinesMaDDiDDPG(I....ii. Lappend(iaded
1)), (inder 1)}, k
20:
21:
H' + CaleDensity (GaiiyyGGainn Hairit)
22:
I= OptimllPRR H', F,k)
23:
24:
return 1, f.f Arra
C ALGORITHM FOR FINDING THRESHOLDS
We provide the pseudocode for the algorithm find the solution for the relaxed problem: Alg finds the thresholds and false positive rates. As we have descrihed in the main text, this algorithm provides the optimal parameter values, if (G(t,-1) (()-)) (t+)) is monotonically increasing.
The idea is that only the false positive rate of the rightmost region can be one. The algorithm receives discretized key and non-key densities. The algorithm first iterates over all the possibilities of the rightmost region. For each iteration, it finds the thresholds that maximize the KL divergence for the rest of the array for which a dynamic programming algorithm exists. After calculating these thresholds, it finds the optimal false positive rate for each region using Alg I After calculating the thresholds and false positive rates, the algorithm calculates the total space used by the back-up Bloom filters in PLBF. It then remembers the index for which the space used was minimal. The 4 and fi's corresponding to this index are then used to build the backup Bloom filters. The worst case time complexity is then (NN
D ADDITIONAL CONSIDERATIONS
D. SANDWICHING: A SPECIAL CASE
We show here that the sandwiching approach can actually be interpreted as a special case of our method. In the sandwiching approach, the learned model is sandwiched between two Bloom filters as shown in Fig 3(A) A). The input first goes through Bloom filter and the negatives are discarded. The positives are passed through the learned model where based their score s(x) they are either directly accepted when s()) > t or passed through another backup Bloom filter when s(x) < t. In setting, we note that the pre-filte fre-filter in the sandwiching approach can be merged with the backup filters to yield backup filters with a modified false positive rate. 3 shows what an equivalent design with modified false positive rates would look like. (Here equivalence means obtain the
13

---

Published as a conference paper at ICLR 2021
same false positive rate with the same bit budget; we do not consider compute time.) Thus, that the sandwiching approach can be viewed as a special case of the PLBF with two regions.
However, this also tells we find when constructing a PLBF with & regions that fi < for all we may assign fo maxigisk fi- We may then target false positive rates for all other intervals to fi/ while keeping the same bit budget. This approach will be somewhat more efficient computationally, as we avoid computing the learned model for some fraction of non-key elements.
make the PLBF more efficient by using sandwiching. Specifically,
initial Bloom filter with false positive rate for and change the
Input (x)
Input (x)
Bloom filter
Negative
fpr
Learned Model
Postive
s(x) st
s(x)
Learned Model
s(x) st
s(x) t
Bloom filter
Bloom filter fpr
Bloom filter
Postive
fpr, fpr,
fpr,
Negative
Postive
Negative
Postive
Negative
Postive
(A)
(B)
Figure 3: (A) represent LBF with sandwiching. represents PLBF design equivalent to the sandwiching approach.
D.2 PERFORMANCE AGAINST NUMBER OF REGIONS k
Earlier, we saw the maximum space saved by using PLBF instead of normal Bloom filter is linearly proportional to the D (tt),, (t) If we split any region into two regions, the overall divergence would increase because sum of divergences of the two split regions always more than the original divergence, as shown in Eq 19 Eq 19 is an application of Jensen's 's inequality.
(01 + 92) x log (ox+ (h1+ha)
[1 x log #
+ (g2
x log
02
(19)
Tig
Increasing the number regions therefore always improves the maximum performance. We would hope that in practice a small number of regions k would suffice. This seems to be the the case in experience; we detail one such experiment in our evaluation(4.2)
D.3 PERFORMANCE USING VARIOUS BLOOM FILTER VARIANTS
consider how the space saved of the PLBF varies with type of backup Bloom filter being any Bloom filter variant the backup Bloom filter. When compare our
used. The PLBF performance with Bloom filter variant, we use that same Bloom filter variant as the backup Bloom filter for fair comparison.
First, absolute space one can save by using a PLBF instead of a Bloom filter variant is given in Eq 10 This quantity increases with increasing
'The sizes of standard Bloom filter variants are proportional to |S] log, (1/f), where S is the set represents, and f is the false positive rate it achieves. See e.g. Mitzennacher (2018) for related discussion. The constant depends on which type of Bloom filteria is used as backup. For example, log,(e) for standard Bloom filter, 1.0 for the optimal Bloom filter.
14

---

Published as a conference paper at ICLR 2021
The relative space saves by using PLBF instead of the given Bloom filter variant is shown in Eq 20 This quantity is the ratio the space saved by PLBF (as shown Eq 10 divided by the space used by the given Bloom filter variant (c [S| x (1/F( as shown in Eq 20
[ex|S)x (o(O), ex (1/5))
Size Of Leurned Model)
(20)
Cancelling the common terms we obtaín the following Eq Eq
Dic (ic((((),AO)) (1/F(1
Learned Model ox [S] (ogg(
(21)
The relative space saved, like the absolute space saved, also increases with increasing c. Thus, both the relative and absolute space saved for the PLBF is higher for a standard Bloom filter (c 1.44) than an optimal Bloom filter (c = 1.00), and hence our experiments in Section are conservative estimates of gains possible in practice using PLBE
E ADDITIONAL EXPERIMENTS
E.1 PERFORMANCE W.R.T STANDARD BLOOM FILTERS
Earlier, we evaluated our performance using optimal Bloom filters and here we present results using standard Bloom filters. As shown in Appendix D.3 PLBF performs better w.r.t standard Bloom filters than optimal Bloom filters. As one can see from Fig PLBF performs better than the standard Bloom filter.
aenocitingg Aauracc
Sendwccing Agpaet
False Positive rate
Faloe Posilive nate
Possivve
Better
Better
Better
30
46
Space Usedlin Kb)
eie
we
1280
Space Used(in Kb)
ein Space Usedjin Kb)
Key
Non-Key
Key
Non-Key
Key
Non-Key
(A) Synthetic
(B) URLs
(C) EMBER
Figure 4: FPR vs Space for the (A) Synthetic (B) URLs (C) EMBER datasets for various baselines along with key and non-key score distributions.
E.2 PERFORMANCE AND MODEL QUALITY
Here we provide an experiment to see how the performance various methods varies with the quality of the model. As discussed earlier, a good model will have high skew of the distributions g and towards extreme values. We therefore vary the skew parameter of the Zipfian distribution to simulate the model quality. We measure the quality of the model using the standard F1 score. Fig 5 represents the space used by various methods to achieve a fixed false positive rate of 0.001 as we vary the Fl score of the model. The figure shows that as the model quality in terms of the Fl score increases, the space required by all the methods decreases (except for the optimal Bloom filter, model). The space used by all the methods goes to 1, as for the synthetic dataset there is no space cost for the model. The data point corresponding to Fl score equal to 0.99 was used to plot Fig 2
which does
the Fl score goes to
15

---

Published as a conference paper at ICLR 2021
1000
x
Space Used(in Kb)
600
Optimal Bloom filter
Sandwiching Approach
200
AdaBF
PLBF
0.84
0.86
0.88
0.90
0.92
0.94
0.96 0.98 1.00
F1 score
Figure 5: Space used by various baselines as we increase Fl score for Synthetic dataset
E.3 DISCRETIZATION EFFECT ON DYNAMIC PROGRAMMING RUNTIME, PLBF SIZE
All the runtime experiments in this subsection and the next subsection are measured using an 2.8GHz quad-core Intel Core i7 CPU 2.80GHz with 16GB of memory. We use the bloom-filter python package (bloom filter) for our backup Bloom filters. The dynamic programming algorithms are implemented in Python.
how the dynamic programming (DP) algorithm runtime (psuedo code in Alg 3 and PLBF size vary with level of discretization (N). In the tables below, we have the DP algorithm runtime and space taken by the PLBF to achieve approximate empirical false positive rate of 0.001 for various N. As discussed in Sec. 3.3.2 with increasing value of one gets closer optimal parameters, the cost of higher computation time. This trend is demonstrated in the table below for the URLs and EMBER datasets. We note that if runtime is an issue, the increase in size from using smaller N relatively small.
Here provide experiment
DP Runtime(in sec)
PLBF Size (in Kb)
50
1.17
187.6
100
2.15
184.37
500
10.97
183.63
1000
26.94
183.55
2000
56.79
182.85
Table 1: DP runtime and space used by PLBF as we increase the discretization in the URLs dataset
N
DP Runtime(in sec)
PLBF Size (in Kb)
50
1.36
2952.33
100
2.52
2944.68
500
11.39
2933.09
1000
25.26
2928.76
2000
56.12
2926.79
Table 2: DP runtime and space used by PLBF as we increase the discretization N in the EMBER dataset
E.4 CONSTRUCTION TIME FOR VARIOUS BASELINES
Here we look at the construction time breakdown for the PLBF and various alternatives, with the goal of seeing the cost of in terms of construction time for using the more highly tuned PLBF. The construction time of all the learned Bloom filters includes the model training time and parameter estimation time, which
required for the standard Bloom filter construction process. Since
16

---

Published as a conference paper at ICLR 2021
use the same model for all learned baselines, the model construction time is the same for all of them. In Fig/6] we plot the construction time breakdown for various baselines in order to achieve an approximate empirical false positive rate of 0.001. Recall that the AdaBF and Sandwiching approaches use heuristics to estimate their parameters and unsurprisingly they therefore seems somewhat faster than PLBE. However, for N = 100 than the key insertion time and model training time. The parameter estimation time for PLBF varies with the level of discretization we for the DP algorithm. The PLBF with N 1000 takes the longest to execute while standard Bloom filter is fastest baseline. As shown in TableTabove using N 1000 gives only slight improvement in size. We therefore believe that if construction time an issue, for situations where one might want to re-learn and change the filter as data changes, one can choose parameters for PLBF construction that would still yield significant benefits over previous approaches.
the parameter estimation time is smaller
Key
Parameter Extimation Time
Model Training
30
Thw (In sec
20
PLBF(X-1000)
PLBF(N-500)
PLBF(N-100!
AdaBF
Sandwkhing
Standard BF
Baselines
Figure 6: Construction time breakdown for various basclines for the URLs dataset
17


Reviews:
[{"review_id": "SQDxMuUejI", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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 proposes a generalization of the sandwiched Bloom filter model that maintais a set of score partitions instead of just two and an algorithm for optimizing parameters of the partition under the target false-positive rate. Authors evaluate partitioned Bloom filter on three datasets and demonstrate that delivers better false positive rates under for a given model size compared to the baselines.\n\nI find the paper quite innovative and the experimental results impressive. My main concern is regarding the paper clarity.\n1. How can a region's FPR $f_i$ be greater than 1? Perhaps, this is something very obvious, but I couldn't get this immediately and perhaps some other readers might  struggle here too.\n2. The learned model size appears in the optimization objective, but is considered given. I wonder what will change if we allow to trade-off the learned model power for a larger number of regions and larger backup Bloom filters in each region? Does it even make sense to ask such a question? Would the results change if a different model is used? I think it is possible that for a given variant of a learned Bloom filter, a different model may result into different values of optimal parameters and a difference performance, thus these should ideally be optimized independently for each of the baselines. I also think that size of the pickle file is arguably not the best estimate for the learned model size if indeed a different model is used for each of the filters, e.g. a neural network might admit a decent compression rate if a lower precision number format is used etc. Thus, it is important to separate the impact made by a learned model from an algorithmic improvement.\n3. Is there any variance caused by observing particular distributions G and H? Is it small enough to ignore or confidence interals for each of the curves might actually overlap? I would also be interested in understanding behaviour of all considered models as the sample size changes.\n\nI also feel like authors can cite *Meta-learning neural Bloom filters. Rae et al, 2019* as it considers a relevant (although a different as well) setting.\n\nNevertheless, I think the kind of analysis presented in the paper very useful for the community and for further development of learned data structures. I recommend acceptance and I will gladly raise my rather conservative score if authors could clarify the points mentioned above.", "extra_scores": {}, "extra_text": {}}, {"review_id": "JZ9kl8xb-mr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "A clear exposition of the problem and proposed solution, the paper key strength is in the formulation of the partitioned bloom filter as an optimization problem that generalizes previously proposed architectures, and prescribes an interpretable solution for the choice of the optimal partition-thresholds in terms of the properties of the given learned model (specifically, its false-negative and true-negative threshold dependent curves). Furthermore, the experimental section clearly illustrates a significant advantage of the proposed method over state of the art alternatives. \nThe theoretical treatment, however may be considered as a first attempt at combining essential properties of a learned model and bloom-filter design - the paper could be improved by considering and motivating the usage of a particular lower bound for the space cost of a bloom filter and incorporating in the the optimization formulation the relation between the size of the learned model and the qualities of the false positive and false negative curves. The latter, especially, makes a significant practical difference since the model may be part of the design and assuming out the size-quality tradeoff results in a sub-optimal scheme and renders the overall proposed solution as a heuristic still.\n\nUpdate (Nov 30th) In light of the author's responses and the other reviews I increase my score for this paper to 7: Good paper, accept.", "extra_scores": {}, "extra_text": {}}, {"review_id": "-e0h7pw3BP2", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "\nThis work proposed a technique to fine tune the partitioned learned Bloom filter to reduce the space consumption given a false positive rate threshold.\n\nThe idea is to formulate the problem into a two-part optimization problem: How to best partition the scores from the model into a given number of regions and how to choose thresholds for the regions to minimize the overall space consumption of Bloom filters. A relaxed version of the latter problem is addressed by using KKT conditions to obtain the optimal thresholds. The former problem is addressed by discretizing the region boundaries and dynamic programming.\n\nOverall, I like the idea of fine tuning the partitioned learned Bloom filter. It seems to me that it will also be possible to fine tune the number of partitions as well, e.g., a simple way is to use a binary search. The evaluation result is impressive compared with baselines in terms of space consumption vs. false positive rate. And the writing of the paper is clear and easy to follow.\n\nHaving said that, I have some concerns with this line of work.\n\nFirst, IMHO, the real challenge of putting these learned Bloom filters into work is how to maintain them under insertions. While it is OK that this is not the focus of this work, it seems to me that the proposed optimal learned Bloom filter can be brittle under insertions. It will be great to understand how the proposed technique degrades compared with the baselines. In addition, with partitioned Bloom filters, it seems to be more prone to resizing upon insertions compared with using a single Bloom filter. \n\nSecond, it is possible that the proposed technique needs to be reoptimized upon insertions. In this case, it will be important to understand the overhead of constructing the Bloom filters proposed in this technique compared with the baselines. However, the overhead of constructing the various variants of Bloom filters is missing in the evaluation. It might be possible to reduce the overhead by using a coarser grained discretization for the DP. The performance, however, can degrade with a coarser grained discretization.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All of the reviewers thought that this paper addresses an interesting and important problem.  Several of the reviewers thought that the paper gave a creative approach for training bloom filters and this would be of interest to the community. 
Decision: Accept (Poster)