Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: In this paper, the authors proposed Search Data Structure Learning (SDSL), which they claim to be a generalization of the standard Search Data Structure. They also present a new metric called Sequential Search Work Ratio (SSWR) to evaluate the quality and efficiency of the search. They introduced a new loss called F-beta Loss, showing their algorithm is better than two previous results, MIHash (Cakir et al. 2017) and HashNet (Cao et al. 2017).

I appreciate the key message the paper is trying to convey: we need the formal definition or mutual agreement on the problem as well as the correct evaluation metrics to push forward a research area. However, I have several major concerns about the contribution of this paper. 

1. I do not see a formal definition of SDSL. Definition 3.1 is just a definition of matching and non-matching relations. 
2. What is new in the metric defined in Definition 3.4? The denominator is constant for all search methods. C(.,.,.) is the cost of re-ranking, and w0 is the cost of searching (filtering the candidate). 
3. There is no theoretical or empirical comparison/evaluation of the proposed metric. The calculations in Appendix A are very standard calculations. It is unclear about the innovation of this metric from a theory perspective. In experiments, the authors directly use SSWR, and there is no justification on why this is the right metric.

Before proposing the new loss, etc., I suggest the authors could go back and justify the metric's effectiveness. Otherwise, it is hard to conclude if this paper has made any progress.

=========================================

Thanks for the rebuttal and revision. My first concern has been addressed. However, I still found the proposal lack empirical or theoretical proof, so I am not convinced the contribution is principle enough. I decide to keep my original score.

review_title: The paper needs to justify the new metric.

final_score: rating: 4: Ok but not good enough - rejection
review_content: 
This article presents a new evaluation metric that improves upon hamming distance of two. Meanwhile, a new F-beta loss is proposed with advantages over other learn to hash methods in this evaluation metric. 



Strength:
A new formulation on both evaluation metric and a new loss function


Weakness:
1. Claim: In the introduction of the paper, different data structures such as graph-based Efanna, HNSW, and ONNG. However, in the following sections of the paper, the author does not discuss the possibility of SWR pr SSWR on these methods. Is SSWR only designed for binary codes based information retrieval?
2. Definition of cost: In Appendix A, the cost is estimated by how many calls in expectation
are needed to find those k elements if we sample from S uniformly without replacement. Is there any justification for why we assume the k elements by uniform sampling? In hashing based retrieval, the sampling is based on a distribution with PDE monotonic to the distance [1]. In this case, is the cost estimated correctly?
3. Comparison with other evaluation metrics: Is there any discussion of SSWR with evaluation metrics other than p@2. For instance, mAP, queries per second(QPS), and speedups over brutal force search. Is higher QPS or higher speedups over brutal force equivalent to higher SSWR?
4. Experiments: This paper only presents results in image search settings.  Is there more comparison of f-beta loss in different search settings? For instance, (1) ANN search with l2 or cosine similarity. (2) Maximum Inner Product Search (3) Cross-modal retrieval such as text-image search.

[1]Mutual Information Estimation using LSH Sampling https://www.semanticscholar.org/paper/Mutual-Information-Estimation-using-LSH-Sampling-Spring-Shrivastava/7241d1e839fdb69f7f0cc70220ad055e8900946c

review_title: A new evaluation metric and a new loss for search via binary codes

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper is generally well written, and the authors target on an important and challenging problem of learning how to search. Search is a complex problem, and people designed various data structures to handle different kinds of search problems. The authors generalize these searching data structures by search data structure learning. The idea is novel and very interesting.

Then, the authors design SSWR metric evaluate the efficiency and quality of the search process. And the authors design ELBA(Efficient Learning Binary Access) by proposing a novel loss function and neural networks to create a discrete binary code(s) for both the queries and documents. And the authors conduct several experiments on NoisyMnist dataset to compare with several methods to show the advantage of the proposed framework.

MNIST dataset is a simple and small dataset, so more challenging datasets (such as SIFT-1M and GIST-1M) used in the search community are suggested to make the paper more convincing.

=======================

After reading all the review comments and rebuttals, I would like to change my score to 4. 
The paper is interesting, but more detailed analysis and experiments are needed to make the work more clear and convincing.

review_title: This paper proposes a general search framework called Search Data Structure Learning. A learning based method is designed to learn how to search in the database. In order to train the whole process, a novel loss function is designed and differentiable parameterized networks are adopted. The authors also design a novel metric to evaluate the performance. Experiments on NoisyMnist are conducted to demonstrate the effectiveness of the proposed method.

final_score: rating: 3: Clear rejection
review_content: This paper proposes a new objective to learn representations that allow for efficient and accurate search with the Multi-Bernoulli Search data structure. The motivation for such a scheme is strong and the preliminary empirical results demonstrate the utility of using the proposed representation learning objective and the data structure. 


However, I am currently leaning towards a reject because of two main reasons: The first being the clarity of the presentation in the paper that makes it hard to identify (i) novel contributions, (ii) key algorithmic and technical details -- the main paper is supposed to be somewhat self-sufficient; with the current version, it was significantly hard for me to follow through the presentation even when repeatedly referring to the supplement. The second reason is the lack of positioning of the proposed scheme/objective/data structure to a long line of research on the use of machine learning (with novel metrics/objectives and data structures) for search, including the learning of space partitioning trees [A, B, C], locality sensitive hashes [E] and representations [D] -- it is quite possible that the proposed scheme is solving a different and/or more general problem but I believe it would be useful to connect this "Search Data Structure Learning" to the existing work on "Learning to Search".


Beyond the aforementioned high level comments, please find the following specific comments/questions that should be addressed:

- The set of relations $\mathcal{R}$ and the per-database $\mathcal{R}_D$ could use further motivation as to how they relate to search and/or relate to the task of learning search data structures. 
- It is not clear why the distinction between "absolute" and "relative" is necessary in the context of the problem being targeted in this paper.
- The SSWR definition is unclear to me and can use more exposition. It is not clear that $\delta_t, t = 1, \ldots, T$ is a sequence of sets. Also, it is not explained why the oracle costs are only incurred for the final $\delta_T$ and not all intermediate ones (unless $\delta_{t-1} \subseteq \delta_t$) or to the complete $\cup_{i=1}^T \delta_t$.
- At the end of section 3, after presentation of SSWR, it is not clear why we are minimizing for a search sequence generator $\mathcal{G}$ that is aggregated over database-query pairs $(D, q)$ -- wouldn't we learn a data structure per database (as is done for data structures used for nearest-neighbor search)? Can this be clarified, and if it is deliberate, please motivate the need and advantage of learning across databases.
- The algorithm description is very hard to follow -- there are M back-end data structures and also the learned representation is used to generate M probable back-ends to insert in and T probable back-end to search from. It is not clear how the search involves $T$ passes over the $M$ back-ends. It would be good to clarify in the main paper that the "outcomes" are keys for each backend and all $T$ keys are tried in all $M$ back-ends.
- How are we leveraging multiple databases as shown in the previous loss function?
- The halting mechanism requires better presentation and clarification. It makes intuitive sense. But the presentation of the training algorithm (at least in the main paper) seems insufficient to provide enough context about the specifics of the halting mechanism.



[A] Li, Z., Ning, H., Cao, L., Zhang, T., Gong, Y., & Huang, T. S. (2011). Learning to search efficiently in high dimensions. In Advances in Neural Information Processing Systems (pp. 1710-1718).
[B] Cayton, L., & Dasgupta, S. (2008). A learning framework for nearest neighbor search. In Advances in Neural Information Processing Systems (pp. 233-240).
[C] Dong, Yihe, et al. "Learning Space Partitions for Nearest Neighbor Search." ICLR 2020.
[D] Sablayrolles, A., Douze, M., Schmid, C., & Jegou, H. (2018, September). Spreading vectors for similarity search. In International Conference on Learning Representations.
[E] Wang, J., Liu, W., Kumar, S., & Chang, S. F. (2015). Learning to hash for indexing big data -- A survey. Proceedings of the IEEE, 104(1), 34-57.

review_title: Interesting line of research; lacks sufficient clarity and positioning with respect to relevant existing literature

Meta-review: This paper addresses an interesting problem and all reviewers agree.  Most reviewers found the paper difficult to understand and it was hard to see the novel contributions.    The paper will need a significant revision before publication.
Decision: Reject