Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper tried to formulate the selection of candidate set of approximate nearest neighbor (ANN) search as a multilabel classification problem, and proposed a theoretical framework with experiments to show the effectiveness of "recall vs. query time" tradeoff.
strengths_and_weaknesses: * Strengths

1) Quality: high. 
The re-formulation of ANN search as a multilabel classification is very theoretical with sufficient mathematical proofs in detail but as appendices. In terms of quality, the theoretical details are very high to show that the authors are trying to guarantee the correctness of all technical contents. However, such a theoretical way oppositely re-formulated a simple ANN search problem into another form that seems complex.

2) Clarity: high.
The whole paper is well-written and well-organized, thus it is easy to follow and understand.

* Weaknesses

Regarding the originality, significance, and completeness of the proposed method, the following concerns should be carefully considered.

1) The re-formulation of ANN search as a multilabel classification is claimed by the authors that the proposed method is an intuitive theoretical framework. However, with the multilabel information that is mapped into binary vectors, the ANN search processing actually can be easily applied to any existing lookup-based indexing methods, rather than re-formulating it into a multilabel classification problem to select candidate set of a probed ANN search. Thus, the motivation (why such as re-formulation is necessary), and the originality (how the re-formulation is originally different from the existing looku-based indexing methods if only applying the multilabel binary vectors but not think about supervised or unsupervised) are not clear nor convincing to the readers.

2) The proposed framework only targets at the measurement of "average recall vs. query time" trade-off, but neglects the very important criteria including "precision" or "F-score". As we know, an ANN search can just simple return the all data points in the dataset as search result that can guarantee the recall in 100% coverage without any computations that need costly query time. After confirming the experiments and their details in supplementary materials, any evaluations in terms of precision or F-score are not conducted. Therefore, the completeness of experimental evaluations is low and insufficient to prove the real effectiveness of the proposed framework.

3) In the experiments, we can see that the dimensionality of all data sets is extremely high ($>100$), however, the authors did not discuss the impact of such high-dimensional side-effects that should dramatically downgrade the recall and query processing efficiency. Such a side-effect is the well-known "curse of dimensionality". Any additional discussions should be considered for ANN search when using high-dimensional data sets for experiments.

4) It should be good to evaluate the pre-processing time of the proposed framework by comparing to those existing lookup-based methods because they also need  heavy computational time to build the indexes before running an ANN search.
questions: 1) Why this paper does not consider the evaluation criteria of "precision" or "F-score" that are very common to evaluate the search quality of ANN?

2) Why this paper does not discuss the high-dimensional side-effects regarding the well-know "curse of dimensionality"?

3) Why the re-formulation of ANN search is needed to do in such a multilabel classification to find the candidate set of an ANN search? 
limitations: The limitations of the proposed framework have been fairly addressed in the paper.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper revisits the space-partitioning-based methods of approximate nearest neighbor search and proposes a new multilabel classification framework. Space-partitioning-based ANN search algorithms outputs a candidate list of $k$-nearest neighbors based on an index structure. This paper views the candidate set selection problem as a multilabel classification problem, by regarding the retrieval of the indices of the candidates as marking the query point with $k$ labels. Given a multilabel classifier, its use as an ANN algorithm is straightforward. The paper also establishes a sufficient condition for a partitioning-classifier-based ANN search algorithm, and shows that the chronological kd tree is asymptotically consistent when it is used for ANN search. Empirical evidences support that the proposed framework is indeed powerful.
strengths_and_weaknesses: **Strengths**
- The idea of viewing the candidate set selection problem as a multilabel classification problem is natural and neat. In particular, it suggests that the existing space-partitioning based methods are based on a possibly suboptimal classifier (which they call the naive classifier) and provides a simple wrapper to improve the previous unsupervised space-partitioning methods by constructing a better conditional probability estimate. Further, since this framework allows to plug-in any classifier, it opens up a question whether and when a learned classifier can outperform the unsupervised methods.
- The presentation is very clear (except one suggestion below).
- The experiments are well elucidating the ideas of the paper.

**Weaknesses**
- One minor complain is that the current flow is a bit misleading. I would expect to see Section 3 right after Sections 2.1 and 2.2, as the multilabel classification framework is independent of the form of classifiers. After Section 3, the authors can explain partitioning classifiers, the notion of natural classifiers, and the comparison with the existing lookup search based methods (essentially the content in Section 4.) The current flow does not prevent understanding the ideas by much, but I believe that the perspective of naive and natural classifiers and the discussion in Section 4 deserve better presentation, considering that it is the main empirical improvement shown in Section 6 (Figure 1).
questions: - While it is explained, in line 298, that "*as expected based on the theory*, the performance of partition-based index structures can indeed be improved by interpreting them as partitioning classifiers," I do not see which "theory" a priori predicts that the natural classifier would outperform the naive classifier in the proposed framework. Is it based on the observation that the Bayes classifier in the form of a plug-in classifier which is the form of the natural classifier, while the naive classifier is of a different form? I would appreciate if the authors can elaborate this.

limitations: Limitations are well discussed.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: This paper focuses on the approximate nearest neighbor (ANN) search problem. The main contribution is that authors formulate candidate set selection in ANN search directly as a multilabel classification problem where the labels correspond to the nearest neighbors of the query point, and interpret the partitions as partitioning classifiers for solving this task. 
strengths_and_weaknesses: Strengths:
1. The motivation is novel.
2. A concrete implementation is provided.
3. Some experimental results are provided.

Weaknesses:
1. The motivation might be unreasonable. The size of label space equals the number of training examples which is usually very large in approximate nearest neighbor (ANN) search problem. For example, the benchmark data set GIST has one million training examples, it is very difficult to learn a multi-label classifier with so many labels.
2. This paper is not well organized. Key contributions are introduced very briefly while related works are demonstrated too detailedly. For example, the proposed method is only introduced with less than half of one page (Section 3). For another example, the experimental setting is not introduced clearly, at least the number of nearest neighbors is not given in experiments.

questions: I have listed some problems above. It is suggested to focus on the key contributions when writing the manuscript. Moreover, the resulted problem has large label space, maybe the emerging learning task extreme multi-label learning/classification will be useful.
limitations: Authors have listed two limitations in Section 7. However, I think that the large label space is the most limitation of the proposed framework. Moreover, the pre-processing time of computing the true nearest neighbors for training examples will be very long when the size of training set is large. Unfortunately, when we need approximate nearest neighbor search, the size of training set is usually very large. Otherwise, we can obtain the accurate nearest neighbors easily.
review_title: null

Meta-review: metareview: In this paper, the authors propose a novel multi-label classification framework in the spatial partitioning-based method of approximate nearest neighbor search. The space partitioning based ANN search algorithm outputs the nearest neighbor candidate list based on the index structure. In this paper,  the problem of candidate set selection to be a multi-label classification problem is considered, and searching an index of candidates as labeling query points. The paper is theoretically solid and gives accurate answers to the questions of the reviewers during the discussion period. In particular, the main point of this paper is that existing search-based algorithms can be viewed as specific sub-optimal methods in multi-label classification frameworks. The idea is original and the evaluation is appropriate.
confidence: Less certain
Decision: Accept