A Multilabel Classification Framework for Approximate Nearest Neighbor Search
Authors: Ville Oskari Hyvönen
Elias Jääsaari
Teemu Roos
Venue: NeurIPS 2022 Accept (2022)
Keywords: approximate nearest neighbor search
multilabel classification
statistical learning theory

Abstract: Both supervised and unsupervised machine learning algorithms have been used to learn partition-based index structures for approximate nearest neighbor (ANN) search. Existing supervised algorithms formulate the learning task as finding a partition in which the nearest neighbors of a training set point belong to the same partition element as the point itself, so that the nearest neighbor candidates can be retrieved by naive lookup or backtracking search. We 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. Empirical results suggest that the natural classifier based on this interpretation leads to strictly improved performance when combined with any unsupervised or supervised partitioning strategy. We also prove a sufficient condition for consistency of a partitioning classifier for ANN search, and illustrate the result by verifying this condition for chronological $k$-d trees.


A Multilabel Classification Framework for Approximate Nearest Neighbor Search
Ville Hyvönen
Elias Jääsaari Machine Learning Department Carnegie Mellon University ej jjaassacs... cmu cmu.edu edu
Department of Computer Science University of Helsinki
Helsinki Institute for Information Technology (HIIT)
ville.o hywonen@helsinki..f.
Teemu Roos
Department of Computer Science
University of Helsinki
Helsinki Institute for Information Technology (HIIT)
deemu.roostee helsinki.
Abstract
Both supervised and unsupervised machine learning algorithms have been used to learn partition-based index structures for approximate nearest neighbor (ANN) search. Existing supervised algorithms formulate the learning task as finding a partition in which the nearest neighbors of training point belong the same partition element as the point itself, so that the nearest neighbor candidates can be retrieved by naive lookup backtracking search. We formulate candidate set selection ANN search directly as multilabel classification problem where the labels correspond the nearest neighbors of the query point, and interpret the partitions as partitioning classifiers for solving this task. Empirical results suggest that the natural classifier based on this interpretation leads to strictly improved performance when combined with any unsupervised or supervised partitioning strategy. We also prove sufficient condition for consistency of partitioning classifier for ANN search, and illustrate the result by verifying this condition for chronological k-d trees.
1 Introduction
Approximate nearest neighbor (ANN) search is fundamental algorithmic problem. There is large body of literature on ANN search spanning several research communities, including the machine learning community. Specifically, space-partitioning data structures such as space-partitioning trees (Friedman et al. [976 Muja and Lowe 2014 Dasgupta and Sinhal 2015) and data-dependent
hash tables (Indyk and Motwani 1998 Datar et al. 2004 Weiss et al. methods commonly used for ANN search.
2009 are machine learning
In this article, we propose an intuitive theoretical framework for partition-based ANN search. In particular, we formulate the candidate set selection directly as multilabel classification problem where the labels represent the indices of the nearest neighbors of the query point. This formulation suggests that the performance of space-pariitioning data structures can be improved by using them in a theoretically justified fashion as partitioning classifiers (Devroye et al. 1996, Chapter 21) instead of searching them under the earlier lookup-based paradigm. Our classification framework also enables applying general purpose classifiers such as a multilabel random forest directly as an index structure for ANN search.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

We start by reviewing the relevant background on ANN search and multilabel classification (Sec. and formulating candidate set selection in ANN search as a multilabel classification task (Sec. B
In Sec. 4 we define the natural (partitioning) classifier for the general multilabel classification task.
In Sec. 6 we show that interpreting the earlier lookup-based candidate set selection methods in the
multilabel classification framework of Sec. 3 suggests that they define suboptimal classifier. Our
multilabel formulation also enables us to consider asymptoties in the standard statistical learning framework: we establish sufficient condition for consistency of partitioning classifier for ANN search (Sec. As a concrete example (Sec. 7.2), we verify this condition for the chronological k-d tree (Bentley 1975) that was the first data structure proposed for accelerating nearest neighbor search. To empirically validate the proposed framework, we show that using a natural classifier that is aligned with the ANN task in conjunction with ppacce-prtitioninn data structures proposed in the literature leads to strictly improved empirical performance compared to the earlier lookup-based candidate set selection methods (Sec. g
2 Background and notation
2.1 Approximate nearest neighbor search
Let the corpus points {cy] and the query point be vectors in Rd. We call the lt corpus points that are closes to the query point x its k nearest neighbors and denote the set of their indices by
(N) == k k-argmin
| - -cylls
(1)
j=l....,m
where the notation k a-argmmin f means the of values for which the function f has the smallest values, and || is the Euclidean distance. Other metrics, or-more generally-dissimiaaryy measures can also be used define the nearest neighbors.
The trivial solution to the problem of finding the nearest neighbors (x) of the query point x is to compute the distances to all the corpus points and sort these distances. However, when the dimensionality of the data is high and the corpus size is large, this brute force solution is often too slow if the application requires fast response times. The first data structure proposed for speeding up nearest neighbor search was the k-d tree (Bentley) 1975). However, for high-dimensional data, a k-d tree not faster than the brute force approach for exact nearest neighbor search because of the well-known curse of dimensionality that affects the non-parametric statistical
partitioning methods for nearest neighbor search-in general (Lee and Wong 1977). Although the query speed of index structures for exact nearest neighbor search degrades when the dimensionality of the data increases so that they are not an improvement on the brute force approach, this problem can be mitigated by allowing an approximate solution. This is why in modern high-dimensiona applications approximate nearest neighbor (ANN) search is typically used when fast solution to the nearest neighbor problem is required.
Algorithms for ANN search can be divided into three categories: graphs (Malkov al. 2014; Malkov and Yashunin 2018 Iwasaki and Miyazaki| 2018 [Baranchuk et al. 2019). quantization (Jegou et al.) 2019] Sablayrolles et al. 2019). and space- pariceeprtitioning methods. In this article, we consider space-pattitioning methods that can be further divided into tree-based (Muja and
al.
Lowe 2014, Dasgupta and Sinha 2015 Jaäsaari et al. 2019) and hashing- (Datar al.[2004
Aumüller et al..2019 Gong et al. 2020) algorithms that use trees and hash tables, respectively, as
index structures.
Space-partitioning algorithms for ANN search use an index structure to select a candidate set ((x) C (1 of potential nearest neighbors. They then calculate the exact distances between the points in the candidate set and the query point, and return the nearest points as the approximate nearest neighbors. These algorithms will correctly retrieve nearest neighbor j E NN) if and only if it belongs to the candidate set. Thus, the recall of a space- canc-ppatitioning algorithm can be written as Rec(S (x)) := NN (NN (z) (())), where we denote the number of elements of the set A by [A]. The performance of an approximate nearest neighbor algorithm is typically measured by its average recall- recall-query time tradeoff (see e.g. Aumüller al. (0199) or Li al. (2019) -ie., the average query time required to reach certain average recall level on a set of test queries.
In what follows, we assume that the ties are broken uniformly at random so that the query point always has exactly l nearest neighbors.
2

---

2.2 Multilabel classification
Consider a standard multi-label classification problem with m labels. Let X I2 be random variable and let L(X) S (l....,m) m be the corresponding label set. Equivalently, the output variable can be presented in binary encoding by defining Y {0, 13"h as an m-bit random vector, where if j E j(X)), otherwise.
1 y, 0
A multilabel classifier is an m-component function 9 (91,.... Im) R + {0.1) that attaches label set to the value of the input variable X. Denote the training that is assumed to be an ii.d. sample from the distribution of the pair Y) by D, = {(x,, Y:) When the classifier Rdd x (TR. x {0, 1)m""" - {0, 10 is learned from the training set of size n, we denote by (x))(x) (z) == gxx, D.). When the training set D,, is considered a random variable, the classifier g g(") also becomes random function.
The performance of the classifier is measured by a loss function L {0. 10. x [0, + R, and the objective is to minimize the risk R(g) == (X)). Y)]. This risk is lower-bounded by the Bayes risk R inf, Rgg), the minimizer of which called the Bayes classifier.
The Bayes classifier for many common multilabel loss functions-such as Hamming loss, ranking loss, precision, recall, and f--meauues--is obtained by thresholding the conditional label probabilities (z(2)= := P(Y, = x = x} (Dembezynski et al. 2010;; Koyejo et al. 2015). This justifies the standard plug-in approach of first estimating the conditional label probabilities by in (x).... fmm......m.. (x). and then defining the plug-in inn classifier as
9, (m) (x)
{1, (o 0.
11,
if (E)
(3)
otherwise,
where E [0, 1]: equivalently, the plug-in in classifier can be written as the estimate of the label set L(x) as [(x) {j E {I....,m} mm (x)) > r).
The multilabel classification problem often solved by reducing it to a series of binary or multiclass classification problems, and estimating the conditional label probabilities 7/ (2:) under this model. (see, e.g., Menon et al. (2019) for a discussion of different reduction methods). In what follows, we will employ the pick-all-labels (PAL) reduction (Reddi al.] 2019) where we separate each label I E L(x;) of the training set point x; into multiclass (but single-label) training instance (æi, l), and fit the classifier to this modified training set by minimizing multielass loss function.
3 Candidate set selection as multilabel classification problem
Equipped with the above definitions, we are now in position to formalize candidate set selection in ANN search described in Sec. 2.1 as an instance of the multilabel classification problem described in Sec. 2.2
In the classical formulation of ANN search, the input-output pair is defined as (z. (x).. It is straightforward to observe that this is essentially an instance of the multilabel classification problem where NN₃( (x).e,,,.. the set of indices of the k nearest neighbors of the query point-is the label set [xx. Assuming that the values of x are i.i.d. draws from the distribution of the random variable X (the query distribution), the objective is predict the value of the random variable Y (defined by (2) with N (X) as a label set) given the value of the random variable X. A distinctive property of this classification problem, which follows from the definition of the ANN task, is that the size of the label set [xx) 1 Uj = k is constant for all queries.
-.e..,
Since the labels [1....,m)] m} correspond to the indices of the corpus points, the classification decision (3) where the probability estimates are thresholded corresponds candidate set selection, and the estimated label set ((x) corresponds to the candidate set S(xr).
MMore generally, instead the conditional label probability estimates in (z)..... .... (xr) any score function values si (x).... Sm.. (x: for the labels can be learned and thresholded to make the classification decision. While we will present all the results only for the version of the plug-in in classifier that uses the probability estimates, they readily generalize to the version of the plug-in in classifier that uses the score function values.
3

---

If no additional training data is available, the corpus itself can be used as a training set. More precisely, in this case we interpret {ez]ā=1 as sample from the query distribution, compute the is nearest neighbors of the corpus points, and then use {(c V2) } as a training set. Note that in this case Ujj for each j = =I,... m since each corpus point is the nearest neighbor of itself.
4 Partitioning classifiers
In this section, we first give a general definition of the partitioning classifier. We then define the natural classifier-that is special case of the partitioning classifier-for the single partition and for the ensemble of partitions for the general multilabel classification problem described in Sec. 2.2
Partitioning classifier is general term for classifier that is based on learning a partition of the instance space and whose classification decision is based on the labels of the training set points that belong to the same partition element as the query point. Partitioning classifiers can be divided into two categories depending on whether the partition is flat or recursive. There is a vast literature on recursive partitioning classifiers (i.e., classification trees), and gradient boosted trees (Friedman et al. Friedman 2001) are one of the most widely used and efficient classifiers (Chen and Guestrin
2000
2016
Flat partitions more typically used for density estimation (Kontkanen and Myllymäki
2007
Lupez-Rubio 2013 Cui et al. (021), but they have also been used for classification (Lugosi
and Nobel 1996 McAllester and Ortiz 2003).
Denote by P {R1, R2....,,yy R the partition of Rd, i.c., a collection of disjoint sets for which U R = Rd. Denote the structure function that maps the query point to the index of the partition element it belongs into by q Rd + f1,2, L}. When the partition is learned from the training data, we denote it by p(n) = π (D.), where π (Dx) ) is a partitioning rule that associates the training set with a partition of !R
Natural classifier for single partition. Partitioning classifiers use the training set twice: first, to learn the partition p(x) x (D,), and second, to classify the query point using the training set points that belong to the same partition element Ry(z) as the query point x. In the multiclass
classification, the conditional label probabilities can be estimated in natural fashion by the observed label proportions
1
f (z)
Σ
Vij-
(4)
Ng(x) (:2,E
where Na(=) := : 24 Ry(e) denotes the number of training set points in the same partition element as the query point. This standard practice can be motivated by noting that these observed label proportions are the maximum likelihood estimates of the piecewise constant multinomial model where the conditional label probabilities are constants at each of the partition elements.
In the multilabel case, the estimation of the conditional label probabilities by (4) can be motivated via the PAL reduction under which the observed label proportions in Ry(=)) are proportional to the maximum likelihood estimates of the piccewise constant multinomial model. To classify the query point, the conditional probability estimates (4) are plugged into (3). i.e., the query point is assigned into all the classes whose probability estimate is greater than equal to the value of the threshold parameter r. We call this partitioning classifier the natural classifier.
Natural classifier for ensemble of partitions. When collection of partitions (P(") T
Tell where p(a) : {.e(")....,(!) is used as a classifier- as in random forests (Ho 1998 Breiman 2001 the contributions of the partitions aggregated. In this article, we consider the most straightforward aggregation method where the conditional probability estimates are obtained as averages of the conditional probability estimates of the individual partitions:
1x(2)) T
Σ
(1) 1
(z).
(5)
The estimate of the single partition 1/ (x)) is defined as in 4 for the corresponding partition P!"") and the corresponding structure function qt.

---

5
Related work
The most directly relevant earlier literature consists of studies that learn space-pauee ppace-partitioning index structures for ANN search using supervised information. The idea of optimising the index structure for the particular query distribution was first presented by [Maneewnggvaaana and Mount (200). and later extended by Cayton and Dasgupta (2008) who formulate ANN search as a supervised learning problem and propose a tree-based and hashing- basee algorithm for solving it. More recently, many supervised learning to hush-methods, such as minimal loss hashing (Norouzi and Fleet, (2011). LDA hashing (Strecha et al. 201T), and kernel-based supervised hashing (Liu et al. (011), have also been proposed for ANN search (see, e.g., Wang et al. (2015) or Wang et al. (2017) for survey).
However, the earlier supervised methods pose the supervised learning problem in an indirect fashion. This is because they, like the earlier unsupervised methods, select the candidate set using a method which we call lookup search they select the corpus point into the candidate set if and only if belongs to the same partition element as the query point. Consequently, their objective is to learn a partition in which the h nearest neighbors of a query point belong to the same partition element with it. In contrast, our objective is to directly learn a partitioning classifier that predicts its nearest neighbors correctly. We will elucidate the difference in the next section.
Candidate set selection for ANN search
In view of the multilabel formulation of Sec. the natural classifier defined in Sec. used to select a candidate set for ANN search. However, in this section we interpret also the earlier lookup-based candidate set selection methods (lookup search and voting search) in our multilabel classification framework, and show that they define a classifier a different form. We show that this classifier that we call the naive classifier-is is in fact the natural classifier for the different multilabel classification problem where the labels do not represent the corpus points that are the nearest neighbors of the query point but the corpus points that belong to the same partition element as the query point. This suggests that the natural classifier would be a more suitable candidate set selection method for ANN search than the naive classifier. The empirical results of Sec. 8 indicate that this is indeed the case.
+ can directly be
Candidate set selection for single partition. First, assume that we utilize the single fixed partition P = (RR,,..,,,,,, and the training set {(x,,)) w)) to approximate the nearest neighbors of the query point x. The natural classifier defined in Sec. selects the candidate set as
i(x)= = (j E (1...., m) (1)(x)) > +)
where + E [o, 1). and the conditional label probability estimates f1)()) Notss E. obtained as the observed label proportions among the training set points that belong to the same partition element with the query point. In contrast, lookup search selects the candidate set as
E Ryco) Pij are
f(x) = (i E (1....,m) mm c E Rg(a)):
i.e., it selects the corpus point into the candidate set if and only if it belongs to the same partition
element with the query point. When interpreted in the classification framework of Sec. 3 7 defines
the classifier L(x) = i E {l...., m) (x) > T}, where T E [0, 1) and 7 (z) = 1 R (c;): we
call this a naive classifier.
We immediately observe that the naive classifier not a natural classifier for the multilabel classi-
fication problem in which the labels are defined as Vij = 1 (nn,(an)(C) (cy) as in Sec. 3 Instead, it is natural classifier for the different multilabel classification problem which the labels are defined
'Otten, lookup search is combined with priority queue guided backtracking search in which the query point is routed into more than one element in a partition, and all the corpus points that belong to these partition elements are then selected into the candidate set. This technique is called priority search (Arya and Mount 1993] Silpa-Anan and Hartley 2008) or mudti-probe LSH (Ly al. 2007). depending whether the index structure is based or hashing- based, respectively. For clarity, we do not consider backtracking that is mainly a memory-savine technique- in the analysis below: it can be easily incorporated both into lookup search and our method by allowing the structure function to return a set of indices instead of a single index, and considering Uleg(a) Rt instead of the single partition element Hy(s).
5

---

as B/y = 1 R,, (e,)),) In other words, the naive classifier is geared towards the learning problem in which instead of the k nearest neighbors the query point-thi the labels represent the corpus points that belong to the same partition element as the query point. The candidate set selection method (7) also explains why the objective of the earlier supervised methods for learning the partition differs from ours: in these methods, the objective is to maximise the number of nearest neighbors of the query point that belong to the same partition element with in order to maximise the recall (while minimising the number of non-neighbors in that element in order to maximise precision).
Candidate set selection for an ensemble of partitions. Assume that the fixed set of partitions {P:) is used approximate the k nearest neighbors of query point æ. The natural classifier defined in Sec. selects the candidate set
((x) = LeE (L....,,m] (1) >T)
as in (6). but now (x) - - (0) (x),, where the contributions of the individual partitions
f (x) are defined as above. In contrast, the earlier (both supervised and unsupervised) methods select the corpus point into the candidate set and only if it belongs the same partition element as the query point in at least one of the T partitions. Hence, the candidate set selected by lookup search
((x)
- ij jE (1, m
(l.....mblll e U @ Li (L..... m) (2) r}.
glo(s) }
(9)
t=1
where (x) = + 11) (z), (z). E [0, #), and the contributions of the partitions 1i (x) are
(()
defined as above.
Unlike in the case of single partition where the value of the threshold parameter T E [0, 1) does not affect the classification decision of the naive classifier, since (z) E {0, (0, now affects the classification decision, since Vi (x) E (0, :.... 1]. Hence, a tuning parameter can be added lookup search by allowing be chosen freely as proposed by Hyvönen et al. (2016) who call the resulting method voting search.
7 Consistency of partitioning classifiers for ANN search
The ideal index structure for ANN search always returns a candidate set that contains all the l nearest neighbors of the query point and no other corpus points. Under the multilabel formulation, this corresponds to a classifier for which the expected multilabel 0-1 loss (g(g ())))))))))))))) = P(g(()) * Y} zero. To this end, we prove a sufficient condition for the consistency of a partitioning classifier for ANN search under ()- loss. Consistency under (I- loss also directly implies consistency for the other common multilahel loss functions, such as Hamming loss, precision, recall, and F-measures. As concrete example, we prove the consistency of the chronological k-d tree (Bentley 1975) by checking that this condition holds for
7.1 Sufficient condition for consistency
The classical theorem for proving consistency of partitioning classifiers for binary classification is:
Theorem 1. DDerroye al. (196)), Theorem 6.1, p. 94-95) Assume that only the features X1,..., Xn, are used to learn the partition pp(a) = n (x.,..., Xa). The natural classifie ((m) defined by p(n) is consistent (under 0-1 loss) for binary classification, if
(i) N₂(X) - so in probability, and (ii) diam (Ry(x)) 0 in probability,
when n CC.
'The natural classifier for binary classification is defined as the classifier that classifies the query point into the majority class of the training points that belong the partition element with

---

The number of the training set points in the partition element the query point x belongs to is denoted by (x) := Ki X, Rg(z)) H. and the diameter of set defined as the maximum distance between any two points of this set and denoted by diam (A) == sup ||a bl|-
a A
While this result is for binary classification, it can be readily extended to the multilabel case. However, as a multilabel classification problem, ANN search has two distinguishing properties: (i) the Bayes error R is zero; (ii) decision boundaries between the labels consist of subsets of hyperplanes. It turns out that in this case, the second condition of Theorem iss sufficient for the consistency of a partitioning classifier:
Theorem 2. Let g( be natural classifier defined by the partition p(n) (RI,..., R1) and the threshold parameter T E [0, 1) for ANN search. Assume that the distribution of X, denoted by n. is continuous. If diam (Rgx)) + in probability-thtt is, for every e >> O.
P(diam (R₂())) +
+
when n + 0C, then the classifier g g(a) is consistent (for 0-1 loss) i.e. ED., ((g + 0.
Proof. If for all the pairs of corpus points (cz, 0g),, ) J' + j. all the points of the partition element R
are closer to Cj than Cy' (or vice versa) that is, if there is no such pair (cg.Cy) for which there exists a. b.be E R such that ||a cyll < lla Cyr and |lb - cyll each x E R and j = 1. ...... m. consequently, each x E R₁ is classified correctly for any T E [0, 1).
.|b - Cyy l-then also (x) nn (x) for
Now, since for each j ,,..., m.
P(u 1l (X) (X) (X)}
$ P (3j' #j: E R)( s.t. 1|a- --al- < ||a ll. 1b6 --yl > 1 cl
- Σ P( E Ra(x) s.t. I|a - -yll < ||a - llll, ||b - الرl > ||b - 1r,
to prove consistency of ((n) is sufficient to show that for all j.j E { (4....,m).j
m}.
P[ b Rx( s.t. lla cyll ||a 1l. bbb e |bb cg [1} +
in probability when n + 0o.
Choose any j.j', j # j', and denote the hyperplane that is halfway in between the corpus points ej and Cy by H ;= {i E Rd || - -c,ll || cy I|] For any t = 1,2.... let He denote the set surrounding H by a margin of width 1/t. Since Hi H2 3 H3 ...., and H ne n H4, it follows from the upper continuity of the probability measure that lim ((H,) = ((H). Because t-xx0
the Lebesgue measure of the hyperplane H in Rd is zero and is absolutely continuous w.r.t. the Lebesgue measure by the assumption, then also lim p(H,) = p(H) =0. (-30
Now, for any ( = 1,.,..., the Ra((r) is greater than 1/t. Hence,
... if Rg(x) crosses the hyperplane H, then either x E H. or the diameter of
P(3a, b E Ry(x) s.t. ||a -cyl < lla- - 1. 16--e > 11--1-0 cg. 11
< P(X E He or diam(Ba(x)) > 1/t}
$ ((HH) + Pfdiam
> 1/t).
We can get p(H,) as small as desired by choosing a large enough t; and since by assumption the second term is arbitrarily small when n is large enough, the result follows.
7.2 Consistency of chronological k-d tree
Next, we illustrate the utility of Theorem by applying it to prove the consistency the chronological k-d tree (Bentley] 1975) that rotates the split directions and uses the same split direction for all the nodes at one level of a tree. At the first level the training data split at the median of the first coordinates of the data points. At the second level both nodes are split at the median of the second coordinates of the node points. At the (d + 1 1h level, the nodes are split again at the median of the first coordinates, and so (see Appendix C.
7

---

More precisely, let X, XI,,,..... Xn E Rd be ii.d. random variables. A chronological k-d tree can be formalized as a partitioning rule that returns the partition p TX Xn). When the tree height f. this partition has 2 elements (also called leafs). The leafs are hyperrectangles in R. Some of the edges of these hyperrectangles may have infinite length. To handle these leafs, we introduce the notation where, for any M > O, the hypercube [-M, M divides the partition elements RI,..., Ryr into three disjoint sets:
A (1e 11, ....,......................... 2 Rí C M,MM,]]}
: = (1E (I....,,2 2), Rı C Rd \|
(10)
B (1. 22) (AUC).
Here A the set of indexes of the partition elements that are completely inside the hypercube [-M, Mjd. { B is the set of indexes of the partition elements that cross its boundary, and C' is the set of indexes of the partition elements that are completely outside of it.
First, we prove two auxiliary results that bound the number of nodes crossing the boundary of the box [-M, M and the combined length of the edges (in any fixed coordinate direction) of the nodes that reside completely inside [-M, Mj4 respectively. Note that these bounds are of purely combinatorial nature and thus do not depend on the training set. The proofs of the following results are presented in Appendix A.
Lemma 1. For any training set D it holds for the number of nodes of a chronological k-d tree- denoted by NB = crossing the border of the hypercube M-,, M]] that
NB S 4d 2
Lemma 2. Let E (1.....d) be any coordinate direction. Denote the length of the node Ri in the jth coordinate direction by Vt. Then for any training set D.,.
Σ TEA
V1 S 4M 2
We are now in position to establish the consistency of the chronological k-d tree for approximate nearest neighbor search. view of Theorem i suffices to prove that the leaf diameter converges to zero in probability:
Theorem 3. for the height of a chronological k-d free holds that l -> oc when n. - co, then the leaf diameter diam R))x)) converges zero in probability.
8 Experiments
We present empirical results validating the utility of our framework. In particular, we compare the natural classifier the earlier candidate set selection methods discussed Sec. 6 differrnnt types of unsupervised trees that have been widely used for ANN search. Specifically, we use ensembles of randomized k-dd trees (Friedman et 1976 Silpa-Anan and Hartley, 2008). random projection
(RP) trees (Dasgupta and Freund, 2008 Hyvönen et al.) (016)) and principal component (PCA) trees (Sproull] 1991] [991]paäsaari Jääsaari al. 2019 (see Appendix C for detailed descriptions of these data structures). Another consequence of the multilabel formulation of Sec. 3 is that it enables using any established multilabel classifier for ANN search. To demonstrate this concretely, we train random forest consisting of standard multilabel classification trees (trained under the PAI reduction (Reddi et al.) 2019) by using multinomial log-likeli ligeeiili as a split criterion) and use it as an index structure for ANN search; it turns out that the fully supervised classification trees have an improved performance compared to the earlier unsupervised trees on some-but, curiously, not on data sets.
We follow standard ANN search performance evaluation setting (Aumüller et al. 2019 Li et al.. 2019) by using the corpus as the training set, searching for k = 10 nearest neighbors in Euclidean distance, and measuring performance by evaluating average recall and query time over the test set of 1000 points. We use four benchmark data sets: Fashion (m = 60000, d 784), GIST (m 1000000, 960), Trevi (m 101120, 4096), and STL-10 (m = 100000, 9216).
All the algorithms implemented in C++ and run using single thread. We tune the hyperparameters

---

by grid search and plot the Pareto frontiers of the optimal hyperparameters. Further details of the experimental setup are found in Appendix B. The code used to produce the experimental results is attached as supplementary material and can also be found at https: / / thub. wtt.ccoo///ooiie waioo//viioooo///oo -o
Comparison of candidate set selection methods. The candidate set selection method proposed in this article is the natural classifier (8) described Sec. [ for completeness, we also include the special case obtained by fixing
in the comparison. The earlier methods are lookup search (naive classifier (9) with т = 0) and voting (Hyvönen et al. 2016 Jääsaari et al.) 2019) (naive classifier free tuning parameter). 'The results for the Trevi data set presented in Fig. and indicate, as the discussion of Sec. Suggesss,, that the natural classifier performs better than the earlier lookup-based methods for all types of trees (this finding holds consistently over all the data in our experiments; see Fig. 2 in Appendix).
(9) with
Natural dlassifier
Natural dassifier,
Naive classifier (voting)
Naive classifier, (lookup)
Trevi, RP
Trevi, KD
Trevi, PCA
query time (9)
10'
10"
10"
10
10"
10
0.5
0.6
0.7
0.8
0.9
0.5
0.6
0.7
0.8 recall
0.9
1.0
0.5
0.6
0.7
0.8
0.9
1.0
Figure 1: Recall vs. query time (log scale) of ensembles RP, k-d, and PCA trees. The solid blue line is the natural classifier proposed in this paper; the dash-dotted red line is the natural classifier with 7 that included for completeness; the dashed green line is voting; and the double-dash-de dotted violet line is lookup search. The natural classifier is the fastest and the lookup search is the slowest of the methods for each tree type.
Comparison of tree types. We compare the aforementioned ensembles of unsupervised (RP, KD, and PCA) trees and the random forest consisting of supervised classification trees (RF); for all four tree types the candidate set is selected by (8). The results are shown in Table [ Since the random forest (RF) leverages supervised information to learn the trees, we would expect that it is the fastest tree-based method. Indeed, this is the case on Fashion and GIST. However, on STL-10 and Trevi, the unsupervised PCA tree is the fastest method. We hypothesize that this is because of the high dimensionality of STL-10 and Trevi: standard supervised classification trees employed by random unsupervised
forest restricted to axis- akis-aligned splits, whereas PCA trees although they split criterion- can find more informative oblique split directions. An interesting topic for future work would be apply supervised classification trees that utilize oblique split directions.
Conclusion
We establish a general theoretical framework for ANN search by formulating candidate selection as a multilabel learning task. Empirical results validate our framework: a natural classifier derived the earlier lookup-based candidate
directly from the problem formulation is strict improvement set selection methods. In addition, we provide a sufficient condition that guarantees consistency of a partitioning classifier for ANN search. We verify this condition for chronological k-dd trees, indicating that-given enough training thea-they retrieve a candidate set containing all the nearest neighbors of the query point and other corpus points.
Supervised ANN search methods typically have longer pre- processing times com- pared unsupervised methods. This is because (1) they require computing the true nearest neighbors {yx) of the training set points {1r, )/1 and (2) supervised index structures are often slower to build compared their unsupervised counterparts (c.f. Appendix D.1). 1). fast index construction required, the second problem can be mitigated by learning trees in an unsupervised fashion, but using
Limitations.

---

Table I: Query times (seconds / 1000 queries) at different recall levels for the different tree types. The fastest method in each case is typeset in boldface.
data
(%)
PCA
KD
RP
RF
80
0.075
0.076
0.099
0.063
Fashion
90
0.111
0.126
0.172
0.095
95
0.163
0.171
0.261
0.146
80
1.330
0,958
1.009
0.705
GIST
90
2.942
2.286
2.226
1.530
95
5.641
4.451
4.598
3.253
80
0.382
0.872
1,211
0.756
STL-10
90
0.756
2.126
3,248
1.774
95
1.315
4.376
7.330
3.654
80
0.330
0.543
0.591
0.582
Trevi
90
0.684
1,464
1,468
1.234
95
1.212
3.244
3.289
2.350
them as partitioning classifiers as described in Sec. since the experiments of Sec. g suggest that the candidate selection method has pronounced effect on the performance than the tree type.
Future research directions. While we demonstrate our approach using random forest classifier, expect that the most important consequence of our work is that it enables using any type of classifier as an index structure for ANN search. In particular, gradient boosted trees (Friedman) (001)) promising since they often including tree-hased models (Agrawal et al. 2013 Prabhu and Varma 2014 Jain et al.) 2016), sparse linear models (Babbar and Schölkopt 2017 2019 Yen al. 2017). and embedding- based neural networks (Guo et al.) 2019). are also promising model candidates for ANN search since they are specifically tailored for multilabel classification problems with extremely large label spaces.
accurate than random forests. Extreme classification models,
Our formulation enables analyzing ANN search the statistical learning framework, thus opening multiple theoretical research questions: (1) Can we establish sufficient condition for strong consis- tency? (2) Can we prove consistency of more adaptive partitioning classifiers, such as PCA trees or classification trees? (3) Can establish faster than logarithmic convergence rates? The last question especially interesting, since prediction times of trees are logarithmic: a positive answer would theoretically justify decreasing query times by increasing the training set size.
Acknowledgements
Funding in direct support of this work: Academy Finland grants #345635 (DAISY). #311277 (TensorML), and #313857 (WiFiUS). The authors wish to thank the Finnish Computing Competence Infrastructure (FCCI) for supporting this project with computational and data storage resources.
References
Rahul Agrawal, Archit Gupta, Yashoteja Prabhu, and Manik Varma. Multi-label learning with millions of labels: Recommending advertiser bid phrases for web pages. In Proceedings of the 22nd International Conference on World Wide Web, pages 13-24. ACM, 2013.
Sunil Arya and David M Mount. Algorithms for fast vector quantization. In Proceedings of DCC93:
Data Compression Conference, pages 381-390. IEEE, 1993.
Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. ANN-benchmarks: A benchmarking
tool for approximate nearest neighbor algorithms. Information Systems, 87, 2019.
Martin Aumüller, Tobias Christiani, Rasmus Pagh, and Michael Vesterli. PUFFINN: parameterless and universally fast finding of nearest neighbors. In 27th Annual European Symposium on Algorithms, ESA 2019, pages 10:1-10:16, 2019.
10

---

Rohit Babbar and Bernhard Schölkopf. DiSMEC: Distributed sparse machines for extreme multi classification. In Proceedings of the Tenth ACM International Conference on Web Search and Data Mining, pages 721-729, 2017.
Rohit Babbar and Bernhard Schölkopf. Data scarcity, robustness and extreme multi-labed classification. Machine Learning, 108(8-9): (1:.9)))13299 300:1112-1333 1351, 2019.
Dmitry Baranchuk, Dmitry Persiyanov, Anton Simitsin, and Artem Babenko. Learning to route in similarity graphs. In International Conference Machine Learning, pages 475-484, PMLR,
2019.
Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communica- tions of the ACM, 18(9):509-517, 1975.
Leo Breiman. Random forests. Machine Learning, 45(1):5-32, 2001.
Lawrence Cayton and Sanjoy Dasgupta. A learning framework for nearest neighbor search. In Advances in Neural Information Processing Systems, pages 233-240, 2008.
Tianqi Chen and Carlos Guestrin. XGBoost: A scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 785-794. ACM, 2016.
Jingyi Cui, Hanyuan Hang, Yisen Wang, and Zhouchen Lin. GBHT: Gradient boosting histogram transform for density estimation. In International Conference on Machine Learning, pages 2233- 2243. PMLR, 2021.
Sanjoy Dasgupta and Yoav Freund. Random projection trees and low dimensional manifolds. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pages 537-546, 2008.
Sanjoy Dasgupta and Kaushik Sinha. Randomized partition trees for nearest neighbor search. Algorithmica, 72(1):237-206 2015.
Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab Mirrokni. Locality-sensitivy hashing scheme based on p-stable distributions. In Proceedings of the 20th Annual Symposium on Compu- tational Geometry, pages 253-262,40 2004.
Krzysztof Dembezynski, Weiwei Cheng, and Eyke Hüllermeier. Bayes optimal multilabel classifica- tion via probabilistic classifier chains. In International Conference Machine Learning. PMLR, 2010.
Luc Devroye, László Györfi, and Gábor Lugosi. A Probabilistic Theory of Pattern Recognition. Springer Science Business Media, 1996.
Jerome Friedman, Trevor Hastie, Robert Tibshirani, et al. Additive logistic regression: statistical view of boosting (with discussion and rejoinder by the authors). The Annals of Statistics, 28(2):
337-407, 2000.
Jerome H Friedman. Greedy function approximation: a gradient boosting machine. Annals of
Statistics, pages 1189-1232, 2001.
Jerome H Friedman, Jon Louis Bentley, and Raphael Ari Finkel. An algorithm for finding best matches in logarithmic time. ACM Trans. Math. Software, SXSLAC-PUB-1549 20:20-2266, 1976.
Long Gong, Huayi Wang, Mitsunori Ogihara, and Jun Xu. iDEC: indexable distance estimating codes for approximate nearest neighbor search. Proceedings of the VLDB Endowment, 13(9), 2020.
Michael Greenwald and Sanjeev Khanna. Space-efficient online computation of quantile summaries. ACM SIGMOD Record, 30(2):58-66) 188866,777 2001.
Chuan Guo, Ali Mousavi, Xiang Wu, Daniel N Holtmann-Rice Satyen Kale, Sashank Reddi, and Sanjiv Kumar. Breaking the glass ceiling for embedding classifiers for large output spaces. In Advances in Neural Information Processing Systems, pages 4944-4954, 2019.

---

Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. Accelerating large-scale inference with anisotropic vector quantization. In International Conference on Machine Learning, pages 3887-3896. PMLR, 2020.
Tin Kam Ho. The random subspace method for constructing decision forests. IEEE transactions pattern analysis and machine intelligence, 20(8):832- 844, 1998.
Ville Hyvönen, Teemu Pitkänen, Sotiris Tasoulis, Elias Jääsaari, Risto Tuomainen, Liang Wang, Jukka Corander, and Teemu Roos. Fast nearest neighbor search through sparse random projections and voting. In Proceedings of the 4th IEEE International Conference on Big Data, pages 88 881-888. IEEE, 2016.
Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pages 604 613, 1998.
Masajiro Iwasaki and Daisuke Miyazaki. Optimization of indexing based on k-nearest neighbor graph for proximity search in high-dimensional data. arXiv preprint arXiv:1810.0755: 2018.
Elias Jääsaari, Ville Hyvönen, and Teemu Roos. Efficient autotuning of hyperparameters in approxi- mate nearest neighbor search. In Proceedings of the 23rd Pacific-Asia Conference on Knowledge Discovery and Data Mining, volume 2, pages
Springer, 2019.
Himanshu Jain, Yashoteja Prabhu, and Manik Varma. Extreme multi-label loss functions for recom- mendation, tagging, ranking & other missing label applications. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 935-944, 2016.
Herve Jegou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(():117-128, 2010.
Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with GPUs. IEEE Transactions on Big Data, 2019.
Petri Kontkanen and Petri Myllymäki. MDL histogram density estimation. In Artificial Intelligence and Statistics, pages 219-226. PMLR, 2007.
Oluwasanmi O Koyejo, Nagarajan Natarajan, Pradeep K Ravikumar, and Inderjit S Dhillon. Consis- tent multilabel classification. Advances Neural Information Processing Systems, 28:3321-3329, 2015.
Der-Tsai Lee and Khak-Kuen Wong. Worst-case amalysis for region and partial region scarches in multidimensional binary search trees and balanced quad trees. Acta Informatica, (1):233-29, 1977.
Wen Li, Ying Zhang, Yifang Sun, Wei Wang, Mingjie Li, Wenjie Zhang, and Xuemin Lin. Approxi- mate nearest neighbor search high dimensional data-experiments, analyses, and improvement. IEEE Transactions on Knowledge and Data Engineering, pages 1475-1488, 2019.
Wei Liu, Jun Wang, Sanjiv Kumar, and Shih-Fu Chang, Hashing with graphs. In Proceedings of the 28th International Conference on Machine Learning, pages 1-8, 2011.
Ezequiel López-Rubio. Rubio. histogram transform for probability density function estimation. IEEE Transactions Pattern Analysis and Machine Intelligence, 36(4):644-656, 2013.
Gábor Lugosi and Andrew Nobel. Consistency of data-driven histogram methods for density estimation and classification. The Annals of Statistics, 24(2):687-706, 1996.
Qin Lv. William Josephson, Zhe Wang. Moses Charikar, and Kai Li. Multi-probe LSH: efficient in- dexing for high-dimensional similarity search. In Proceedings of the 33rd International Conference on Very Large Data Bases, pages 950-961, 2007.
Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov. Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems, 45:61-68, 2014.
12

---

Yury A Malkov and Dmitry A Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2018.
Songrit Maneewongvatana and David M Mount. The analysis of a probabilistic approach to nearest neighbor searching. In Workshop Algorithms and Data Structures, pages 276-286. Springer, 2001.
David McAllester and Luis Ortiz. Concentration inequalities for the missing mass and for histogram rule error. Journal of Machine Learning Research, ((Oct):895-911) 2003.
Mark McCartin-Lim, Andrew McGregor, and Rui Wang. Approximate principal direction trees. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pages 1611-1618, 2012.
Aditya Menon, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Multilabel reductions: what is my loss optimising? Advances in Neural Information Processing Systems, 32, 2019.
Marius Muja and David G Lowe. Scalable nearest neighbor algorithms for high dimensional data. IEEE Transactions on Pattern Analysis and Machine Intelligence, 36(1 36(11):2227-2240, 2014.
Mohammad Norouzi and David J Fleet. Minimal loss hashing for compact binary codes. In 28th
International Conference on on Machine Learning, pages 353-360, 2011.
Yashoteja Prabhu and Manik Varma. FastXML; A fast, accurate and stable tree-classifier for extreme multi-label learning. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 263-272, 2014.
Sashank J Reddi, Satyen Kale, Felix Yu, Daniel Holtmann- Rice, Jiecao Chen, and Sanjiv Kumar. Stochastic negative mining for learning with large output spaces. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1940-1949. PMLR, 2019.
Alexandre Sablayrolles, Matthijs Douze, Cordelia Schmid, and Hervé Jégou. Spreading vectors for similarity search. In Proceedings of the 7th International Conference on Learning Representations, 2019.
Chanop Silpa-Anan and Richard Hartley. Optimised kd-trees for fast image descriptor matching. In 2008 IEEE Conference Computer Vision and Pattern Recognition, pages 88. IEEE, 2008.
Robert F Sproull. Refinements to nearest-neighbor searching in k-dimensional trees. Algorithmica, (1-6):579-589, 1991.
Christoph Strecha, Alex Bronstein, Michael Bronstein, and Pascal Fua. LDAHash: Improved match- ing with smaller descriptors. IEEE Transactions Pattern Analysis and Machine Intelligence, 34 (1):66-78, 2011.
Vladimir Naumovich Vapnik and Alexey Yakovlevich Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16 (2):264-280, 1971.
Jingdong Wang, Ting Zhang, Nicu Sebe, Heng Tao Shen, et al. A survey on learning to hash. IEEE Transactions on Pattern Analysis and Machine Intelligence, 40(4):769-790, 2017.
Jun Wang, Wei Liu, Sanjiv Kumar, and Shih-Fu Chang. Learning to hash for indexing big data
survey. Proceedings of the IEEE, 104(1):34-55) 57, 2015.
Yair Weiss, Antonio Torralba, and Rob Fergus. Spectral hashing. In Advances in Neural Information Processing Systems, pages 1753-1760, 2009.
Ian EH Yen, Xiangru Huang, Wei Dai, Pradeep Ravikumar, Inderjit Dhillon, and Eric Xing. PPDSparse: A parallel primal-dual sparse method for extreme classification. Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 545-553, 2017.
Qi Zhang and Wei Wang. A fast algorithm for approximate quantiles in high speed data streams. In 19th International Conference on Scientific and Statistical Database Management (SSDBM 2007). pages 29. IEEE, 2007.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 9
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix A
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [Ye]] See the supplemental repository or framewook
a e-mulis 1-mmlttaabbl--lasssiifiattt.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix B and the supplemental repository https
//github. htntthu..coooteeee htmm/vioshvvo//ao wwtprr//aammuiiiimm aammmllllaabeeee classificatiiiiicccc..c..aiiiiie wawooon--frrmoooo framework
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [No]
4. If you using existing assets (e.g., code, data, models) or curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "W7RLCB3pcxB", "reviewer": "Reviewer_wPJV", "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.", "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.\n", "limitations": "Limitations are well discussed.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n- 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.\n- The presentation is very clear (except one suggestion below).\n- The experiments are well elucidating the ideas of the paper.\n\n**Weaknesses**\n- 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).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "QhCnIKvJv3", "reviewer": "Reviewer_jQnM", "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. ", "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.", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The motivation is novel.\n2. A concrete implementation is provided.\n3. Some experimental results are provided.\n\nWeaknesses:\n1. 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.\n2. 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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8BfmHquOoA", "reviewer": "Reviewer_efJe", "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.", "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?\n\n2) Why this paper does not discuss the high-dimensional side-effects regarding the well-know \"curse of dimensionality\"?\n\n3) 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.", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "* Strengths\n\n1) Quality: high. \nThe 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.\n\n2) Clarity: high.\nThe whole paper is well-written and well-organized, thus it is easy to follow and understand.\n\n* Weaknesses\n\nRegarding the originality, significance, and completeness of the proposed method, the following concerns should be carefully considered.\n\n1) 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.\n\n2) 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.\n\n3) 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.\n\n4) 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept