Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper proposes two new bloom filter algorithms that incorporate a learnt model for estimating if an input is in the set or not. These methods blend the space between pure BF and learnt BF with one threshold by creating regions over the score and having varying number of hash functions for each region.

I really like the paper and the approach taken. However, the experiments are on such small datasets that the true impact of these models aren't as impressive as they could be. In practice, BFs are used when dealing with millions/billions of entries to achieve real-time performance in real-world. For such applications, not only the memory is of concern but also the run-time part of the equation. In other words, if we have a learnt classifier for BF, how much will it impact the execution time vs memory usage as both are needed to be traded-off. It would have been great if the authors had experimented with larger datasets and had practical considerations for run-time and memory vs FPR investigated.
review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: This paper extends the Bloom filter learning by using the complete spectrum of the scores regions. It uses multiple thresholds and then varies the number of hash functions among different scores regions to obtain better trade-off. Detailed theoretical analysis provides guaranteed superiority over learned Bloom filter under some conditions. The experiments also show the two proposed methods outperform learned Bloom filter in FPR and memory usage.

The motivation is based on the observation that the keys' score distribution density has an opposite trend to the non-keys. Though the experiment results support this observation, some theoretical analysis on this and its relationship with the final FPR could be provided. 
review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: The paper proposed an adaptive learned bloom filter. Rather than setting a threshold of prediction score, the paper partitions the score into several intervals; for query insider each interval, the paper either uses a group of independent hash functions to hash the query in one unified bloom filter or introduce an independent bloom filter. The paper proposes efficient ways to tune the hyper-parameters, and provides the analysis of the error. Experiments on two applications show the effectiveness of the proposed methods. 

The idea seems useful. However, I have a few concerns/questions. My decision depends on the responses of the author(s). 

(1) Although the paper claims the score information can be fully exploited, the paper seems to do hashing for all possible queries. Why not set up a tau such that only when the score is below tau, we conduct the adaptive hashing? When the score is bigger than tau, we still claim an identification of the key? In this way, a bunch of keys can still be saved and without extra hashing. 

(2) The proposed method seems to be a hierarchical hashing strategy.  The first level is to hash the queries into different intervals through a score function learned from data. Why not compose another group of random hash to do the first level hashing? What is the major benefit of collecting training examples to run a machine learning model? Accordingly, why not compare with such a baseline using a group of random hashing to do the first level? 
review_title: Official Blind Review #2

Meta-review: The paper improves the Bloom filter learning by utilizing the complete spectrum of the scores regions. 

The paper is nicely written with strong motivation and theoretical analysis of the proposed model. The evaluation could be improved: all the experiments are only tested on the small datasets, which makes it hard to assess the practicality of the proposed method. The paper could lead to a strong publication in the future if the issue on evaluation can be addressed. 

Decision: Reject