Learned Bloom filters enhance standard Bloom filters by using a learned model for the represented data set. However, a learned Bloom filter may under-utilize the model by not taking full advantage of the output. The learned Bloom filter uses the output score by simply applying a threshold, with elements above the threshold being interpreted as positives, and elements below the threshold subject to further analysis independent of the output score (using a smaller backup Bloom filter to prevent false negatives). While recent work has suggested additional heuristic approaches to take better advantage of the score, the results are only heuristic. Here , we instead frame the problem of optimal model utilization as an optimization problem . We show that the optimization problem can be effectively solved efficiently, yielding an improved partitioned learned Bloom filter%DIFDELCMD < }%%% , which partitions the score space and utilizes separate backup Bloom filters for each region . 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.
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 %DIFDELCMD < }%%% , 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.
R
Learned Bloom filters enhance standard Bloom filters
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,
D
data
R
a learned Bloom filter may under-utilize the model by not taking
previous methods for learned Bloom filters do not take
R
output. The learned Bloom filter uses the output score by simply applying a threshold, with elements above the threshold being interpreted as positives, and elements below the threshold subject to further analysis independent of the output score (using a smaller backup Bloom filter to prevent false negatives). While recent work has suggested additional heuristic approaches to take better advantage of the score, the results are only heuristic. Here , we instead
learned model. Here we show how to
D
. We show that the optimization problem can be effectively solved efficiently, yielding an improved
D
partitioned learned Bloom filter
R
, which partitions the score space and utilizes separate backup Bloom filters for each region
, and using our framework derive algorithms that can achieve near-optimal performance in many cases