Fast Partitioned Learned Bloom Filter
Authors: Atsuki Sato
Yusuke Matsui
Venue: NeurIPS 2023 poster (2023)
Keywords: optimization
data structures
algorithms
theory
learned algorithms

Abstract: A Bloom filter is a memory-efficient data structure for approximate membership queries used in numerous fields of computer science.
Recently, learned Bloom filters that achieve better memory efficiency using machine learning models have attracted attention.
One such filter, the partitioned learned Bloom filter (PLBF), achieves excellent memory efficiency.
However, PLBF requires a $\mathcal{O}(N^3k)$ time complexity to construct the data structure, where $N$ and $k$ are the hyperparameters of PLBF.
One can improve memory efficiency by increasing $N$, but the construction time becomes extremely long.
Thus, we propose two methods that can reduce the construction time while maintaining the memory efficiency of PLBF.
First, we propose fast PLBF, which can construct the same data structure as PLBF with a smaller time complexity $\mathcal{O}(N^2k)$.
Second, we propose fast PLBF++, which can construct the data structure with even smaller time complexity $\mathcal{O}(Nk\log N + Nk^2)$.
Fast PLBF++ does not necessarily construct the same data structure as PLBF.
Still, it is almost as memory efficient as PLBF, and it is proved that fast PLBF++ has the same data structure as PLBF when the distribution satisfies a certain constraint.
Our experimental results from real-world datasets show that (i) fast PLBF and fast PLBF++ can construct the data structure up to 233 and 761 times faster than PLBF, (ii) fast PLBF can achieve the same memory efficiency as PLBF, and (iii) fast PLBF++ can achieve almost the same memory efficiency as PLBF.
The codes are available at [this https URL](https://github.com/atsukisato/FastPLBF).

Fast Partitioned Learned Bloom Filter
Atsuki Sato
Yusuke Matsui
The University of Tokyo
Tokyo, Japan
a_ A_sato@hal. t.u-tokyo.ac ac. jp
matsuichal, w...oal......ttooe.a......
Abstract
A Bloom filter is memory-efficient data structure for approximate membership queries used in numerous fields of computer science. Recently, learned Bloom filters that achieve better memory efficiency using machine learning models have attracted attention. One such filter, the partitioned learned Bloom filter (PLBF), achieves excellent memory efficiency. However, PLBF requires O ((N3)) k) time complexity to construct the data structure, where N and are the hyperparameters of PLBF. One can improve memory efficiency by increasing N, but the construction time becomes extremely long. Thus, we propose two methods that can reduce the construction time while maintaining the memory efficiency of PI PLBF. First, we propose fast PLBF, which can construct the same data structure as PLBF with a smaller time complexity (()2 Second, we propose fast PLBF++, which construct the data structure with even smaller time complexity ( log N +N k²). Fast PLBF++ does not necessarily construct the same data structure as PLBF Still, it is almost as memory efficient as PLBF, and it is proved that fast PLBF++ has the same data structure as PLBF when the distribution satisfies certain constraint. Our experimental results from real-world datasets show that (i) fast PLBF and fast PLBF++ can construct the data structure up 233 and 761 times faster than PLBB, (ii) fast PLBB can achieve the same memory efficiency as PLBF, and (iii) fast PLBB++ can achieve almost the same memory efficiency as PLBF. The codes are available at https: // thub. http///tsssssttasstsaaaa
1 Introduction
Membership query is a problem of determining whether a given query q contained within a set S. Membership query is widely used in numerous areas, including networks and databases, One can correctly answer the membership query by keeping the S and checking whether contains g. However, this approach is memory intensive because we need to maintain S.
A Bloom filter [1] is memory-effeiien data structure that answers approximate membership queries. Bloom filter uses hash functions to compress the set into a bitstring and then answers the queries using the bitstring. When Bloom filter answers q E S, it be wrong (false positives arise); when answers q É S, is always correct (no false negatives arise). A Bloom filter has been incorporated into numerous systems, such networks [2, 4], databases [5, 6. 7], and cryptocurrencies [8, 9].
A traditional Bloom filter does not care about the distribution of the set or the queries. Therefore, even the distribution has a characteristic structure, a Bloom filter cannot take advantage it. Kraska et al. proposed learned Bloom filters (LBFs), which utilize the distribution structure using machine learning model [10]. LBF achieves a better trade-off between memory usage and false positive rate (FPR) than the original Bloom filter. Since then, several studies have been conducted various LBFs [11, 12, 13].
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

non-keys
keys
to
12-1
Density
8t
0.005
0.032
0.008
G2
score
0.3
0.23
0.02
50
H1
He
BF,
BF
BF
BF
BF
FPR
fi
f2
fx
FPR
Figure 1: PLBF partitions the score space into regions and assigns backup Bloom filters with different FPRs to each region.
Figure 2: PLBF divides the score space into N segments and then clusters the N segments into regions. PLBF uses dynamic programming to find the optimal way to cluster segments into regions.
Partitioned learned Bloom filter (PLBF) [14] variant of the LBE. PLBF effectively the distribution and currently one of the most memory-efficiet LBFs. To construct PLBF, a machine learning model is trained to predict whether the input is included in the set. For given element æ, the machine learning model outputs score s(x) [0, 1]. indicating the probability that S includes PLBF divides the score space [0, into N equal segments and then appropriately clusters the N segments into k(< N) regions using dynamic programming (DP). Then, A backup Bloom filters with different FPRs are assigned to each region. We can obtain a better (closer optimal) data structure with larger N. However, PLBF builds DP tables (NN) times, and each DP table requires (( time complexity build, so the total time complexity amounts to ((N*)) k)). Therefore, the construction time increases rapidly N increases.
We propose fast PLBE, which is constructed much faster than PLBE. Fast PLBF constructs the same data structure as PLBF but with O(N2k) time complexity by omitting the redundant construction of DP tables. Furthermore, we propose fast PLBF++, which can be constructed faster than fast PLBF, with time complexity of O(N log N + 222). Fast PLBF+ accelerates DP table construction by taking advantage of characteristic that DP tables often have. We proved that fast PLBF+ constructs the same data structure PLBF when the probability of x E S and the score s sxx) are ideally well correlated. Our contributions can be summarized follows.
We propose fast PLBF, which can construct the same data structure as PLBF with less time complexity.
We propose fast PLBF++, which can construct the data structure with even less time complexity than fast PLBE Fast PLBF++ constructs same data structure as PLBF when the probability of & E S and the score s(x) are ideally well correlated.
Experimental results show that fast PLBF can construct the data structure up to 233 times faster than PLBF and achieves the same memory efficiency PLBF.
Experimental results show that fast PLBF++ can construct the data structure to 761 times faster than PLBF and achieves almost the same memory efficiency PLBF.
2 Preliminaries: PLBF
First, we define terms to describe PLBF [14]. Let S be a set clements for which the Bloom filter is to be built, and let Q be the set of elements not included in S that is used when constructing PLBF are called keys, and those not included are called non- non-keys. To build PLBF, machine learning model is trained to predict whether given element is included in the set S or Q. For a given element æ, the machine learning model outputs a score s(x) E [0, 1]. be included in the set S."
(SnQ = Ø). The elements included
The score sxx) indicates "how likely
Next, we explain the design of PLBF PLBF partitions the score space [0, 1] into regions and assigns backup Bloom filters with different FPRs to each region (Figure 1). Given a target overall FPR.

---

F (0, 1), we optimize t E R++ and f E R to minimize the total memory usage. Here, t is vector of thresholds for partitioning the score space into regions, and f a vector of FPRs for each region, satisfying to 0 < 1 <... ..... l 1 and 0 < fa S kk.......).
Next, we explain how PLBF finds the optimal t and f. PLBF divides the score space [0, 1] into N(> k) segments and then finds the optimal t and f using DP. Deciding how to cluster N segments into k consecutive regions corresponds to determining the threshold (Figure 2). We denote the probabilities that the key and non-key scores are contained in the i-th segment by 9i and h;, respectively. After we cluster the segments (i.e., determine the thresholds t), we denote the probabilities that the key and non-key scores are contained in the i-th region by G; and H;, respectively (e.g., 91 + 92 + 9s G1 in Figure 2).
We can find the thresholds that minimize memory usage by solving the following problem for each j k N (see the appendix for details); we find way cluster the 1st to (j 11)-th segments into k- regions while maximizing
k
G H:
loga
(I)
PLBF solves this problem by building j x table DP KL [p[[g] = =0...j-1mmm q 0.. for each j. DP [p]g]] denotes the maximum value Ei= G. log, H.
G
one can get when you
cluster the 1st to p-th segments into q regions. To construct PLBF, must find a clustering method
that achieves DP kLLi
[][k- 1]. ki can be computed recursively as follows:
(p 0 Ag - 0)
DP KL
(PTT]] =
00
((p = 0 v 2
(DPku 11/2 1]+ di...i.p))) (else),
max (=1..p
(2)
where the function dkL(ū, i,) is the following function defined for integers i and i, satisfying 1 S it i N:
4.
Σ G- Di Eisi h4
dkl ((r,
Σ gi
log2
The time complexity to construct this DP table O(j²R). Then, by tracing the recorded transitions backward from k 1][k: 1]. we obtain the best clustering with a time complexity of Okk). As
the DP table is constructed for each j = k N, the overall complexity is O()*k). The pseudo-code for PLBF construction is provided in the appendix.
We can divide the score space more finely with a larger N and thus obtain a near-optimal t. However, the time complexity increases rapidly with increasing N.
3
Fast PLBF
We propose fast PLBF, which constructs the same data structure as PLBF more quickly than PLBF by omitting the redundant construction of DP tables. Fast PLBF uses the same design as PLBF and finds the best clustering (i.e., t) and FPRs (i.e., f) to minimize memory usage.
PLBF constructs DP table for each j k..... N. We found that this computation is redundant and that we can also use the last DP table DP for j = .... N - 1. This is because the maximum when clustering the 1 to (j - 1) 1)-th segments into l - 1 regions is
value of Σ/=1 G2 log,
G. H.s
equal to DP [j [][ 1].
from DP KL.
We can obtain the best clustering by tracing the transitions backward 1] 1]. The time complexity of tracing the transitions is O(k), which is faster
than constructing the DP table.
This is simple method, but it is a method that only becomes apparent after some organization on the optimization problem of PLBF. PLBF solves N k + optimization problems separately, i.e., for each of j K....,, the problem of "finding the optimal t and f when the k-th region consists of
3

---

N
0
3
DPau -1]
Daa lelle 1]
DRalellee
Dhufelia]
(a)
(b)
Figure 3: The cases (a) where there is no "crossing" of the recorded transitions when computing DL [[[9]] (p 1. N 1) from DL 1] (p 0... 2) and (b) where there is. The arrows indicate which transition took the maximum value. Empirically, the probability of "crossing" small.
7
2
4
7
Max
4
2
6
5
3
6
-10
-00
-00
00
00
2
A
-50
3
5
8
9
2
N
Figure Computing DP (pla 1.. 1) from DP Lplly (p 0... N 2) via the matrix A. The computation is the same as solving the matrix problem for matrix A. When the score distribution is ideal, A is monotone matrix.
Figure 5: Example of a matrix prob- lem for 4 x 5 monotone matrix. The position the maximum value in each row (filled in gray) is moved to the "lower right".
the j. Nth segments" is solved separately. Fast PLBE, the other hand, solves the problems for j = k N - faster by reusing the computations the problem for j = N. The reorganization of the problem in the appendix makes it clear that this reuse does not change the answer.
The pseudo-code for fast PLBF construction is provided the appendix. The time complexity of building DP-V is O(N2)) and the worst-case complexity subsequent computations is ONN22. Because N > k, the total complexity is O(N²k), which is faster than (NN3k) for PLBF, although fast PLBB constructs the same data structure as PL.B.
Fast PLBF extends the usability of PLBF In any application of PLBF, fast PLBF can be used instead of PLBF because fast PLBF can be constructed quickly without losing the accuracy of PLBE Fast PLBF has applications in a wide range of computing areas [15, 5], and is significantly superior in applications where construction is frequently performed. Fast PLBF also has the advantage of simplifying hyperparameter settings. When using PLBF, the hyperparameters N and k must be carefully determined, considering the trade-off between accuracy and construction speed. With fast PI.B, on the other hand, it is easy to determine the appropriate hyperparameters because the construction time is short enough, even if N and are set somewhat large.
4
Fast PLBF++
We propose fast PLBF++, which can be constructed even faster than fast PLBF, Fast PLBF+ accelerates the construction of the DP table DP by taking advantage of characteristic that DP tables often have. When the transitions recorded in computing DPN KL [p][a] (p 1...N 1) from DP lp[g 1] (p (p= ....N - 2) are represented by arrows, as in Figure 3, we find that the arrows rarely "cross" (at locations other than endpoints). In other words, the transitions tend to have few intersections (Figure 3(a)) rather than many (Figure 3(b)). Fast PLBF+ takes advantage of this characteristic to construct the DP table with less complexity (NV log N), thereby reducing the total construction complexity to O(N log N NKk)..

---

Ag
Ee-1
(a)
(b)
(a)
(b)
Figure 6: A divide-and-conquer algorithm for solving a matrix problem for a monotone ma- trix: (a) An exhaustive search is performed on the middle row, and (b) the result is used to nar- row down the search area. (c) This is repeated recursively.
Figure 7: When the number of regions is fixed at and the number of segments is increased by 1, the optimal if A is monotone matrix (a). When A is not monotone matrix (b), the optimal f--1 may decrease.
t f--1 remains unchanged or increases
First, we define the terms to describe fast PLBE++, For simplicity, DP section. The (N 1) (N matrix defined as follows:
KL is denoted as DP in this
-00
(i ( 1,p 2......... N
Api DPLL 1][g - 1) + (1, (clse).
(4)
Then, from the definition of KL.
DPKL/Plld-
max i=1...--
Api.
(5)
The matrix A represents the intermediate calculations involved in determining DPRt/pl[o) from DL p01g- 1] (Figure 4).
Following Aggarwal et al. [16], we define the monotone matrix and matrix problem as follows.
Definition 4.1. Let B be n X real matrix, and we define function J (1...n) - {1...m) where J(i) the E (1 ....m. m) such that Biy the maximum value of the i-th row of If there is more than one such j. let J(i) be the smallest. A matrix B is called monotone matrix if (in) S (i2) for any 1 and 12 that satisfy S é < i2 I n. Finding the maximum value of each TOW of matrix is called matrix problem.
..mm..
An example of matrix problem for monotone matrix is shown in Figure 5. Solving the matrix problem for a general n x m matrix requires (nm) time complexity because all matrix values must be checked. Meanwhile, if the matrix known be monotone matrix, the matrix problem for this matrix can be solved with a time complexity of O(n + m log n.) using the divide-and-conquer algorithm [16]. Here, the exhaustive search for the middle row and the refinement of the search range are repeated recursively (Figure 6).
We also define ideal score distribution follows.
Definition 4.2. score distribution ideal if the following holds:
91
92
9N
(6)
h1
h2
bN
An ideal score distribution implies that the probability of x E S and the score s(x) are ideally well correlated. In other words, ideal score distribution means that the machine learning model learns the distribution ideally.
"Few crossing transitions" in Figure indicates that A is monotone matrix or is close to it. It is somewhat intuitive that A is a monotone matrix or close it. This is because the fact that A is monotone matrix implies that the optimal f--1 does not decrease when the number of regions is fixed at and the number of segments increases by (Figure 7). intuitively more likely that t remains unchanged or increases, in Figure 7(a), than that - decreases, in Figure 7(b). Fast PLBF+ takes ad advantage of this insight to rapidly construct DP tables.
From Equation (5), determining DP [p]]] (p 1....... ....N-1 - from 1g 0...
equivalent to solving the matrix problem of matrix A. When conquer algorithm solve this problem with O(N log N) time complexity. (The same algorithm
monotone matrix, the divide-and-
5

---

Malicious (keg)
10
Berrign (non-key)
Maliciuss (key)
16
Berign (non-key)
Count
Count
Count
12
10
10
0.2
03
044
66
6A
60
62
0.6
0.8
62
04
06
Score
Score
Score
(a) Malicious URLs Dataset
(b) EMBER Dataset
Figure 8: Histograms of the score distributions of keys and non non-keys.
9.00
10
100
(a) Malicious URLs Dataset
(b) EMBER Dataset
Figure 9: Ratio of keys to non-keys.
can obtain a not necessarily correct solution even if A is not a monotone matrix.) By computing DP [][[] with this algorithm sequentially for q 1... k 1, we can construct DP table with a time complexity of O(Nk log N). The worst-case complexity of the subsequent calculations is ONN)², so the total complexity is ( log N + NN*).. This is the fast PLBF++ construction algorithm, and this is faster than fast PLBF, which requires ((N*k) computations.
Fast PLBF++ does not necessarily have the same data structure PLBF because A is not necessarily a monotone matrix. However, as the following theorem shows, we can prove that A is a monotone matrix under certain conditions.
Theorem 4.3. If the score distribution is ideal, A is a monotone matrix.
The proof is given in the appendix. When the distribution is not ideal, matrix A is not necessarily a monotone matrix, but as mentioned above, it is somewhat intuitive that close to a monotone matrix. In addition, as will be shown in the next section, experiment results from real-world datasets whose distribution is not ideal show that fast PLBF++ is almost as memory efficient as PLBF.
5 Experiments
This section evaluates the experimental performance of fast PLBF and fast PLBF++. We compared the performances of fast PLBF and fast PLBF++ with four baselines: Bloom filter [1], Ada-BF [11], sandwiched learned Bloom filter (sandwiched LBF) [12], and PLBF [14]. Similar to PLBF, Ada-BF an LBF that partitions the score space into several regions and assigns different FPRs to each region. However, Ada-BF relies heavily on heuristics for clustering and assigning FPRs. Sandwiched LBF is an LBF that "sandwiches" a machine learning model with two Bloom filters. This achieves better memory efficiency than the original LBF by optimizing the size of two Bloom filters.
To facilitate the comparison of different methods or hyperparameters results, we have slightly modified the original PLBF framework. The original PLBF was designed to minimize memory usage under the condition of a given false positive rate. However, this approach makes difficult to compare the results of different methods or hyperparameters. This is because both the false positive rate at test time and the memory usage vary depending on the method and hyperparameters, which often makes it difficult to determine the superiority of the results. Therefore, in our experiments, we used framework where the expected false positive rate minimized under the condition of memory usage. This approach makes it easy to obtain two results with the same memory usage and compare them by

---

keys
Train machine learning model
Find optimal parameters
250
200
Consiruction Timer [s]
Consiruction Time
150
100
5.0
0.0
Bloon fiber
Adte-FF
Sunderiche LBF
PLBF
Feed PLBF Paol PLBF++ (Proposes) (Froposed)
Broom liber
Adw+FF
Sendarched
PLBF
Faod PLEF Faxtt F (Proposed) (Proposed)
LBF
(a) Malicious URLs Dataset
(b) EMBER Datasct
Figure 10: Construction time.
the false positive rate at test time. See the appendix for more information on how this framework modification will change the construction method of PLBFs.
Datasets: We evaluated the algorithms using the following two datasets.
Malicious URLs Dataset: As in previous papers [11, 14], we used Malicious URLs Dataset [17]. The URLs dataset comprises 223,088 malicious and 428,118 benign URLs. We extracted 20 lexical features such as URL length, use of shortening, number of special characters, etc. We used all malicious URLs and 342,482 (80%) benign URLs as the training set, and the remaining benign URLs the test set.
EMBER Dataset: We used the EMBER dataset [18] as in the PLBF research. The dataset consists of 300,000 malicious and 400,000 benign files, along with the features of each file. We used all malicious files and 300,000 (75%) benign files as the train set and the remaining benign files as the test
While any model can be used for the classifier, we used LightGBM [19] because of its speed in training and inference, as well as its memory efficiency and accuracy. The sizes of the machine learning model for the URLs and EMBER datasets are 312 Kb and 1.19 Mb, respectively. The training time of the machine learning model for the URLs and EMBER datasets is 1.09 and 2.71 seconds, respectively. The memory usage of LBF is the total memory usage of the backup Bloom filters and the machine learning model. Figure shows histogram of each dataset's score distributions of keys and non-keys. We can see that the frequency of keys increases and that of non- decreases as the score increases. In addition, Figure plots g:/h, h (i ge/ / tends to increase as increases, but the increase is not monotonic (i.e., the score distribution is not ideal).
N) when
000. We can see that
5.1 Construction time
We compared the construction times fast PLBF and fast PLBF+ with those of existing methods. Following the experiments in the PLBF paper, hyperparameters for PLBF, fast PLBF, and fast PLBF+ were set to = 1, 0000 and = 5.
Figure 10 shows the construction time for each method. The construction time for learned Bloom filters includes not only the time to insert keys into the Bloom filters but also the time to train the machine learning model and the time to compute the optimal parameters (t and in the case of PLBF).
Ada-BF and sandwiched LBF use heuristics to find the optimal parameters, so they have shorter construction times than PLBF but have worse accuracy. PLBF has better accuracy but takes more than 3 minutes to find the optimal and f. On the other hand, our fast PLBF and fast PLBF+ take less than seconds. As a result, Fast PLBF constructs 50.8 and 34.3 times faster than PLBF, and fast PLBF++ constructs 63.1 and 39.3 times faster than PLBF for the URLs and EMBER datasets, respectively. This about the same construction time as sandwiched LBF, which relies heavily on heuristics and, as will see in the next section, is much less accurate than PLBF.

---

Bloom fiter
Ad
Sandwkchdd LBF
PLBF
Fost PLBF (Proposed)
Fast PLBF+ +- (Proposed)
False Posilive Rale
False Posilve
10
0.
0.6
12
1.8
2.0
200
2.4
2.5
3.0
Total Memory Usage [Mbi]]
Total Memory Usage [Mbil]
(a) Malicious URLs Dataset
(b) EMBER Dataset
Figure 11: Trade-off between memory usage and FPR.
PLBF (Propoead)
Fast PLBF++ (Proposed)
110
Fabee Postivv Rate
Construction Time [c]
Positve Rate
Condruucion Time [c]
1:44
8
1.40
10'
(a) Malicious URLs Dataset
(b) EMBER Datasct
Figure 12: Ablation study for hyper-parameter N.
5.2 Memory Usage and FPR
We compared the trade-off between memory usage and FPR for fast PLBF and fast PLBF+ with Bloom filter, Ada-BF, sandwiched LBF, and PLBF. Following the experiments in the PLBF paper, hyperparameters for PLBF, fast PLBE, and fast PLBF++ were always set to = 000 and 5.
Figure 11 shows each method's 's trade-off between memory usage and FPR. PLBF, fast PLBF, and fast PLBF+ have better Pareto curves than the other methods for all datasets. Fast PL.BF constructs the same data structure PLBF in all cases, so it has exactly the same accuracy PLBF, Fast PLBF++ achieves almost the same accuracy as PLBF, Fast PLBF++ has up to 1.0019 and 1,000083 times higher false positive rates than PLBF for the URLs and EMBER datasets, respectively.
5.3 Ablation study for hyper-parameters
The parameters of the PLBFs are memory size, N. and k. The memory size is specified by the user, and N and k are hyperparameters that are determined by balancing construction time and accuracy. In the previous sections, we set N to 1,000 and 5, following the original paper on PLBF. this section, we perform ablation studies for these hyperparameters to confirm that our proposed methods can construct accurate data structures quickly, no matter what hyperparameter settings are used. We also confirm that the accuracy tends to be better and the construction time increases N and & are increased, and that the construction time of the proposed methods increases much slower than PLBF
Figure 12 shows the construction time and false positive rate with various N while the memory usage of the backup Bloom filters is fixed 500 Kb and is fixed at 5. For all three PLBFs, the false positive rate tends to decrease as N increases. (Note that this is the false positive rate on test data, so it does not necessarily decrease monotonically. The appendix shows that the expected value of the false positive rate calculated using training data decreases monotonically as N increases.) Also, as increases, the PLBF construction time increases rapidly, but the fast PLBF construction time increases much more slowly than that, and for fast PLBF++, the construction time changes little. This because the construction time of PLBF is asymptotically proportional to N3, while that of fast PLBF and fast PLBF++ is proportional to 2 and N log N, respectively. The experimental results

---

PLBF
Fast PLBF (Proposec)
Fast PLBF++ (Proposed)
1'10"
1.1
Faee Poslives Rate
Construction Time (6]
Construction [s]
8.
13
16'
(a) Malicious URLs Dataset
(b) EMBER Dataset
Figure 13: Ablation study for hyper-parameter k.
show that the two proposed methods can achieve high accuracy without significantly changing the construction time with large N.
Figure 13 shows the construction time and false positive rate with various & while the backup bloom filter memory usage is fixed 500 Kb and N is fixed at 1,000. For all three PLBFs, the false positive rate tends to decrease as & increases. For the EMBER dataset, the false positive rate stops decreasing at about l 20, while for the URLs dataset, it continues to decrease even about & = 500. (Just as in the case of experiments with varying N, this decrease is not necessarily monotonic.) In addition, the construction times of all three PLBFs increase proportionally shorter construction time than PLBF, and fast PLBF++ has an even shorter construction time than fast PLBF. When & 50, fast PLBF constructs 233 and 199 times faster than PLBF, and fast PLBF+ constructs 761 and 500 times faster than PLBF for the URLs and EMBER datasets, respectively. The experimental results indicate that by increasing the two proposed methods can achieve high accuracy without significantly affecting the construction time.
k. but fast PLBF has much
Related Work
Approximate membership query is query that asks whether the query q is contained in the set S while allowing for false positives with a small probability E. One can prove that at least |S log, (1) bits of memory must be used answer the approximate membership query if the elements in the set or queries are selected with equal probability from the universal set [20].
A Bloom filter [1] is one of the most basic data structures for approximate membership queries. It compresses the set S into a bit string using hash functions. This bit string and the hash functions are then used to answer the queries. To achieve an FPR of Bloom filter requires |S| (t) loga bits of memory. This is log, e times the theoretical lower bound.
Various derivatives have been proposed that achieve better memory efficiency than the original Bloom filter. The cuckoo filter [21] is more memory efficient than the original Bloom filter and supports dynamic addition and removal of elements. Pagh et al. [22] proposed replacement for Bloom filter that achieves a theoretical lower bound. Various other memory
filters exist, including the vacuum filter [23], xor filter [24], and ribbon filter [25]. However, these derivatives do not consider the structure of the distribution and thus cannot take advantage of it.
Kraska et al. [10 proposed using machine learning model as prefilter of a backup Bloom filter. Ada- BF [11] extended this design and proposed to exploit the scores output by the machine learning model. PLBF [14] uses design similar to that of Ada-BB BF but introduces fewer heuristics for optimization than Ada-BF. Mitzenmacher [12] proposed an LBF that "sandwiches" a machine learning model with two Bloom filters. This achieves better memory efficiency than the original LBF but can actually be interpreted special case of PLBE
Limitation and Future Work
As explained in Section 4, it is somewhat intuitive that A is monotone matrix or close to it, so it is also intuitive that fast P achieves accuracy close to PLBE. Experimental results on the URLs and EMBER datasets also suggest that fast PLBF++ achieves almost the same accuracy as PLBF

---

even when the score distribution is not ideal. This experimental rule is further supported by the results of the artificial data experiments described in the appendix. However, there is no theoretical support for the accuracy of fast PLBF++. Theoretical support for how fast PLBF++ accuracy may degrade relative to PLBF a future issue.
Besides, it is possible to consider faster methods by making stronger assumptions than fast PLBF++. Fast PLBF++ assumes the monotonicity of matrix A. We adopted this assumption because matrix A is proved to be monotone under intuitive assumptions about the data distribution. However, by assuming stronger assumptions about matrix A, the computational complexity of the construction could be further reduced. For example, if matrix A is totally monotone, the matrix problem for matrix A can be solved in ((N) using algorithmss such as [16, 26]. Using such existing DP algorithms is promising direction toward even faster or more accurate methods, and is a future work.
8 Conclusion
PLBF is an outstanding L.BF that can effectively utilize the distribution of the set and queries captured by machine learning model. However, PLBF is computationally expensive construct. We proposed fast PLBF and fast PLBF++ to solve this problem. Fast PLBF superior to PLBF because fast PLBF constructs exactly the same data structure as PLBF but does so faster. Fast PLBF++ is even faster than fast PLBF and achieves almost the same accuracy as PLBF and fast PLBF. These proposed methods have greatly expanded the range applications of PLBF.
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for their constructive comments. This work was supported by IST AIP Acceleration Research JPMJCR2332, Japan.
References
[1] Burton H Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7):422 426, 1970.
[2] Andrei Broder and Michael Mitzemmacher. Network applications of bloom filters: survey. Internet mathematics, 1(4):485-500 2004.
[3] Sasu Tarkoma, Christian Esteve Rothenberg, and Eemil Lagerspetz. Theory and practice of bloom filters for distributed systems. IEEE Communications Surveys & Tutorials, 14(1):131- 155, 2011.
[4] Shahabeddin Geravand and Mahmood Ahmadi. Bloom filter applications in network security: A state-of-the-art survey. Computer Networks, 57(18):4047-4064, 2013.
[5] Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C Hsich, Deborah Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E Gruber. Bigtable: A distributed storage system for structured data, ACM Transactions on Computer Systems (TOCS), 26(2):1-26, 2008
[6] Michael I Goodrich and Michael Mitzenmacher. Invertible bloom lookup tables. Allerton Conference Communication, Control, and Computing (Allerton), 201
[7] Guanlin Lu, Young Jin Nam, and David HC Du. Bloomstore: efficient key-value store for indexing of data deduplication on flash. In IEEE Symposium on Mass Storage Systems and Technologies (MSST), 2012.
Bloom-filte filter based memory-
[8] Mike Hearn and Matt Corallo. Bips: Connection bloom filtering, 2012. URL http:///wwbb.om//iccciiii///h//e 2012.
[Online; accessed 22-December-20222,
[9] Jongbeen Han, Mansub Song. Hyeonsang Eom, and Yongseok Son. An efficient multi-signature wallet blockchain using bloom filter. In Proceedings of the ACM Symposium on Applied Computing, 2021.
10

---

[10] Tim Kraska, Alex Beutel, Ed H Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. Proceedings of the International Conference on Management of Data, 2018.
[11] Zhenwei Dai and Anshumali Shrivastava. Adaptive learned bloom filter (ada-bf): Efficient utilization of the classifier with application to real-time information filtering the web. In Advances in Neural Information Processing Systems, 2020.
[12] Michael Mitzenmacher. A model for learned bloom filters and optimizing by sandwiching. In Advances in Neural Information Processing Systems, 2018.
[13] Jack Rae, Sergey Bartunov, and Timothy Lillicrap. Meta-learning neural bloom filters. In International Conference on Machine Learning, 2019.
[14] Kapil Vaidya, Eric Knorr, Michael Mitzenmacher, and Tim Kraska. Partitioned learned bloom filters. In International Conference on Learning Representations, 2021.
[15] Yi-Hsuan Feng, Nen-Fu Huang, and Chia-Hsiang Chen. An efficient caching mechanism for network-based url filtering by multi-level counting bloom filters. In 2011 IEEE International Conference on Communications (ICC), 2011.
[16] Alok Aggarwal, Maria M Klawe, Shlomo Moran, Peter Shor, and Robert Wilber. Geometric applications of a matrix-searching algorithm. Algorithmica, 2(1):195-208, 1987.
[17] Manu Siddhartha.
Malicious
urls dataset
kaggle. [Online;
URL accessed
22 2022m) 2021.
[18] Hyrum S Anderson and Phil Roth. Ember: an open dataset for training static pe malware 2018.
machine learning models. arXiv preprint arXiv: arXiv:/804.
[19] Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie- Yan Liu. Lightgbm: A highly efficient gradient boosting decision tree. In Advances in Neural Information Processing Systems, 2017.
[20] Larry Carter, Robert Floyd, John Gill, George Markowsky, and Mark Wegman. Exact and ap- proximate membership testers. In Proceedings of the ACM symposium on Theory of computing, 1978.
[21] Bin Fan, Dave G Andersen, Michael Kaminsky, and Michael Mitzenmacher. Cuckoo filter: Practically better than bloom. In Proceedings of the ACM International Conference on emerging Networking Experiments and Technologies. 2014.
[22] Anna Pagh, Rasmus Pagh, and S Srinivasa Rao. An optimal bloom filter replacement. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 2005.
[23] Minmei Wang. Mingxun Zhou, Shouqian Shi, and Chen Qian. Vacuum filters: More space- efficient and faster replacement for bloom and cuckoo filters. Proceedings of the VLDB Endowment, 13(2):197-21 2019.
[24] Thomas Mueller Graf and Daniel Lemire. Xor filters: Faster and smaller than bloom and cuckoo filters. Journal of Experimental Algorithmics (JEA), 25:1-16, 2020.
[25] Peter C. Dillinger and Stefan Walzer. Ribbon filter: practically smaller than bloom and xor. arXiv preprint arXiv:2 02555, 2021.
[26] Zvi Galil and Kunsoo Park. A linear-time algorithm for concave one-dimensional dynamic programming. Information Processing Letters. 33(6):309-311 1989.
[27] Johan Ludwig William Valdemar Jensen. Sur les fonctions convexes et les inégalités entre les valeurs moyennes. Acta mathematica, 30(1):175-193, 1906.

---

Appendices
Appendix A details the optimization problem designed in the original PLBF paper [14] and its solution. It includes a comprehensive analysis of the optimization problem and a detailed description of how PLBF's method leads (under certain assumptions)
a solution to the optimization problem, which are not provided in [14]. Appendix B presents details of PLBF and the fast PLBF algorithm along with pseudo-codes Appendix C gives the proof of Theorem 4.3, a theorem about the accuracy of fast PLBF++. In Appendix D we explain the trivial modifications to the PLBF framework that we made for the experiments. Appendix E describes a detailed ablation study of the PLBFs hyperparameters. N and k. Appendix F describes the experiments on the simplified solution method presented in the PLBF paper. Appendix G describes experiments with artificial datasets to evaluate the experimental performance of fast PLBF++ in detail.
Appendix A Solution of the optimization problems
In the original PLBF paper [14], the analysis with mathematical expressions was conducted only for the relaxed problem, while no analysis utilizing mathematical expressions was performed for the general problem. Consequently, was unclear which calculations were redundant, leading to the repetition of constructing similar DP tables. Hence, this appendix provides a comprehensive analysis of the general problem. presents the optimal solution and the corresponding value of the objective function using mathematical expressions. This analysis uncovers redundant calculations, enabling the derivation of fast PLBF.
The optimization problem designed by PLBF [14] can be written as follows:
1
minimize f.t
Σ
cl G. logz
fr
subject to
Σ Hafs S
(7)
i=1 to = Au5
12 < <t =1
11=1...k) k).
The objective function represents the total memory usage of the backup Bloom filters. The first constraint equation represents the condition that the expected overall FPR is below F. c 2 1 is a constant determined by the type of backup Bloom filters. G and H are determined by t. Once t is fixed, we can solve this optimization problem to find the optimal f and the minimum value of the objective function. In the original PLBF paper [14], the condition < 1 (i -1..k) ..) was relaxed; however, here we conduct the analysis without relaxation. We assume G2 > 0, H, > 0 1...... and |S] > O.
The Lagrange function is defined using the Lagrange multipliers
R and E R, as follows:
L(F L(f Σ G logz
Σ Hu(fi
+)+ + Σ H. H.f.-F))
(8)
From the KKT condition, there exist ja and & in the local optimal solution f of this optimization problem, and the following holds:
QL
0/, (J,P,D) (i= l...k) k)
1, - 0, 2,2, 0, R.lS. 1) =0 11=1...k)
(10)
Σ H.J.- F 0 D2 0, 0
Σ HrJ. - F =0.
(11)
define Z and I as and I n NI = 2 are satisfied. Furthermore, we assume that Izc1 # Ø. This means that there is at least region that uses backup Bloom filter with FPR smaller than 1.
[i) = and If<i = (il J. < 1). I
(k..k)
12

---

By introducing 1 and <1, Equations (9, 10, 11) can be organized as follows:
cS||G f4 + pHl, R4 2 0, f =
(iE I==1)
(12)
dSIG; = f.0H4, =0 f << (fEI)<))
(13)
H. - PSO, 020, D H. H.+
Σ 1E2fe1
Σ H iE
Σ
H.J-
- = 0. (14)
#EZy=1
iELy<1
Here, we get 0. This because if we assume D 0, Equation (13) implies that G; 0 for
i E [f Ø), which contradicts the assumption that G; > 0. From & > 0 and Equation (13),
c|S| G. f. = D H.
(i
(15)
From Equations (14, 15) and D > 0,
cSI G. ==0 H,
Σ
H; +
Σ
Hi
(16)
iEI,=1
iEIf<1
c|Sl
F F- -iE
Hi
=
EiEr,e
G₁
(17)
Substituting Equations (15, 17) into the objective function of the optimization problem (7), we obtain
F -jez,, H2 Gi
G log, (F.
1
Σ
-|S logz logz
(18)
EjErfer Gj H:
iELye1
1 Gy=1
G;
=| - G)=1) -
- c|S| Σ
G
Go
F- F- H1=1
Hi
iET
(19)
We define Gy-1 and H5-1
G. and H5 EieI, Hi respectively.
PLBF makes the following assumption: Assumption A.1. For optimal t and f. Iy=1 = Ø or 1 {k}.
In other words, PLBF assumes that there is at most one region for which f and if there one, is the region with the highest score. PLBF then tries all possible thresholds t (under the division of the score space).
In the following, we discuss the optimal f and t under the assumption that the j-th to N-th segments clustered as the k-th region (j NN..
In the case I f=1 = Ø0 because Gy=1 = H5=1 = Equation (19) becomes
F (
k-1
G;
c
logz
elS loga
cSS
G
loga
(20)
H
H,
Meanwhile, the case of Iz=1 = {k), Equation (19) becomes
1 Gk F H
k-1
G H,
e|S((1 - Gk) log,
cSS)
Ge
loga
(21)
In both cases, the terms other than the last one are constants under the assumption that the j-th to N-th segments are clustered as the k-th region. Therefore, the value of the objective function is minimized
when the 1st to (j 3-11 --1)tth -h segments are clustered in a way that maximizes Σi=1 G, log, G H.
Thus,
the problem of finding that minimizes memory usage be reduced the following problem: for each j = k...N, we find a way to cluster the 1st to (j - 1)-th segments into regions that (Ga
maximizes k-1 G2 loga
H.
13

---

Algorithm PLBF [14]
Input:
g RV probabilities that the keys are contained in each segment
h E IN,, probabilities that the non-keys are contained in each segment
F E (0.1) target overall FPR
k E N: number of regions
Output:
E R*+1 ttreshold boundaries of each region
f E &R* FPRS of each region
A Algorithm:
THRESMAXDIVDPiga k))
constructs DP KI. and calculates the optimal thresholds by tracing the transitions backward from DP kT. ; 1][k
OPTIMALFPR , h t, F))
returns the optimal FPRs for each region under the given thresholds
SPACEUSED(gg h. f)
returns the space size used by the backup Bloom filters for the given thresholds and FPRs
MinSpace <- 0O
hhst None
fest f- None
for j ....N
+ TURESMAXDIVDP(G, j. f + OPTIMALFPR( h, t, F, F)
MinSpaceUsed > SPACEUSED(g, h t, f) then MinSpaceUsed SPACEUSED(g. h. f)
teet t-
fbest f
return bbest fbest.
Appendix B Algorithm details
In this appendix, explain the algorithms for PLBF and the proposed method using pseudo-code in detail. This will help to clarify how each method differs from the others.
First, we show the PLBF algorithm in Algorithm 1. For details of OPTIMALFPR and SPACEUSED. please refer to Appendix and Equation (2) in the original PLBF paper [14], respectively. The worst case time complexities of OPTIMALFPR and SPACEUSED are ( and O(k), respectively. As the DP table is constructed with a time complexity of O(j2k) for each j = k. k...N, the overall complexity is k)
Next, we show the fast PLBF algorithm in Algorithm 2. The time complexity of building DPN KL is O(N²A), and the worst-case complexity of subsequent computations is ONN))) Because > k, the total complexity is O(N2),, which is faster than O(N*k) for PLBF, although fast PLBF constructs the same data structure as PLBF.
Finally, we describe the fast PLBF++ algorithm. The fast PLBF++ algorithm is nearly identical to fast PLBF. but it calculates approximated DP with a computational complexity of O(N log N). Since the remaining calculations are unchanged from fast PLBF, the overall computational complexity is O(Nk log N + NR2)..
Appendix C Proof of Theorem 4.3
In this appendix, we present proof of Theorem 4.3. demonstrates that fast PLBF+ can attain the same accuracy PLBF and fast PLBF under certain conditions.
The following lemma holds.
14

---

Algorithm 2 Fast PLBF
Algorithm:
MAXDIvDP (g. h, NV, k)
constructs DP
(HRESMAXDIVVDPX... j,
calculates the optimal thresholds by tracing the transitions backward from DP - -1][k-
MinSpaceUsed <- 00
best + None
fbest <- None
DP KL f MA
for j =k...N
t THREESMADDVVDDPA KL. j.k)
f + OPTIMALFPR(G, h, F,
if MinSSaaceUsed > SPACEUSED(g, h t, f) then MinSpaceUssed + SPACEUSED(g.h,, f,
bbett 6 t
foost f f
return Liestt f Jhst
Lemma C.1. Let un, u2 un, and 02 be real numbers satisfying
0 < 01 < U2
(22)
0 < 1/2
(23)
U2
(24)
V1 12
Furthermore, we define the function D(x, y) for real numbers
and y as follows:
u1 +
}
U2 + x
U/2
D(I, 3) (u1 + x)) logz
log2
(mg + x)) loga
U2 loga
U1 + y
V1
02 +
U/2
(25)
If en
holds, then D(x, v)
Proof.
0D
U1 +
122 + 2
log2
logg2
(26)
Ox
U1 +
U2 y
0D
01 +
U2 + x
+
(27)
8y
U1 +
U/
From Equations (22, 23, 24), when 0 <
y, and
21 we obtain
Ii + Ø0
U2 +
(28)
f1 y
1/2 +
Therefore,
0D
(29)
Zr
0D
0.
(30)
Oy
15

---

Thus,
inf
D(a,y) 2
inf
D(x,y)
(31)
0<a,0<u
inf D(2u1, 201)
(32)
201
U2
2u1 + ui
}
inf 220
2 loga
+ u2 log2
(zt + u2) log2
201
201 +
(33)
0.
(34)
The transformation to Equation (34) is due to Jensen's 's inequality [27]. This shows that if E then (z,, y) 2 0.
25
Proof. We prove Theorem 4.3 by contradiction.
Assume that the (N 1) x (N - 1) matrix is not a monotone matrix. That is, we assume that there exists p N 2) such that ((p) > J(p + 1). Let J(i) be the smallest j such that Ag equals the maximum of the i-th row of A. We define a = (pp and a' = J(p + 1) (a > a' from the assumption for contradiction).
From the definitions of A and J(i), we obtain the following:
DPkL(p][ DP 11ʃg 1] + dkl (a.p)
(35)
DP + 1|[g] = DPKL/a' - 11[1 1] + dkl. (a' + 1)
(36)
[r > DPkt(a' - 11//2 - 1] dkL (a', p)
(37)
DP 1](]] DPRL[a- 1][g 1119-111 -1] dRL (a, ((a.ppp. 1):
(38)
Using Equations (35, 36, 38), we evaluate the right side of Equation (37) minus the left side of
Equation (37).
DPKLla' 1][q 1] + dkL p) DP (L
(39)
[DDPLI + 1][g] - dKL(a', p + 1)} + dkl p) - (DPkLla - 1][g 1] + dkI (a, (a, p)}
(40)
(DPRL (p 1][q] DP DP (a 1|ʃg 1|} + dxL p) dal ,p +p 1) dxl (a. p)
(41)
dkL(a. 1) dk1 (a' ,p) dkl + 1) dkl. (a. p)
(42)
(d, p (aL(a. p)} {dkI(a', p 1) dKL (a' pP)
(43)
Equations (35, 36) are used for the transformation to Equation (40), and Equation (42) used for the transformation Equation (38).
We define U1, U2 U1 U2 H. and as follows:
Σ
Jis
U2
Ds. = 9p+1,
==a
ima'
(44)
14,
02
Σ his == hy+1-
i=a
i=a!
From the conditions ideal score distribution and a'
< a, the followings hold:
0 < #1 U2
(45)
0 < 01 0/2
(46)
0/2
(47)
y
11
U2
0
<
x, y.
(48)
Therefore, from Lemma C.1, U1 + x
(un + x) +0gg
un logg
[1
u1
}
(m2 + x)) loga
112 + x0
W2 logg
U2
01 +
+
U/2
(49)
(dKklaa, (a, dkI(a, (dku p dkL(d',
(50)
0.
(51)
16

---

Algorithm 3 OptimalFPR__ (Algorithm in [14)
Input:
G E RN probabilities that the keys are contained in each region
H RRN; probabilities that the non-keys contained in each region
F (0.1): target overall FPR
E N: number of regions
Output:
f E RR FPRs of each region
for l..kk fit G H,
while 3i: fi >
for i 1
if f > 1 then fi
Gsum Hgum 0
for i
1...k Ks if fi 1 then
Geum f- Gsum + G3
Hsum t Hsum + H;
for i 1...k
if fi < then fi - H1-(I-Gaun
return
Then, from Equations (39. .9.44)) 43), we obtain
DPk,,a' - 1][g 1] (a', DP [p]aa] 2 0.
(52)
However, this contradicts Equation (37). Hence, Theorem 4.3 is proved.
Appendix D Modification of the PLBF framework
In this appendix, describe the framework modifications made to PLBF in experiments. In the original PLBF paper [14], the optimization problem was designed to minimize the amount of memory usage under given target false positive rate (Equation (7)). However, this framework makes difficult to compare the results of different methods and hyperparameters. Therefore, we designed the following optimization problem, which minimizes the expected false positive rate under given memory usage condition:
minimize ft
Σ H1t.
1=1
subject to
Σ G|S loga
1
S M
(53)
4o
< 4
ft < 1
(i ii 1; k),
where M is a parameter that is set by the user to determine the upper bound of memory usage and is by the user.
a way cluster the 1st to (j - 1) segments into k regions that maximizes Σ G, logz for each j k... N. We can compute this using the same DP algorithm as in the original framework.
Analyzing as in Appendix A, we find that order to find the optimal thresholds t, we need to find
G.
H:
17

---

Algorithm 4 OptimalFPRR_M
Input:
G E RV; probabilities that the keys are contained in each region
H RN probabilities that the non-keys contained in each region
M E upper bound of the total memory usage of backup Bloom filters
k BET N: number of regions
Output:
f E RR FPRs of each region
Kaum +0
for i = L...k k
Koum f Ksum + G2 loga
C
+- M M Kuu
c for i = 1..... k
J 2-8 H.
while 3i:
for i = 1...k
if [ 1 then
fi +
Gaum t 0
Hsum +
Kaum 0
for
1...k if ft 1 then
Geum +- Gsum + G2
Haum f Hsum + H,
else
Ksum f Kaum + G2 log2
G+ H.
M M+clSkKKun c] (S((1-Gam) Garm)
for
1.... ... k
if [ < 1 then
fr - - G: H4
return f
Also similar to Appendix A, introducing I and Iςςι for analysis, it follows that the optimal false positive rates f is
J. = G3 H;
(
(54)
where
M + +|8) Eierfes G3 Golog2
G₁ H.
(55)
c|S) - GG
In the original framework, the sets I5=1 and Σ₁<1 obtained by repeatedly solving the relaxed problem and setting fi to for regions where J; > 1 (for details of this algorithm, please refer to
the Section 3.3.3 in the original PLBF paper [14]). our framework, we can find the sets I,=1 and If<1 in the same way.
The pseudo-code for OPTIMALFPR F in the original PLBF paper [14] and OPTIMALFPR M_,, which conditioned on the memory usage M, shown in Algorithm 3 and Algorithm 4. For both functions, the best-case complexity is (k)) and the worst-case complexity is (lk)).
Also, the fast PLBF algorithm for the case conditioned by memory usage shown in Algorithm It is basically the same the original PI.BF Algorithm 2, but instead of using the SPACEUSED function, the EXPECTEDFPR function is used here. Then, the algorithm selects the case when the expected overall false positive rate calculated using the training data is minimized.
18

---

Algorithm 5 Fast PLBF conditioned by memory usage
Algorithm:
MAXDIvDP(g. h. k)
constructs DP
THRESMAXDIV (DV k.k:
calculates the optimal thresholds by tracing the transitions backward from DP DPR..I - 1
OPTIMALFPR Mgg. h, t, M,M, k):
returns the optimal FPRs for each region under the given thresholds and the memory usage EXPECTEDFPR ( h, t, f):
returns the expected overall false positive rate for the given thresholds and FPRs
MinExpectedF PR 4-
best + None
Shest f- None
DP KL. MAXDIVDD(g,, h, N,k)
for j =k...N
& TURESMAXDIV(DIP KL..AAAADNDDDDL....A k..j,k)
f < OPTIMALFPR M(g. h, M.
MinExpecctdFFRR EXPECTEDEPR(g, h, t. then
MinExpectedFPR t EXPECTEDFPR h,t,f)
Ubstt 6-6
f f
return best, fest
Appendix E
Additional ablation study for hyperparameters
This appendix details the ablation studies for the hyperparameters N and k. In this appendix, we discuss the results of the ablation studies that were not presented in Section 5.3. The results confirm that the expected false positive rate decreases monotonically as the hyperparameters N and k increase. We also confirm that the proposed methods are superior to PLBF in terms of hyperparameter determination.
First, we confirm that the expected false positive rate decreases monotonically as N increases. The expected false positive rate is computed using training data (objective function in Equation (53)). Figure 14 shows the expected false positive rate various N and k. The ablation study for N done with à fixed to 5. The ablation study for & is done with N fixed to 1,000.
The expected false positive rate decreases monotonically methods. However, as observed in Section 5.3, the false positive rate at test time does not necessarily decrease monotonically as N or k increases, Also, the construction time increases as N or & increases. Therefore, it is necessary to set appropriate N and &s when practically using PLBFs.
N l increases for all datasets and
Therefore, we next performed comprehensive experiment various N and k. Figure 15 shows the construction time and false positive rate for each method when the memory usage of the backup bloom filter is fixed at 500 Kb, N is set to 8, 16, .6. 1024, and l is set to 10, and 20. The curves connect the same l: and different N results.
The results show that the proposed methods are superior to PLBB because it is easier to set hyper- parameters to construct accurate data structures in a shorter time. PLBF can achieve the same level of accuracy with the same construction time as fast PLBF and fast PLBF++ if the hyperparameters N and & are set well. However, is not apparent how N and & should be set when applying the algorithm to unseen data. If N or k is set too large, the construction time will be very long, and if N or & is set too small, the false positive rate will be large. The proposed methods can construct the data structure quickly even if the hyperparameters N and are too large. Therefore, by using the proposed methods instead of PLBF and setting and l relatively large, is possible to quickly and reliably construct data structure with reasonable accuracy.
Furthermore, we performed an ablation study using fast PLBF to obtain guidelines for set- ting the hyperparameters N and k (Figure 16). We observed false positive rates for N
19

---

PLBF
Fast PLBF (Proposed)
Fast PLBF++ (Proposed)
x 10
x
10
Expected False Positive Rate
Expected False Positive Rate
1.8
1.5
13
1.2
10
10"
10"
10
10
10"
N
k
(a) Malicious URLs Dataset.
10
x
10
Expecled False Posilive Rale
Expected False Positive Rate
7.5
6.0
7.0
5.5
6.6
8.0
5.0
5.5
5.0
10'
10²
10"
N
k
(b) EMBER Dataset.
Figure 14:
Expected false positive rate computed with training data at various N or k. The memory usage of the hackup bloom filter is 500 Kb. The ablation studies for N are done with & fixed to (left figures). The ablation studies for k are done with N fixed to 1,000 (right figures).
20, 50, 100, 200, 300, 1500 and 50, 100, 200, 300, ..... 1400 with k N. For the Mali- cious URLs Dataset, the false positive rate was lowest when N = 1300 and k 700 (in this case, the fast PLBF construction is 333 times faster than PLBF). And for the Ember dataset, the false positive rate was lowest when N 500 and A = 50 (in this case, the fast PLBF construction is 45 times faster than PLBF). The Malicious URLs Dataset showed an almost monotonous decrease in the false positive rate N and k: increased, while the Ember Dataset showed almost no such trend. This is thought to be due to a kind of overlearning that occurs as N and & are increased in the Ember Dataset. Although method for determining the appropriate N and l: has not yet been established, we suggest setting N 1000 and ~ 100. This is because the false positive rate is considered to be small enough at this level, and the proposed method can be constructed in few tens of seconds. In any case, the proposed method is useful because it is faster than the original PLBF for any hyperparameters N and k.
Appendix F Experiments PLBF solution to relaxed problem
The PLBF paper [14] proposes two methods: a simple method and complete method. In this appendix, conducted experiments the simple method and evaluated the difference in accuracy compared to the complete method. The results revealed that, in certain cases, this method exhibited significantly lower accuracy than the complete method. It then confirmed that fast PLBF and fast PLBF+ are superior to the simple method in terms of the trade-off between construction time and accuracy.
The simpler method, described section 3.3.3 of [14], does not consider the condition that fa S 1 (i 1k..k) when finding the optimal t. In other words. this method solves the relaxed problem
20

---

PLBF
Fast PLBF (Proposed)
Fast PLBF++ (Proposed)
0.017
Faise Positive Rate
0.016
0.015
0.014
10
10
10
Construction Time [s]
(a) Malicious URLs Datasct
0.016
False Positive Rate
0.014
0.012
0.010
k
10
0.008
10
10
10
Construction Time [s]
(b) EMBER Dataset
Figure 15: Construction time and FPR for various N and k. The curves connect the same h and different N results. The memory usage of the backup bloom filter is 500 Kb.
that does not consider the condition fi < 1 (i k). The complete method uses the first method repeatedly as a subroutine to solve the general problem and find the optimal t. Here, the time complexity of the method for the relaxed problem is O(N2k), and that of the method for the general problem is ())*)..
We experimented with the simpler method. Figure 17 shows the construction time (the hyperpa- rameters for PLBFs were set to 1. 000 and 1: 5). The PLBF for the relaxed problem has about the same construction time our proposed fast PLBF This is because the time complexity for constructing the two methods (N22) for both. Figure 18 shows the trade-off between memory usage and FPR. On the URL. dataset, the method for the relaxed problem is almost accurate as the method for the general problem. At most, has a false positive rate of only 1.06 times greater. On the other hand, on the EMBER dataset, the method for the relaxed problem is significantly less accurate than the method for the general problem, especially when memory usage is small. has up to 1.48 times higher false positive rate than the complete method.
In summary, the method for the relaxed problem can construct the data structure faster than the method for the general problem, but the accuracy can be significantly worse, especially when memory usage small. Our proposed fast PLBF has the same accuracy as the complete PLBF in almost the same construction time as the method for the relaxed problem. Our fast PI.BF++ can construct the data structure even less time than the method for the relaxed problem, and the accuracy degradation is relatively small.
21

---

1400
1400
000057
1200
00134
12m0
1000
900
00012
Fable Posibee Rais
1000
False Postive Raie
800
700
-0.0300
-0.0086
500
0.0128
500
300
500
200
0.0034
100
0.0033
100
200
200
190
(00)
1100
1200
1990
1000
100
000
000
800
990
1000
1100
1000
(a) Malicious URLs Dataset
(b) EMBER Dataset
Figure 16: FPR for N 50, 100, 200,300, 1400 and A: 20, 50, 100, 200, 300, ..... 1500 with
N.
Appendix G Experiments with artificial datasets
We experimented with artificial datasets. Fast PLBF++ is faster to construct than fast PLBF. However, fast PLBF+ is not theoretically guaranteed to be as accurate as PLBF, except when the score distribution is "ideally monotonic." Therefore, we evaluated the accuracy of fast PLBF++ by creating a variety of datasets, ranging from data with monotonicity to data with little monotonicity. The results show that the smaller the monotonicity of the score distribution, the larger the difference in accuracy between fast PLBF++ and PLBF. We also observed that in most cases, the false positive rate for fast PLBF+ within 1.1 times that of PLBF, but in cases where there is little monotonicity in the score distribution, the false positive rate of PLBF++ can be up to 1.85 times that of PLBF.
Here, we explain the process of creating an artificial dataset, which consists of two steps. First, as in the original PLBF paper [14], the key and non-key score distribution is generated using the Zipfian distribution. Figure (a) shows a histogram of the distribution of key and non-key scores at this time, and Figure 20(a) shows g:/h; (i 11=1... 1... N) when N = 1, 000. This score distribution is ideally monotonic. Next, we perform swaps add non- monoooonniict to the score distribution. Swap refers to changing the scores of the elements in the two adjacent segments so that the number of keys and non-keys in the two segments are swapped. Namely, an integer i randomly selected from ......,, 11.2...,NN--. N)1 and the scores of elements in the i-th segment are changed so that they are included the (i + 1)-th segment, and the scores of elements in the (i + 1)-th segment are changed to include them in the i-th segment. Figures 19(b) to 19(1) and Figures 20(b) 20()) show the histograms of the score distribution and g:/h, /,, (i = 1... .N) for 10, 10 that as the number of swaps increases, the score distribution becomes more monotoni.... For each case of the number of swaps, 10 different datasets were created using 10 different seeds.
10 swaps, respectively. can be seen
Figure 21 shows the accuracy of each method for each number of swaps, with the seed set to 0. Hyperparameters for PLBFs are set to N 1, 000 and k PLBF++ achieve better Pareto curves than the other methods for all datasets. It can also be seen that the higher the number of swaps, the more often there a difference between the accuracy of fast PLBE++ and fast PLBE
can be seen that fast PLBF and fast
Figure 22 shows the difference in accuracy between fast PLBF++ and fast PLBF for each swap count. Here, the "relative false positive rate" is the false positive rate of fast PLBF++ divided by that of PLBF constructed with the same hyperparameters and conditions (note that fast PLBF constructs the same data structure as PLBF, so the false positive rate of fast PLBF is the same as that of PLBF). We created 10 different datasets for each swap count and conducted experiments for each dataset and method with a memory usage of 0.25Mb, 0.5Mb, 0.75Mb, 1. 1.0Mb, 1.25Mb, and 1.5Mb. Namely, we compared the false positive rates of fast PLBF and fast PLBF++ under 60 conditions for each swap count. The result shows that fast PLBF++ consistently achieves the same accuracy as PL.FF in total of 240 experiments where the number of swaps 10 or less. It also shows that in the experiments where the number of swaps is 10" or less, the false positive rate of fast PLBF++ is less than 1.1 times
22

---

Insert keys to Bloom fllter
Train machine learning model
Find optimal para parameters
200
Construction Time [s]
100
PLBF
Fast (Proposed)
Fast PLBF++ (Proposed)
(for relaxed problem)
(a) Malicious URLs Dataset
200
Construction Time [s]
100
5.0
0.0
PLBF
PLBF (for relaxed problem)
Fast PLBF (Proposed)
Fast PLBF+ (Proposed)
(b) EMBER Dataset
Figure 17: Construction time. The memory usage of the backup bloom filter is 500 Kb, and the hyperparameters PLBFs are = 1, 000 and k 5.
that for PLBF, except for 14 cases. However, in the cases of 10 swap counts (where there is almost no monotonicity in the distribution). the false positive rate for fast PLBF++ is up to 1.85 times that for PL.B.
23

---

Bloom filter
Ada-BF
Sandwiched LBF
PLBF
PLBF (for relaxed problem)
Fast PLBF (Proposed)
Fast PLBF+ (Proposed)
False Positive Rate
10
10-2
0.6
0.8
1.0
1.2
1.4
1.6
1.8
2.0
Total Memory Usage [Mbit]
(a) Malicious URLs Dataset
False Positive Rate
10
10
1.4
1.6
1.8
2.0
2.2
2.6
2.8
3.0
Total Memory Usage [Mbit]
(b) EMBER Dataset
Figure 18: Trade-off between memory usage and FPR. The hyperparameters for PLBBs are 000 and k 5.
24

---

Postive
Nagalive
Posilive
Negalive
Count
COIRTTY
Score
Score
(a) swaps (score distribution ideally monotonic)
(b) swaps
Nagalive
Nagalive
Court
COIRT
Score
Score
Score
(c) 10 swaps
10 swaps
Nagative
Negalive
Count
COLnTE
Score
Score
Score
Score
(e) 10a swaps
10 swaps
Nagativa
Nogalivo
Count
Count
10 swaps
(h) 107 swaps
Positive
Negattve
Count
Count
(i) 10a
swaps
Figure 19: Score distribution histograms of artificial datasets. All figures with the seed 0.
25

---

18
15
9//
0.
(a) swaps (score distribution ideally monotonic)
(b) swaps
10
200
(c) 10a swaps
10a swaps
(e) 10 swaps
10 swaps
(g) 10th swaps
(h) 10 swaps
9.hh
12
( 10 swaps
Figure 20: Ratio of key to non-key of artificial datasets. All figures are with the seed set to 0.
26

---

Bloom filter
Ada-BF
Sandwiched LBF
Fast PLBF (Proposed)
Fast PLBF++ (Propased)
False Posilvv Rale
False Posifve Rate
10
Total Memory Ussaee [Mbrt]
Total Memory Usage [Mbit)
(a) O swaps (score distribution is idcally monotonic)
(b) 10 swaps
False Posilive Rale
False Positive Rate
10
0.0
62
644
69
08
1.0
1.4
0.2
0.4
08
0.8
12
Total Memory Usage [Mbil]
Total Memory Usage (Mbil)
(c) 10 swaps
(d) 10 swaps
False Plsilive Ralte
False Posirive Rate
10
10"
0.0
14
02
DE
en
Total Memory Usage [Mbr]
Total Memory Usage (Mbit)
(e) 10 swaps
(I) 10 swaps
Faise Pasilive Rale
False Positive Rate
10
Total Memory Ussge [Mbil]
Total Memory Usage (Mbit)
g 10 swaps
(h) 10" swaps
False Posilive
10
10"
02
04
05
0.3
1.0
1.0
Total Memory Usage [Mbil]
(i) 10" swaps
Figure 21: Trade-off between memory usage and FPR for artificial datasets. All figures are with the seed set to O. The hyperparameters for PLBFs are N = 1, 000 and
5.
27

---

Relative False Positive Rate
1.8
1.6
1.4
1.2
1.0
0
10a
102
103
10*
105
10
107
10
Number of Swaps
Figure 22: Distribution of the "relative false positive rate" of fast PLBF+ for each swap count. The "relative false positive rate" the false positive rate of fast PLBF++ divided by that PLBF constructed with the same hyperparameters and conditions.
28


Reviews:
[{"review_id": "75eVlUN55V", "reviewer": "Reviewer_cwdf", "summary": "This paper improves upon the Partitioned Learned Bloom Filter (PLBF), which is an essentially optimal learned Bloom filter introduced in ICML 2021. Construction time of PLBF is $O(N^3k)$, where $N > k$ are hyper-parameters. The authors show how to construct the same filter much more quickly; their Fast Partitioned Learned Bloom Filter (FPLBF) produces the same filter as PLBF and takes only $O(N^2k)$ time to construct. They also propose the fast PLBF++ algorithm that runs in even quicker $O(Nk\\log N + Nk^2)$ time. It outputs the same filter under natural assumptions on the input and is essentially just as good experimentally. Extensive experimental evaluation with real world datasets and ablation studies support the claims and demonstrate significant practical speedups.", "questions": "Figure 12 shows that $N=50$ or $N=100$ max are sufficient for minimizing the false positive rate (for a given memory budget) for $k=5$. Figure 13 indicates that $k=100$ or even higher is required for minimizing the false positive rate for $N=1000$. Could you please find the $(N,k)$ combination that approximately minimizes the false positive rate and then measure and show the construction times for that? Could you please also zoom into the FPR plots around their minima without using log-scale on the x-axis (perhaps in the appendix) as I could not determine the location of the FPR minima in terms of $N$ even when I viewed the enlarged pdf on my screen,", "limitations": "Yes, it's adequate.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1) Bloom filters are a ubiquitous approximate set membership data structure. Their combination with learned predictors has been an active and fruitful direction of research in the past years. This paper is another significant step.\n2) The authors are right (and the first to discover to the best of my knowledge) spot the redundancy in the PLBF paper and save an $O(N)$ factor.\n3) Fast PLBF++ is a good connection with the monotone matrix max problem. The authors prove that under natural assumptions it provides the same output even quicker. It works well with real data even if the assumptions are not 100% satisfied. \n4) Detailed experimental evaluation, especially kudos for the ablation in Section 5.3.", "weaknesses": "1) The PLBF authors were rather sloppy by rebuilding the same dynamic programming table from scratch when all they needed was adding another ''row'' to it. In fact looking at eq (2) in the paper it's quite obvious that superscript $j$ plays no role in $\\mbox{DP}^j$ and a single DP table suffices. Nevertheless, credit is due for spotting this.\n2) Practical runtime gains are potentially overstated as they depend on the choice of hyper-parameters $N$ and $k$. The paper shows runtime improvements for $N=1000$ and $k=5$, these hyperparameters are copied from the PLBF ICML 2021 paper, where they appeared without much justification. The (excellent) ablation experiments suggests that much smaller $N$ and much larger $k$ are optimal, which would decrease the runtime gaps in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive evaluation of our paper. Let us answer the questions.\n\n> Could you please find the (N,k) combination that approximately minimizes the false positive rate and then measure and show the construction times for that?\n\nIn Appendix E, we performed an ablation study on the hyperparameters N and k. In response to this comment, we performed an additional, more comprehensive ablation study. \n\nFirst, we performed a coarse grid search with N=10,20,50,100,200,500,1000 and k=3,5,7,10,20,50,100,200,500,1000 (note that k<=N). The memory usage of the backup Bloom filters was fixed at 500 Kb. The results are summarized as follows. \n\nIn the case of URL dataset, \n- for PLBF: the FPR was minimal (1.25%) when (N, k)=(1000, 500). \n  - the construction time is 7.5 hours.\n- for fast PLBF: the FPR was minimal (1.25%) when (N, k)=(1000, 500). \n  - the construction time is 95.0 seconds (284 times faster than original PLBF).\n- for fast PLBF++: the FPR was minimal (1.26%) when (N, k)=(1000, 500). \n  - the construction time is 13.1 seconds (2064 times faster than original PLBF).\n\nIn the case of Ember dataset, \n- for PLBF: the FPR was minimal (0.829%) when (N, k)=(500, 50). \n  - the construction time is 366 seconds.\n- for fast PLBF: the FPR was minimal (0.829%) when (N, k)=(500, 50). \n  - the construction time is 7.98 seconds (45 times faster than original PLBF).\n- for fast PLBF++: the FPR was minimal (0.857%) when (N, k)=(200, 50). \n  - the construction time is 5.67 seconds (64 times faster than original PLBF).\n\nThese results coarsely give the (N, k) combination that minimizes the FPR. They also demonstrate that for the coarse optimal (N, k) settings, the original PLBF requires a substantial construction time, ranging from several minutes to several hours. On the other hand, our two proposed methods take only a few seconds to tens of seconds to build.\n\n> Could you please also zoom into the FPR plots around their minima without using log-scale on the x-axis (perhaps in the appendix) as I could not determine the location of the FPR minima in terms of N even when I viewed the enlarged pdf on my screen.\n\nNext, we performed a more detailed grid search of the fast PLBF accuracy around (N, k)=(1000, 500) for the URL dataset and (N, k)=(500, 50) for the Ember dataset. Specifically, N=500,750,1000,1250,1500 and k=200,400,500,600,800,1000,1250,1500 for the URL dataset and N=200,400,500,600,800,1000 and k=20,40,50,60,80,100 for the Ember dataset (again, note that k<=N). The memory usage of the backup Bloom filters was fixed at 500 Kb.\n\nIn the case of URL dataset, \n- the FPR was minimal (1.23%) when (N, k)=(1500, 800). \n\nIn the case of Ember dataset, \n- the FPR was minimal (0.829%) when (N, k)=(500, 50).\n\nThis comprehensive ablation study and its appropriate visualization will be added to the final version.\n"}, {"review_id": "0PLyVXkz30", "reviewer": "Reviewer_aq8D", "summary": "The paper presents two improvements of the algorithm PLBF (Partitioned Learned Bloom Filter), called fast PLBF and fast PLBF++. PLBF learns the distribution structure and uses it to minimize the memory allocation. An ML model (LightGBM is used in this paper) is trained to predict a score between [0,1] indicating set membership probability. The score space is divided into N segments and then grouped into k<N regions that will each use a backup Bloom filter. The grouping of N segments into k region is formulated as an optimization problem and solved by dynamic programming, with time complexity O(N^3 k) for PLBF. The new method fast PLBF carefully refines the dynamic programming steps (by avoiding some redundant computation) and builds the same data structure but in O(N^2 k). The fast PLBF++ can construct a slightly different data structure, but faster; under some conditions, fastPLBF++ also constructs the same data structure. Experimental evaluation shows the performance of the two schemes.", "questions": "I would like to see more space devoted in the paper to the explanation of fast PLBF compared to PLBF. Can you explain in more detail, or even intuitively, what computation is redundant in PLBF and how it is avoided by the new scheme? All of it is deferred to the appendix, but even there it is not very clear. This is one of the main points of the paper and I think more justification should be included in the paper itself, not in the appendix.", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Learned Bloom filters are a useful data structure. Improving the construction time for PLBF allows for the construction of filters for larger values of N, which improves their performance. The experimental evaluation is good.", "weaknesses": "It is not clearly explained what computations are redundant in PLBF and how they are avoided by fast PLBF.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's insightful comments. We are happy to provide additional clarification on the unclear points raised.\n\n> It is not clearly explained what computations are redundant in PLBF and how they are avoided by fast PLBF. \n\n> Can you explain in more detail, or even intuitively, what computation is redundant in PLBF and how it is avoided by the new scheme? \n\n> This is one of the main points of the paper and I think more justification should be included in the paper itself, not in the appendix.\n\nLet us explain our approach intuitively. While PLBF builds many DP tables, our fast PLBF builds only one DP table and reuses it many times. Specifically, by exploiting the fact that the largest DP table $\\mathrm{DP}^N_\\mathrm{KL}$ contains other smaller DP tables, fast PLBF builds only $\\mathrm{DP}^N_\\mathrm{KL}$ and reuses it. This is a very simple speedup method, but it only becomes apparent by reorganizing the optimization problem and solution (which was not well organized in the original PLBF paper) and discovering that $j$ plays no role in a $\\mathrm{DP}^j_\\mathrm{KL}$ computation.\n\nLet us further elaborate on the optimization problem and how PLBF and fast PLBF solve it. To construct PLBFs, we need an optimal $\\mathbf{t}$ and $\\mathbf{f}$, where $\\mathbf{t}$ are the thresholds for partitioning the score space into several regions and $\\mathbf{f}$ are the false positive rates for each region. To find the optimal values, we must iterate over all the candidates of the “rightmost region” and finds the optimal $\\mathbf{t}$ and $\\mathbf{f}$ for each candidate (see Appendix C of the original PLBF paper for details). Since there are $N-k+1$ candidates of the rightmost region, there are $N-k+1$ “problems” to solve. PLBF solves $N-k+1$ problems separately, i.e., it computes the $N-k+1$ DP tables separately. Fast PLBF, on the other hand, computes only one DP table and leverages it repeatedly to solve $N-k+1$ problems. We mathematically showed that the results of PLBF and fast PLBF are identical.\n\nWe will add this discussion to the final paper and detail the description of fast PLBF."}, {"review_id": "UXxQPSv5Vk", "reviewer": "Reviewer_SSjS", "summary": "The authors propose faster dynamic programming variants of the learned partitioned Bloom filter data structure of Vaidya et al. that requires $O(N^3 k)$ time.\nTwo solutions are proposed, the first constructs the same data structure in time $O(N^2 k) $ time, and another, that constructs a potentially different structure in $O(Nk\\log N+Nk^2)$ time.", "questions": "1. How do you set $N$?\n\n2. Is the error monotone in $N$? (If so, the answer to (1) is simple -- use the largest feasible $N$. I'm not sure otherwise.)\n\n3. Can you explain the differences between your solutions and existing DP acceleration techniques?\n\n4. Vaidya et al. also present an algorithm with runtime $O(N^2 k)$ in their paper, under some assumptions. Can you please comment about whether this is the same conditions you use in Fast PLBF++?\n\n5. In cases where Fast PLBF++ yields a different data structure than PLBF, can you bound the increase in error?", "limitations": "None", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "A significant speedup of a recent paper on a hot and interesting topic. Also, a nice empirical gains in the construction speed.", "weaknesses": "In essence, the authors propose DP acceleration techniques without explaining the difference from off-the-shelf methods.\nMany such solutions are known for decades (e.g., see https://courses.engr.illinois.edu/cs473/sp2016/notes/06-sparsedynprog.pdf), and while it is possible that they don't cover the exact problem, they seem very similar. \n\nWhile the authors propose to use the SMAWK algorithm, it seems that the wrapper needed to get from it to the actual dynamic program might also be known.\nFor example, (https://www.sciencedirect.com/science/article/pii/002001909090215J) solves the following problem:\n\n$$ E[j] = \\min_{0\\le i<j} D[i] + w(i,j)\\ .$$\n\nThis looks nearly identical to your Equation (2), and I believe that a small massaging of the notations might yield your $O(N^2 k)$ solution.\nWithout explaining the difference from known DP acceleration methods, it is very hard to assess the novelty of the presented algorithms.\n\n\nI am also unclear about how you set $N$ in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's insightful comments. We are happy to answer the questions raised.\n\n> How do you set N?\n\nFinding the optimal N and k is difficult, but setting N to about 1000 and k to about 100 may be a good choice. The additional ablation study using two real-world datasets shows the following (for details, see the response to reviewer cwdf):\n\n- The FPR is small enough when N\\~1000 and k\\~100. A larger N or k seems not to cause a much further small FPR.\n\n- When N\\~1000 and k\\~100, the proposed methods take only a few seconds to build (although the original PLBF takes more than an hour).\n\nAlthough it is not sure whether N\\~1000 and k\\~100 make the FPR small enough for unknown datasets, our proposed methods are beneficial because they can always be constructed faster than the original PLBF for any N and k.\n\n> Is the error monotone in N? (If so, the answer to (1) is simple -- use the largest feasible N. I'm not sure otherwise.)\n\nAs N increases, the accuracy improves (although not necessarily monotonically), but at the same time, construction time increases. Therefore, depending on the application, N should be determined appropriately, considering the trade-off between accuracy and construction time.\n\nIn the case of the original PLBF, the construction time significantly increases as N increases, while the proposed methods do not suffer from such long construction times. Hence, it is easier to balance accuracy and construction time using the proposed methods.\n\n> Can you explain the differences between your solutions and existing DP acceleration techniques?\n\nThe two methods we proposed are not novel DP acceleration methods but methods that accelerate the PLBF construction by focusing mainly on the DP part of the PLBF construction.\n\nFirst, fast PLBF is not a DP acceleration method; it is a method that achieves acceleration by solving a large number of “problems” collectively, whereas PLBF solves them separately. PLBF iterates over all the candidates of the rightmost region and finds the optimal thresholds (i.e., t) and false positive rates (i.e., f) for each candidate. Since there are N-k+1 candidates of the rightmost region, there are N-k+1 \"problems\" to solve (see Appendix C of the original PLBF paper for details). PLBF solves N-k+1 problems separately, i.e., it computes the N-k+1 DP tables separately. Fast PLBF, on the other hand, computes only one DP table and leverages it repeatedly to solve N-k+1 “problems.” We mathematically showed that the results of PLBF and fast PLBF are identical.\n\nSecond, indeed fast PLBF++ introduces a faster calculation of DP and is exactly the same as fast PLBF except for the DP part. However, for this acceleration, it is necessary to discover that \"monotonicity\" often appears in the DP calculation for PLBF construction. We provided the following:\n\n- An intuitive explanation for the appearance of \"monotonicity\" (see Figure 7).\n- A theoretical proof (Theorem 4.3) that the perfect \"monotonicity\" appears under the assumption that the score distribution is “ideal” (this assumption is specific to the PLBF problem and is a natural assumption).\n- Experimental results indicating that fast PLBF++ achieves almost the same accuracy as (fast) PLBF in many cases, even when the score distribution is not ideal (see Section 5 and Appendix G).\n\nIn conclusion, fast PLBF++ is not novel as a DP speedup method, but it is a speedup method proposed by careful analysis of the PLBF problem.\n\nWe will include the above discussion in the final manuscript. In addition, we must further discuss the relationship between the proposed methods and general DP acceleration methods pointed out by the reviewer SSjS. Such a discussion will solidify the theoretical connection between our approach and existing DP acceleration methods. Thanks again for the informative and insightful comments.\n\n> Vaidya et al. also present an algorithm with runtime O(N^2k) in their paper, under some assumptions. Can you please comment about whether this is the same conditions you use in Fast PLBF++?\n\nThese two assumptions are different. \n\nPLBF's $O(N^2 k)$ method assumes that \"the false positive rate is less than 1 for all regions when optimal thresholds and false positive rates are set for each region\" (our experiments in Appendix F show that this method can be very inaccurate compared to PLBF's $O(N^3 k)$ method). \n\nOn the other hand, fast PLBF and fast PLBF++ do not make this assumption. The assumption made by fast PLBF++ is that \"the fraction of positive elements among the elements in the $i$-th segment ($g_i/h_i$) increases monotonically with increasing $i$\". Under this assumption, we can prove that fast PLBF++ achieves the same accuracy as PLBF. However, even when this assumption does not hold, fast PLBF++ and PLBF experimentally achieve almost the same accuracy.\n\n> In cases where Fast PLBF++ yields a different data structure than PLBF, can you bound the increase in error?\n\nAs mentioned in the Limitation section of the main text, it is a future work to theoretically bound the increase in error. Currently, we have found the following:\n\n- Theoretical proof (provided in Appendix C) shows that fast PLBF++ is consistent with PLBF under ideal conditions.\n- Experiments on real datasets (in Section 5) show that fast PLBF++ consistently achieves almost the same accuracy as PLBF.\n- Experiments on many artificial data (in Appendix G) show that the accuracy of fast PLBF++ rarely seems to deteriorate catastrophically, unless the situation is very far from ideal."}, {"review_id": "G7llblnm57", "reviewer": "Reviewer_YWKv", "summary": "The authors propose two methods to reduce the construction time of the partitioned learned Bloom filter (PLBF): \n1. Fast PLBF, which can construct the same data structure as PLBF but with a smaller time complexity of O(N^2k) and 2. Fast PLBF++, which can construct the data structure with a time complexity of O(Nk log N + Nk^2) but may not necessarily construct the same data structure as PLBF. Fast PLBF++ is almost as memory efficient as PLBF. \n\nThe authors prove that fast PLBF++ has the same data structure as PLBF when the distribution satisfies a certain constraint.\n", "questions": "My concerns are raised above.", "limitations": "The authors may include a discussion on the potential negative societal impact of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The algorithm and presentation are straightforward and strong theoretical results are provided. \n\n2. The author shows empirically that their construction keeps an edge in practice and can lead to faster PLBF construction.\n\n", "weaknesses": "The authors may provide further ablation studies on the sensitivity of hyper-parameters in practice and discuss more about societal impact.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's positive assessment of our paper. We would like to address their concerns.\n\n> The authors may provide further ablation studies on the sensitivity of hyper-parameters in practice\n\nIn response to this comment, we performed an ablation study to verify the sensitivity of the hyperparameters. The results showed that changing the hyperparameters from (N,k)=(1000, 100) to some extent does not dramatically change the false positive rate. In other words, the accuracy is robust to the hyperparameters, at least around (N,k)=(1000, 100). (The reason for considering around (N,k)=(1000, 100) is that previous ablation studies have shown that setting N to about 1000 and k to about 100 is appropriate to keep the false positive rate small and the build time short. For details, see the ablation studies mentioned in response to reviewer cwdf.) \n\nSpecifically, we performed a grid search for N=800, 850, 900, ..., 1200, and k=80, 85, 90, ..., 120. The memory usage of the backup Bloom filters was fixed at 500 Kb. The results are summarized as follows. \n\nIn the case of URL dataset, \n- best case (minimal FPR case): when (N, k)=(950, 120), the FPR was 1.26%.\n- worst case (maximal FPR case): when (N, k)=(850, 90), the FPR was 1.31%, i.e., 1.037 times larger than the minimum.\n\nIn the case of Ember dataset, \n- best case (minimal FPR case): when (N, k)=(1100, 115), the FPR was 0.830%.\n- worst case (maximal FPR case): when (N, k)=(1200, 80), the FPR was 0.870%, i.e., 1.047 times larger than the minimum.\n\nThus, at most, the false positive rate is only 1.037 or 1.047 times larger than the best case. Therefore, around (N, k)=(1000, 100), the accuracy is robust to hyperparameters.\n\nThis ablation study will be included in the final version.\n\n> The authors may … discuss more about societal impact.\n\n> The authors may include a discussion on the potential negative societal impact of their work.\n\nThe applicability of fast PLBF is broad, including databases and networks. For example, as our experiments suggest, it can be used to detect blacklisted malicious URLs or files. Furthermore, it may improve cache efficiency in databases or optimize routing tables in networks, as in the case of Bloom filters. The scope of fast PLBF fully encompasses and is broader than that of PLBF. In particular, our fast PLBF is expected to have a significant advantage over the original PLBF when applied to applications where the set to be retained changes frequently. This is because in such use cases, the PLBF must be rebuilt repeatedly to maintain accuracy, and fast PLBF has a much shorter construction time than PLBF. \n\nIn addition, we believe that fast PLBF is unlikely to have a negative societal impact because it speeds up the construction of PLBF while maintaining its full accuracy.\n\nIn the final manuscript, we will expand on the use of the proposed methods in the practical/social applications discussed above."}]

Author rebuttal:

Meta-review: Authors presents two improvements of PLBF (Partitioned Learned Bloom Filter), called fast PLBF and fast PLBF++.  The results are sound, interesting and generally appreciated by all the reviewers. There were some concerns. After the rebuttal and thorough discussions, reviewers unanimously agreed that the paper is above the bar for publications.
Decision: Accept (poster)