A Model for Learned Bloom Filters, and Optimizing by Sandwiching
Recent work has suggested enhancing Bloom filters by using a pre-filter, based on applying machine learning to determine a function that models the data set the Bloom filter is meant to represent. Here we model such learned Bloom filters, with the following outcomes: (1) we clarify what guarantees can and cannot be associated with such a structure; (2) we show how to estimate what size the learning function must obtain in order to obtain improved performance; (3) we provide a simple method, sandwiching, for optimizing learned Bloom filters; and (4) we propose a design and analysis approach for a learned Bloomier filter, based on our modeling approach.
This a purely theoretical paper that is concerned with modeling learned Bloom filters (which are a combination of the statistical filter with the backup classic-Bloom eliminating false negatives arising from the use of the statistical model). In addition to analyzing this method, it proposes a sandwiched version of the learned Bloom-filter (classic-Bloom, statistical-filter, classic-Bloom). It also derives a relationship between the size of the learned model and its associated false positive and negative rates, which entail the same or better OVERALL false positive rate of the learned Bloom filter.  I thank the author(s) for the interesting read. I have found it quite educational. However, I have some mixed feelings about the paper. Below, I talk about these in details. But, here are the few highlights: i) Authors focus primarily on the analysis of the false positive rate at a given bit budget. I think it is an important step. However, as noted by Kraska et al an advantage of the learned filter is that it can use the given bit budget more efficiently. In particular, computing the prediction of the neural network uses easy-to-parallelize operations with localized memory accesses and do not suffer from branch misprediction. Furthermore, if run on GPUs they can use of a much faster GPU memory (matrix multiplication on CPU can be very memory-efficient too). I think this warrants at least a discussion.   ii) Perhaps, I am missing something but Section 3.2 is not very useful, because it does not tell how to choose tau without actually running experiments on the test set.  iii) It looks like authors make somewhat inaccurate claims about properties of the classic Bloom filters.   *PROS*  Paper makes the initial and certainly important step towards analyzing learned Bloom filters.  It provides useful examples, which shed light on behavior/properties of the learned Bloom filters: I find these quite educational.  In particular, it illustrates how easy performance of the Bloom filters can deteriorate when there is a mismatch   It proposes two extensions of the Bloom filters, in particular, a sandwiched Bloom filter.  *CONS*  It feels that the paper was somewhat hastily written (see some comments below). The prose is somewhat hard to understand. In part, it is because of the long sentences (sometimes not very coherent). Sometimes, it is because major findings and observations are buried somewhere. I would encourage you to have some short list of easy-to-grasp high-level overview of the findings. For example, it would be a pity to miss notes in lines 238-242.  The discussion in lines 71-81 makes an assumption that our hash functions operate like random and independent variables. Of course, this is not true in practice, but how much is the difference in realistic settings? Furthermore, this makes you say that you can estimate the false positive rate from any subset of queries. My guess would be that this is true only for good-enough families for hash functions. Although classic Bloom filters should be much less susceptible to distribution changes, I don't think they are total immune to them. In particular, I believe there may be adversarial sequences of keys with much worse FP rate. Discussing these aspects seems to would have been helpful. Last, but not least, as mentioned in the highlights the efficiency of the learned Bloom filters for a given number of bits can be better compared to the classic Bloom filter. In particular, because one lookup may require up to k random memory accesses. From this practical perspective, it is not clear to me if the sandwiched approach always makes sense (as it entails additional memory accesses). In particular, for roughly the same false positive ratio and comparable bit budgets, the original learned Bloom filter may be more efficient than than sandwiched version. In particular, I would like to see theory and/or experiments on this. What if we take the budget for the prefilter in the sandwiched version and give it all to the statistical filter?  *SOME DETAILED COMMENTS*   55:  universe to independently and uniformly to a number   : please check if this is grammatically correct.   63: how? Since you provide an overview anyways, it would be nice to explain that you consider a probability of setting each bit as a random independent variable. Then, not setting it to 1 kn times in a row has such and such probability.   64: Which bound do you use? I guess it's for the binomial with the Chernoff or Hoeffding inequality, but it's never bad to clarify.  67:  what the probability is than an element y will be a false positive -> what the probability is that   67:  Because of this, it is usual to talk ->  because it is tightly concentrated around its expectation, it is usual to talk   109: universe possible query keys -> universe OF possible query keys  122: and 500 -> and OF 500  123: the first half of the line has extra text  120-144: a nice useful illustration  227: it is truly to great to some analysis, but what is missing there is the relationship between \theta and F_n. It doesn't have to be theoretical: some empirical evaluation can be useful too.  238-242: This are really nice points, but it is buried deep in the middle of the paper  254-258: It is not only about improving false positive ratio at a given number of bits. The pre-filtering using a Bloom filter has a non-trivial cost, which includes several random memory accesses. The advantage of having a learned filter, which is implemented by a compact neural net, is that computation over that network is very memory-local and can be easily outsourced to GPU (and kept in a super-fast GPU memory).