Optimizing Learned Bloom Filters: How Much Should Be Learned?

Abstract

The learned Bloom filter (LBF) combines a machine learning model (learner) with a traditional Bloom filter to improve the false positive rate (FPR) that can be achieved for a given memory budget. The LBF has recently been generalized by making use of the full spectrum of the learner's prediction score. However, in all those designs, the machine learning model is fixed. In this letter, for the first time, the design of LBFs is proposed and evaluated by considering the machine learning model as one of the variables in the process. In detail, for a given memory budget, several LBFs are constructed using different machine learning models and the one with the lowest FPR is selected. We demonstrate that our approach can achieve much better performance than existing LBF designs providing reductions of the FPR of up to 90% in some settings.