Partitioned Learned Bloom Filters

Bloom filters are space-efficient probabilistic data structures that are used to testwhether 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 provideimproved performance in terms of the rate of false positives, by using a learnedmodel for the represented set. However, previous methods for learned Bloom filtersdo not take full advantage of the learned model. Here we show how to frame theproblem of optimal model utilization as an optimization problem, and using ourframework derive algorithms that can achieve near-optimal performance in manycases. Experimental results from both simulated and real-world datasets showsignificant performance improvements from our optimization approach over boththe original learned Bloom filter constructions and previously proposed heuristicimprovements.