Cluster Tree for Nearest Neighbor Search
Authors: Dan Kushnir
Sandeep Silwal
Venue: Accepted by TMLR ()

Abstract: Tree-based algorithms are an important and widely used class of algorithms for  Nearest Neighbor Search (NNS) with random partition (RP) tree being arguably the most well studied. However, in spite of possessing theoretical guarantees and strong practical performance, a major drawback of the RP tree is its lack of adaptability to the input dataset. Inspired by recent theoretical and practical works for NNS, we attempt to remedy this by introducing *ClusterTree*, a new tree based algorithm. Our approach utilizes randomness as in RP trees while adapting to the underlying cluster structure of the dataset to create well-balanced and meaningful partitions. Experimental evaluations on real world datasets demonstrate improvements over RP trees and other tree based methods for NNS while maintaining efficient construction time. In addition, we show theoretically and empirically that *ClusterTree* finds partitions which are superior to those found by RP trees in preserving the cluster structure of the input dataset.

Published in Transactions on Machine Learning Research (03/2025)
Cluster Tree for Nearest Neighbor Search
Dan Kushnir
Kan.kushaiir@nokii-bblll
Bell Laboratories, Murray Hill, NJ NOKIA
Sandeep Silwal
sitwal@es. wisc. edu
Deportment of Computer Science University of Wisconsin-Madison
Reviewed on OpenReview: htips: // openreview. net/ per/forum? id- ELLNNtcCoo@@ootteeee SMBBzmuuaa
Abstract
Tree-based algorithms Neighbor Search (NNS) with random partition (RP) tree being arguably the most well studied. However, in spite of possessing theoretical guarantees and strong practical perfor- mance, a major drawback of the RP tree is its lack of adaptability to the input dataset. Inspired by recent theoretical and practical works for NNS, we attempt to remedy this by introducing ClusterTree, a new tree based algorithm. Our approach utilizes randomness as in RP trees while adapting to the underlying cluster structure of the dataset to create well-balanced and meaningful partitions. Experimental evaluations real world datasets demonstrate improvements over RP trees and other tree based methods for NNS while main- taining efficient construction time. In addition, we show theoretically and empirically that ClusterTree finds partitions which are superior to those found by RP trees in proserving the cluster structure of the input datasel.
important and widely used class of algorithms for Nearest
1 Introduction
Nearest neighbor scarch (NNS) is a fundamental problem with applications in machine learning, databases, data science, and other fields and has enjoyed vast amount of algorithmic work, both in theory and practice (see the surveys Wang et al. (2016b); Andoni Andonii et al. (2018b); Wang et al. (2014), and [ang al. (2016a) and references within). The problem is defined as follows: given a dataset X Rd, build a data structure quickly return one more datapoints in X that are closest
over X so that for future queries g Rdd to q.
In this paper, we focus broadly on the space partition family of methods for nearest neighbor search. Given a query they produce a sublinear sized subset P C X (referred to as the candidate set.) that includes the desired neighbors. Then rather than computing distances to all points in X from g, we instead compute a sublinear number of distances. In space partition methods, the subset P returned determinod by space partitions that. "bucket" the points in X. This leads to substantially faster query times necessary for scaling to large datasets.
Space partition methods have numerous advantages: they are suitable for distributed and parallel computing as different partitions can be stored on different. machines (Bahmani et al. 2012 Ni et al. 2017 Li et al. 2017 Bhaskara & Wijewardena 2018 They are also GPU friendly due to predictable memory access patterns (Johnson et al. 2021). addition, they been used to design efficient and secure NNS algorithms (Chen al. (019). Lastly, they access the data in one shot, rather than multiple adaptive access, which is crucial for fast dataset construction well eryptographie security. Therefore, space partition algorithms are important (and well studied) class of algorithms for NNS. See also the motivation given in Dong et al. 22020)
mmany remarks apply indexing based methods broadly which space partitions fall under

---

Published in Transactions on Machine Learning Research (03/2025)
There are two main categories of algorithms that perform space partitions: (a) tree based methods (Bentley
1975
Uhlmann
1991
Ciaccia et al., 1997 Katayama & Satoh 1997: Liu et al.) 2004
Beygelzimer et al.
2006
Sinha 2015
Babenko & Lempitsky 2017] Ram & Sinha 2019b Dasgupta & Sinha 2013
2014) and Andoni & Indyk,
(b) hashing based methods such as Locality Sensitive Hashing (LSH) Gionis ct al.
1999;
2006:
Datar et al. 2004; Wang et al., 2014; 2016a). Tree based methods have further advantages over
hashing based methods as they are extremely fast to build (requiring roughly linear time on average), and
also provide the user control over the size of sets P returned for queries by setting an appropriate leaf-size.
Tree based methods have been shown outperform hashing based methods in practice as well (Sinha 2014
Muja & Lowe 2009;
Liu et al. 2004).
The most well studied tree based algorithm is the random partition (RP) tree of Dasgupta & Sinha 2013 2014p. It uses randomness in an oblivious manner to recursively compute partitions of the data. Despite some theoretical guarantees and strong empirical performance of RP trees, they have a strong deficiency which motivates ours paper: Can we utilize randomness while adapting to the underlying dataset structure for tree-based NNS algorithms?
1.1 Our Contributions
We consider a new tree based method which utilizes the power of random projections as in RP trees while adapting to the underlying cluster structure of the dataset. We name our tree ClusterTree. Our contribu- tions are follows:
Fast dataset construction: We optimize for balanced partitions (as in RP-tree) leading to fast tree construction, while also retaining other benefits of tree methods such as user level specification over the size of the returned set P.
Adapting to dataset structure: ClusterTree adapts to the underlying cluster structure to find balanced partitions, by essentially modifying the split criterion of RP-trees, and selecting an optimal projection direction for the split. This leads to meaningful and explainable partitions which are especially important given the recent. interest in explainable MT. algorithms (see references within recent works such as Wan et al. (2021); Dasgupta et al. (2020) and Carvalho et al. (2019) and the workshop of XAT (202))). ). Additionally, we provide hicrarchical clustering analysis for ClusterTree in the supplemental material.
Theoretical analysis and Empirical advantage: We study the performance of ClusterTree under natural dataset modeling assumptions and relate it to recent works graph cuts as well as fast methods for learning Gaussian mixtures; see Sections 2.1 3 for more details. Furthermore, our experiments on a variety of real datasets demonstrate that our method is superior to RP trees and other tree based methods; see Section and the supplemental material.
1.2 Related Works
We briefly overview additional algorithms for NNS besides the hashing and tree-based methods outlined in the introduction. The other class of meth besides space partitions include those where the goal is to generate compressed representations or codes of the input points so that distances can be quickly estimated (Wang
et al.
2014 2016a Ge et al. 2014 Jégou et al., 2011 Wu et al., (017) when a linear scan performed (whercas we are interested in sublinear number of distance calculations). There have also boen work combine compressed codes with tree methods such Product-Split trees (Babenko & Lempitsky 2017).
The fastest methods (with respect to the query time) empirically are graph based where similarity graph is constructed over the input points (Malkov & Yashunin, 2020: Hajebi et al., 2011 Malkov et al. 2014 Wu Then given query, the graph is traversed using a greedy algorithm until convergence.
et al. 2014
Note that space partition and tree-based algorithms, which are the focus of this paper, have several advan- tages over these methods. For example, the graph basod scarch methods lack theoretical guarantocs, have sub-optimal 'locality of reference' (which makes them unsuited for modern architectures (Johnson et al.
2021 Bahmani et al. 2012 Ni al. 2017 Li et al. 2017 Bhaskara. & Wijewardena 2018 Sun et al.
2

---

Published in Transactions on Machine Learning Research (03/2025)
2014 slow construction time, and require adaptive access to data; see the introduction for more benefits of tree-based methods.
We focus on tree based methods which adapt to the underlying dataset. RP trees are stated to adapt to the intrinsic dimensionality of the data and perform better for dataset possessing small intrinsic dimension (Dasgupta & Sinha, 2013; 2014). However, the RP tree construction algorithm is agnostic to structure and density and uses randomness in data-oblivious manner. Other methods which explicitly utilize the dataset at hand include PCA trees and 2-means trees. PCA trees recursively split on the top principal component of the dataset (Sproull 2005; Kumar et al., 2008 Abdullah et al. 2014h. While more adaptive than RP trees, PCA trees can be significantly costlier to construct due to PCA computation (McCartin-Lim et al. 2012) 2-means trees on the other hand, adapt to the dataset by recursively finding partitions which minimiie the 2-means cost (Dong et al. 2020). We note work on adapting the guarantees of RP trees to KD trees, but the performance of KD-trees is still worse than RP trees or PCA trees (Ram & Sinha 2019a). Lastly, we mention that several augmentations to RP trees have been proposed, such as using sparse random projections and Traversing the tree using auxiliary information (Keivani & Sinha 2021 Hyvönen et al. 2016: Sinha & Keivani 2017). Amongst the above tree methods, RP tree is closest to ClusterTree random one-dimensional projections. However, ClusterTree employs a more sophisticated algorithm to process the projections, which optimizes for balanced data partitions while adapting to the input dataset cluster structure. Lastly, we remark that one-dimensional projections have been recently used (for both theory and practice) in other settings, such as k-means clustering (Charikar et al. 2023
they both utilize
2
The ClusterTree Algorithm
2.1 Motivation
In this section we motivate our algorithm for ClusterTree. First, we briefly outline tree based algorithms for NNS: trees are constructed starting from the root node, which represents the entire dataset. Then every node is processed by splitting the points at the node using some partition rule to create left and right child nodes. The partition rule is recursively applied to each node until each leaf node of the final tree contains at most user specified P number of points. Therefore, any tree based algorithm can be specified by its choice of partition rule. Given a query 9, we traverse the tree, following the correct side of the partition the query lands on, until we reach a leaf node.
For RP trees, the partition rule consists of projecting points in a node to one-dimension via a random projection and then splitting based on the median (or slight perturbation of it). It's effectiveness comes from the fact that the randomness is unlikely to split a query from its true nearest neighbor.
However, picking the median split after random projection can be sub-optimal. For example, suppose that the one-dimensional projection results in two well separated clusters where each cluster contains non-trivial fraction of points and one cluster is slightly larger than the other. The median split passes through the larger cluster and splits into two parts which can adversely affect the accuracy of future queries: if query's true nearest neighbors is part of the larger cluster, we can fail to return many nearby points if we descend into the wrong part of the partition. In this case, a better choice of partition would have adapted to the cluster structure by separating the two clusters, and would have allowed for higher quality nearest neighbors to be returned. See Figure 1 for an example.
However, we still have lo roughly balance every partition to ensure that the tree construction time is (a((x)). In particular for the nodes at the top level of the tree, we must ensure both parts of the partition contains a constant factor of the number of points the node to guarantee fast construction time. To balance these two objectives, we use the well known notion of graph conductance which optimizes for both balanced partitions and cluster quality. Our strategy after performing a one-dimensional random projection is to form k-nearest neighbor graph, for some parameter k and find a conductance minimizing partition. For details, I This raises some natural questions:
see Algorithm
Why graph cuts? Graphs cuts are motivated by both recent theoretical and practical develop- ments. On the theoretical side, there are recent works on NNS for general metrie spaces that rely
3

---

Published in Transactions on Machine Learning Research (03/2025)
(a)
(b)
(c)
(d)
Figure 1: (a) Dataset consists of two well separated clusters. (b) Random one-dimensional projection of the dataset. Histogram denote the density of projections. (c) Partitioning strategy of RP trees which uses the median of the projection. (d) Our partitioning strategy successfully separates the clusters.
on spectral graph theory (Andoni al. 2018c db. On the practical side, recent work of Dong et al. (2020) shows that learning space partitions induced from graph cuts of the k-nearest neighbor graph using machine learning tools leads to very competitive algorithm for NNS. Furthermore, another popular set of algorithmns for NNS is to build graphs for dataset X (such as the k-nearest neighbor graph) and then given a query, perform a random walk to determine the output. The intu- ition underlying these works is that graph structure captures properties such as clusterability, which intimately tied to graph cuts, and is important for accurate NNS algorithms. Lastly, another advantage of graph cuts based on conductance is that also optimizes for balanced partitions.
We note that the learning based method and the random walk based method are not scope of this paper since both require large computational cost build the search data structure: both require building graph on the dataset while the learning based method further requires finding sparse cuts on the whole graph (in addition to processing it using neural network). In addition, the second method crucially requires adaptive access to the dataset while tree based method access the data in 'one shot' which is needed for secure search such as over encrypted data (Chen et al. 2019 in addition to the multiple benefits outlined in Section
Why one- miedeimesioonal projections? There practical and theoretical reasons why perform one-dimensional projections. On the practical side, building the k-ncarest neighbor graph in one- dimension is extremely fast (nearly linear time) as it can be computed quickly after sorting. This is not true in larger dimensions. Furthermore in one-dimension, there is natural set of cuts to optimize over, which are cuts based on prefixes of the sorted order. On the theoretical side, we motivate this procedure by studying clusterable datasets under a natural Gaussian model. By relating prior works, show that under natural assumptions, (a) optimizing for hyperplane prefixes leads to 'good' partition for NNS, and (b) one-dimensional projections capture cluster structure present in the original dimension. Lastly, optimize over multiple random projections independently as single projection can be very noisy; however, we can significantly increase the probability of capturing the cluster structure by trying multiple projections.
based
2.2 Algorithm
We present below our algorithm for ClusterTree (Algorithm 2), which employs the efficient one-dimensional cut detection described in Algorithm [
First, we define the notion graph conductance.
Definition 2.1 (Conductance). Given graph G (V, F), V1 V, and V V V1, the conductance of the cut (V1, V) is given by
E(V.. V)
(VV)) = min(vol( Vi), vol(V)
where E(V,, V) is the number of edges between V1 and V and vol(S) denotes the sum of degrees of vertices in S.
4

---

Published in Transactions on Machine Learning Research (03/2025)
Algorithm OneDPProjction((X,77
Require: Dataset X C. R with |X| n, T,k 0
Ensure: Output partition X X1 U X2, vector v
1: for = 1 T do
X random 1 dimensional projection of X using v' Rd
Y y,....; Y, sorted X with each Y, E R
G + k-ncarest neighbor graph on X*
5:
Pi < min (((,) where Sj is the cut in Go given by (Y,,..., Yj), (1,,,........................... Y.)
6:
w (v',B) E Rd+1 is the vector encoding the projection which determines the cut
7: end for
Return the partition X2UX₂ induced by the cut with the smallest 9; value and the vector w associated with the cut
The above Algorithm 1 performs our data adaptive one dimensional splitting rule. At a high level, it forms nearest neighbor graph one dimension after projecting the dataset, and finds the sparsest prefiz cut in the ncarest neighbor graph. v is the random vector resulting set of real numbers after computing the inner product with v² for every point in our dataset. We sort the one-dimensional embedding represented by X to form Yi...., Yn where note that each Y; E IR Finally, Algorithm 2 uses the partition strategy of Algorithm to form a tree structure, and Algorithm 3 recovers the NN of an input point q.
to perform the random projection and X is the
Algorithm 2 MakeCluster Tree( X, (ree(X, k,
Algorithm 3 Query(g.
Require: Dataset C Rd leaf size P. T, k 2 Ensure: Output Cluster Tree over X
Require: Query q E R&, ClusterTree
Ensure: Output leaf of T where q falls in
if | P then
1: Current node +
Return leaf containing X
2: while current node is not leaf node do
3: end if
3: Pick left or right child of current node
4: (X1, X2, v) + OneDProjection X, k)
based on its projection and bias
5: LeftSubTree + MakeClusterTrees (i,, P,T, k)
4: end while
RightSubTree + MakeCluster' Tree (X2, P.T.K. k) Return (LeftSubTTree, RrehtSubTree)
5: Return points of X in the leaf fitting the
query q
Remark 2.1. Each node of the tree is implicitly stores the vector e used to perform the partition.
3 Theoretical Analysis
We first analyze the runtime of ClusterTree. We start with quantifying the number of operation in OneD- Projection:
Lemma 3.1. The runlime of OneDProjection is O(T (nd + n log + nk)).
Note that we might not be optimizing for the cut with lowest conductance since such cut could potentially not respect the sorted ordering. However, we show in the next lemma that order preserving cuts are the sparsest cuts in the graph (fewest number of edges crossing the cut) which suggests that optimizing over prefix cuts is sufficient. We further motivate optimizing over prefix cuts with additional theoretical results in Section 3.1 and Theorem 3.5
Lemma 3.2. Consider a k-nearest neighbor graph on a set of n points (XI...., C R. satisfying X, S X(41 for all S n 1 The spursesl cul respects the sorted ordering. That is, the cut with the fewes! number of edges is of the form (X1....;,,). (x,.,.x.).xx for some j.
We now state an assumption about the balanced partitions. Note that conductance antomatically rewards balanced cuts but for worst case dataset, it can potentially find very unbalanced cut which will lead large tree construction.
5

---

Published in Transactions on Machine Learning Research (03/2025)
Assumption 3.3. For sufficiently large datasets [X], Algorithm min((X:1,|X22) 2 c|X] for independent. constant 1/2.
1 returns
partition
such that
We argue that this is valid assumption for our algorithm Assumption 3.3 holds for datasets with very different structural properties. For example, the assumption holds for uniform inputs on one hand and also highly clustered inputs on the other hand (see Section D In addition, we empirically verify 3.3 for real datasets as well in Section D
Lemma 3.4. Given Assumption 3.3 the tree construction time of MakeCluster is O(T log'oog (nd + log + nk)) = O(Tnd Tnlog n Tnk log n) O(nd) for K. T O(1) as in our experiments.
3.1 Nearest Neighbor Guarantees
We now study the guarantees for ClusterTree for the problem of nearest neighbor search. We define two parameters, and B, that have been used in the context of nearest neighbor search (Dong et al., 2020). For given data sct, a and 3 mcasure the average distance squared between two k-nearest neighbors and the average distance squared between two arbitrary points, respectively.
Definition 3.1. Let D be distribution from which we sample our dalaset X. Denote Delose to be the distribution over random k-nearest neighbors (I,z') E X. To sample from Delose, we first pick uniformly random point x E X and then a uniformly random k-nearest neighbor x' of x. Define
a = B(z,x'' | 22112 B = - 2'12.
Note that a is the expected distance squared between two 'close" points in X (with respect to k-nearest neighbors) and B is the expected distance squared between two random elements of X.
The asumption a & 8 is natural since it states that nearest neighbors are closer than arbitrary pairs of points and thus a non-trivial algorithm is needed, rather than just returning a random point.
We utilize the following theorem from Dong et al. (2020):
Theorem 3.5. There exists a hyperplane H = {x E Rd (a,z) = b} such that the following holds. Let X X, X2 be the partition of X induced by H Xi = (x E (a, x) S X2 for E X (a, b}. Then, one has
Pi(a,z)EDeoo [I, I' are separated by H]
2a
<
min min(PrzwD(ar E X1), PrawD x X2))
Remark 3.1. The eristence of the haperplane from Theorem 8.5 is proved using spectral graph theory and is intimately connected to a sparse cut in the k--earest neighbor graph of X. Furthermore, Theorem 3.5 only guarantees the exislence of a good hyperplane cut, ruther than an arbilrary cul that may not be defoned by a hyperplane. However, this is exactly the family of cuts we optimize for in Algorithm Q
Theorem 3.5 roughly states that if nearest neighbors are much closer than arbitrary pair of points, then a good hyperplane cut exists which separates the dataset into approximalely balanced parts while also assuring that many k k-nearest neighbor pairs in the same partition. This is natural assumption to make since otherwise, returning arbitrary points for queries could suffice for approximate nearest neighbor applications.
Note however that this is an assumption about the dataset in the ambienl dimension, but we are finding cuts after performing a random one-dimensional projection. We argue that after such a projection, the values of a and 3 are approximately preserved.
Lemma 3.6. Suppose we sample our dataset X from distribution D. Let P be a random one-dimensional projection independent of X and define PX = [Px x E X). Let axx, 3x and axxx 3px denole the volues of and 3 for the datasets and PX respectively. Then arx S ax and ßrx = -3x
Lemma 3.6 states that if datasct X satisfies ax < 8x, then the projected dataset PX also satisfies OPX & Bpx. Then by an application of Theorem 3.5 we know that we can find good hyperplane cut for the projected dataset. However, it is not clear that such hyperplane would also perform well for the

---

Published in Transactions on Machine Learning Research (03/2025)
original dataset with respect to nearest neighbor search since points can be heavily distorted after random projection onto one-dimension. In the next section, we argue the soundness of performing one-dimensional projection by assuming a Gaussian mixture model. While this is a simplifying step that does not model all realistic datascts, it serves to highlight the fact that the assumption a < 3 is natural for datasets with a strong cluster structure, in addition to showing significance of trying malliple one-dimensional cut in Algorithm | and picking the best cut. This is important since a single one-dimensional cut has a high chance of returning a very 'noisy' output, even if the original dataset has a strong cluster structure. Thus trying multiple cuts boosts the probability of finding a 'good' projection.
3.1.1 Gaussian Mixture Model
In this section, we analyze the performance of Algorithm for the mixture of two well-separated Gaussians and provide bounds on the number of projections that are needed in Algorithm in terms of the mixture parameters. Our intention is to demonstrate the advantageous behaviour of ClusterTree in the cases of clustered data points. We start with the definition of c-soparated Gaussians.
Definition 3.2. Gaussions N(,1, En) and N (u2, Σz) in Id are defined to be c-separated for
| u2ll
c:= Va (E)+ (E2)
where X1 (E) denotes the largest eigenvalue of the matrix Σ. We consider the case were e is al least a constand value, independent of d.
We first instantiate Theorem 3.5 for mixture of two Gaussians.
Lemma 3.7. Suppose that dataset X with |X| = is sampled from the distribution D ~ wN wN En) + (1 (M), 22). Further, suppose that X contains at least k points from each of the two distributions that make up D and min(w, - -w)- = 2(1. Define ax and Bx as in Defonition 3.1 Then ox S (rxx(tr(E)),,r(EE)) and 3x= = 2211 - P2ll2 + tr(Ei + +E2)).
Remark 3.2. Note that the hypothesis in Lemmaa 3.7 about X having at least l. points from each component is easily satisfied with high probability = o(n) and min(w, w) = 2(1 by a Chernoff bound.
k=
Lemma 3.7 tells us that if 1|21l (distance between the two Gaussian means) is sufficiently large compared to max (tr(E,),tr(E_))) then a /3x x is bounded away from 1. For example, if we have two spherical Gaussians with covariance matrices La and Iā respectively, then we require d n max (o),o)) S || - u22l for xx/3xx < 1/d to hold. In terms of Definition 3.2. it suffices to require c 22(1) to guarantee exx o(1).
The following lemma connects the concept of c-separability with the guarantces of Theorem 3.5
Lemma 3.8. Suppose dataset X is sampled from distribution 'D ~ wN(( Eg ) + - (-- ()22 E2) and the conditions of Lemma 3.7 hold. Then ax/3x 1/e2² for e as in Desinition 3.2
Note that the above discussion applics to the original, yet to be projected, dataset. The hope is that a well-separated pair of Gaussians will remain so after a random projection. This might not be the case as single projection can be extremely noisy since we are projecting to an extremely small dimension. However, it is possible to derive the number of one-dimensional projections needed for well-separated mixtures to also project to well-separated one- one- dieensiiniinll mixtures. Thus by optimizing over multiple cuts in Algorithm [ we can hope to pick a one-dimensional projection which ensures that different components remain separated after the projection.
We first need to define the Q function: For R, Q(x) - f. exp(-t3/2) dt. The following result bounds the number of projections needed to achieve well-separated oimeniinaiol projections Kushnir et al. (2019).
Lemma 3.9. Suppose our dataset X is minture of two c-separated spherical Gaussians in IRdd Let T(cl, d) denote the expected number of one-dimensional projections needed for the two miztures to project to d'- separaled projection in one-dimension. Then we have lim T(e, d) 1/(2Q(d
The following corollary states that we only need a sub-logarithmic (in d) number of one-dimensional projec- tions to guarantee the same order of separation as in the ambient. dimension.
7

---

Published in Transactions on Machine Learning Research (03/2025)
Lemma 3.10. d' is such that c' I e(log log d)o(), then T(d,d) dd) ollogd).
4 Experiments
In this section we evaluate our algorithm empirically on real and synthetic datasets. Our main results shows the trade-off in acceleration and accuracy of ClusterTree As in other NNS works, we measure the fraction of actual k-ncarest neighbors among the returned candidates (Dong et al. 2020). This metric measures the processing time required for queries since distances are compuled from a query to all of the returned candidates. As seen below, and in the additional experiments we provide in our supplementary material, in the vast majority of cases Cluster outperforms all benchmarks in its accuracy- toseyytttpppeeee co--poooessinnttiiiiiieee trade-off.
Datasets. We use the following datasets which have been used in previous machine learning works on clustering and nearest neighbor search (for example the works of Dong et al. (2020); Keivani & Sinha (2021)
Lucic et al. (2018), and Bachem et al.] (2018)): KDD Cup (clustering dataset from a Quantum physics task)
(kdd 2004). News (datasct of news text. where each feature represents
key word includod) (Rennic
2016
Spam (spam text where each feature represents the presence of particular word associated with
spam
van Rijn 2016), SIFT (image descriptors) (Aumüller el. al., 2017), and Gaussian Mixtures. See
Table
Due to space limitation provide experiments with additional data sets in appendix E and
Benchmarks. Our main focus is tree-based algorithms since they are preferable in numerous settings (such as fast construction time, secure computation, and distributed and GPU architectures). Our baselines are the following. Random Partition (RP) Trees: This is the method from Dasgupta & Sinha (2013) 2014) and is arguably the most common tree-based nearest neighbor search algorithm. For RP trees, the partition strategy to split along the median (or a small perturbation of the median) after performing one dimensional random projection. 2-means Trees: The partition strategy is to split points after performing 2-means clustering. We use the classic k-means algorithm until convergence (Dong et al. 2020). PCA Trees: the partition strategy is to split along the median after projecting onto a principal direction (Sproull 2005 Kumar et al. 2008 Abdullah et al.) 2014). Locality Sensitive Hashing (LSH): While this is not a tree- rree-basdd method, it is a classic space partition algorithm and the most well studied theoretical approach (see references Section D. We use the Cross-Polytope version from Andoni al. 2015 2018a).
Dataset
(Size)
(Dimension)
Gaussian Mixture
10*
10a
News
105
10a
RNA
~ 10
8
Spam
~ 106
57
SIFT
10f
128
KDD Cup
5 104
78
Table 1: Datasets used for our experiments.
Parameter Selection. In all of our experiments, we use a fixed value of T = 20 random projections in Algorithm [ For the value of k, we initialize k = 20 and keep increasing k by one until the value of the normalized cut found stops decreasing. Intuitively, it ensures we don't overlook a potentially better cut. Empiricallyy we observed that this only iterates over a few values (~ 5) k.
Evaluation Metric. As other NNS works, we measure the number of candidates returned for queries versus the k-NN accuracy, which is defined to be the fraction of its actual k-nearest neighbors that are among the returned candidates (Dong al.) 2020). This metric measures the processing time required for queries since distances are computed from query to all of the returned candidates. Note that tree-based methods have close to identical query costs. For example, if the trees are all approximately balanced, then on average we perform the same number of operations to return the set of candidates for queries (logarithmic number of vector operations to traverse the tree). Furthermore, the 'wall clock' time for performing queries can be heavily dependent on specific architectures and implementations. Thus, we focus on the quality of the partitions given by the trees. We display the average over 10 independent trials in all of our results and shade +1 standard deviation where appropriate.
8

---

Published in Transactions on Machine Learning Research (03/2025)
Gaussian Mixture
Spam
News
1.00
0.70
RP Tree
0.99
0.99
Accuracy
0.65
1-NN Acturacy
0.98
LN Accuracy
0.97
0.60
0.55
0.95
0.96
0.50
0.94
Cluster Tree
0.95
Cluster Tree
0.45
0.93
RP Tree
Tree
10-10f 12-10f 14 20 16-204 10 11o 20 104
1-10f
2-104 3-10f 4 10 6-10" 7-30"
250
600
200
Candidate Size
Candidate Size
Candidate
SIFT
KDD Cup
0.50
Cluster Tree
Cluster Tree
Tree
0.90
RP Tree
1/N Accuracy
0.45
1 Accuraty
1ANN Accuracy
0.05
0.40
0.91
0.35
0.90
0.75
0.89
Clustar
0.30
0.88
RP Tree
0.65
2-10f
2000 2500
Candidate
Candidate Size
Candidate
Figure 2: Candidate Size vs 1-NN Error for ClusterTree and RP tree for datasets in Table
Gaussian Mixture
Spam
News
1.00
1.0
Cluster Tree
0.95
0.6
LNN Accuracy
0.90
JNN Accurscy
2 2-Mcans Tree
0.5
0.4
Cluster Tree
0.85
0.6
LSH
0.3
RP Tree
0.80
Cluster Tree
0.4
0.2
PCA Tree
Means
0.75
RP Tree
0.2
0.1
0,70
FCA Tree
2000
:0002
15020
20000
25300
1-10f
2-10"
3-10"
4-18' 3-10
6-30f 7-10
1000
200U
2000
4000 5000 eOUD 7006
Candidate Size
Candidate Size
Candidate Size
RNA
KDD Cup
1.0-
0.8
1-NN Accuracy
1-NN Accuracy
0.6
0.6
Cluster Tree
Cluster
0.4
RP Trea
0.4
RP Tree
M-Maans Tree
2-Means
0.2
PCA Trea
0.2
PCA Tree
LSH
LSH
0
1000 2000 3000 4000 5000 6000 7000 8000 Candidate Size
1000 0
2000 3000 4000 5000 6000 7000 Candidate Size
Figure 3: Candidate Size vs 1-NN Error for all baselines.
Nearest Neighbor Experiments. We first evaluate the performance of the algorithms on 1st nearest neighbor error. We ranged over various candidate sizes (by iterating over the leaf parameter) and plotted the fraction of times the nearest neighbor is in the candidate set for a query, averaged over all queries. most datasets, ClusterTree is outperforming RP Trees fewer candidates are required to get better 1-NN accuracy. We provide results for additional six data sets in appendix E
The results for ClusterTree versus RP trees are displayed in Figure 2 We see that for
In Figure 3 we show the results for all of the baselines. We observe that 2-means tree performed the worst on most datasets. Note that for the two datasets KDD Cup and RNA, the computationally intensive PCA trees performed better than ClusterTree, while for the others: News, Spam, and Gaussian Mixtures, ClusterTree was the best algorithm. Nevertheless, ClusterTree has been consistently better than RP Trees. We also remark that it was not computationally feasible to run 2-means Tree and PCA trees for SIFT

---

Published in Transactions on Machine Learning Research (03/2025)
(a)
(b)
(c)
(d)
Figure 4: First two PCA axes of: (a) KDD CUP, (b) RNA, (c) GMM, and (d) SIFT.
GMM
Spem
News
Cluster Tree
0.65
Tree
0.398
0.99
10-NN Accuracy
NN Accuracy
0.60
0.98
0.55
0.96
0.50
Cluster Tree
0.95
Cluster Tree
0.45
RP Tree
RP Tree
10000
12000
14000
18000 18000
20020
1012
10"3 10t 3045 10 10 18*
230
400
600
1200 Candidalle Size
800
1000
1400
Candidate Size
Candidate Size
SIFT
RNA
KDD Cup
Cluster Tree
0.975
0.90
0.400
RP Tree
0.85
Accuracy
NN Accuracy
10 Accuracy
0.375
0.925
0.350
9.000
0.325
0.875
0.70
0.300
0.050
0.65
0.275
0.825
Cluster Tree
Cluster Tree
Tree
0.800
2-10"
3-10' 4-10* 5-10" 6-10f 7-10*
200
500 Candidate Size
400
860
500 1000 1500 2000 2500 3000 3500 Candidale Size
Candidate Size
Figure 5: Candidate Size vs 10-NN Error for ClusterTree and RP tree.
and Spam. We are not plotting error bars for 2-means tree for clarity since it was much larger than all the other algorithms; overall, we observed 2-means trees to be an inherently unstable algorithm.
We repeat the I-NN experiments for 10-NN in Figures 5 and (also in appendix Ep. Note that PCA trees outperform ClusterTree on the KDD Cup dataset but ClusterTree is the best algorithm all other datasets. Note that PCA trees and 2-means trees costly to construct, especially for large datasets, since they are employing much more computationally intensive partition rule than ClusterTree or RPP trees. Lastly, LSH was not as tuneable as the tree-based algorithms in terms of specifying the approximate size of candidates to return; we could smoothly increase the candidate sizes for each tree based algorithm but LSH had a strict lower bound for the number of candidates returned per dataset, even after using a large number of hash functions, for some datascts such as Spam. This maybe due the fact that LSH is not well suitod for point sets whose norms not well concentrated.
Tree- Construction Running-Tinee -ime. We note that both RP Trees and ClusterTree are highly efficient to construct in practice and their main difference is in the quality of candidates returned queries, for which we remonstrate ClusterTree's advantage. Since we optimize over multiple projections, there is a marginal overhead of using ClusterTree over RP trees. Even on a dense dataset (SIFT) of 10t point in dimension 128 with the leaf parameter set to 103 the runtimes to create an RP tree was 11.8 seconds on average whercas ChusteTree took 45.2 seconds. Thus, we do not envision the tree construction be a bottleneck practice since they only have to be constructed once.
10

---

Published in Transactions on Machine Learning Research (03/2025)
Gaussian Mixture
Spam
News
0.7-
0.998
Cluster
1.0
0.6
RP Tree
RP Trea
DDNN Accuracy
1o.NN Io.NN Accuracy
0.8
Mcans Tree
0.5-
994
LSH
PCA Tree
0.6
0.4
0. 992
10-NN
Cluster Tree
0.3
RP Tree
0. 990
0.4
0.2
Means Tree
PCA Tree
0.1
LSH
10 2-10f 3-101 4-30" 5-101 6-101 7-104
2000 1000
2000
4090 5000 6000 7000
Candidate Size
Candidate Size
Candidate Size
RNA
KDD
Tree
RP Tree
10-NN Accuracy
Means Tree
10-MN Accuracy
0.8
PCA Tree
0.6
LSH
0.6
Cluster Tree
0.4
RP Tree
Means Tree
0.2
PCA Tree
/
LSH
0.0
Candidate
Candidate Size
Figure 6: Candidate Size vs 10-NN Error with all baselines.
Accel.
factor max
Bucket size
CTTree Accuracy
RPTree
Accuracy max
Comments
Dataset
min
min
max
min
max
min
GMM
x1.07
x1.27
15302
16430
0.64
0.69
0.61
0.6
SPAM
x2.25
x2.7
3489
24130
0.9980
0.9985
0.9968
0.9975
News
NA
NA
NA
NA
1.0
1.0
0.95
0.99
No shared y-values
SIFT
x1.0
x1.07
14639
68514
0.35
0.43
0.35
0.41
non separable (Fig. 4d)
RNA
X6.56
x7.44
92
123
0.94
0.978
0.95
KDD Cup
x1.34
x1.48
2355
178
0.86
0.88
0.84
0.84
Table 2: ClusterTree vs. RP'rree query running-time acceleration min and max values for 10-NN.
Query Running-Time of ClusterTree vs RP Tree. The main difference between the two data structure is the quality candidates returned on queries. To this end, the experimental setting for Figures 2 and can be used to calculate the acceleration in query time achieved with ClusterTree over RP Trees for a given accuracy, which in shown in Table 2 for the 10-NN case. The table provides the minimal and maximal acceleration factor obtained by ClusterTree in terms of the number of distance computation operations used to retrieve the candidates for given bucket size. For example, 10t points in 2 takes 0.1 seconds. Table 2 also provides the bucket sizes corresponding to the maximal and minimal acceleration obtained, and the accuracy of each method at the minimal and maximal accuracy difference between the mothods. Hence, the trends observed in Table 2 largely depend on the clusterability of each data set (see discussion below and Fig. 4). We also provide similar tables for comparing ClusterTree with the two other gree-based baselines in appendix
RP Trees for each data, set. We measure the running time
Varying Number of Projections. We ranged over various candidate sizes and plotted the 1-NN error the number of projections (the paramcter T) in Algorithm | varied. This is to demonstrate that optimizing over multiple one-dimensional projections is important in practice, as suggested by our theoretical analysis. While the number of projections does not influence the performance for some datasets, we note that for datascts such as News and RNA, optimizing over multiple projections advantagcous. The results are shown in Figure 7 Note that only for this experiment, we use a randomly sub- sab-sampled datasets Spam, News and SIFT with 5 10 points for computational efficiency.
11

---

Published in Transactions on Machine Learning Research (03/2025)
0.26
Gaussian Mixtures
Spam
News
0.912
0.24
1-NV Accuracy
Accuracy
1-NN Accuracy
0.42
0.906
0.40
0.904
0.16
0.902
0.14
0.38
20
0.900
1500
2000
3500
1000
15.00
1500
2000
2500
3000
3500
60
80
160
120
140
Candidate Size
Candidate Size
Candidate Size
RNA
KDD
0.8
1.00
20
0.7-
1AN Accuracy
1-NN Accuracy
0.85
0.6
0.97
0.80
0.5
0.96
0.75
0.95
0.94
0.70
10000
15000
20000
25000
200
400
860
1000 1200 1400 3800
2000 2500 3000
Candidate Size
Candidate Size
Candidate Size
Figure 7: Optimizing over multiple projections in Algorithm
can improve accuracy.
When can expect ClusterTree to outperform RP trees? Our tree construction method especially exploits the cluster structure as it builds the tree over the dataset. If the dataset does not possess such a property, we expect ClusterTree and RP trees to have approximately the same behaviour. To highlight this, we plotted the first two PCA projections of the centered and normalized versions of some of our datascts in Figure 4 We can observe a strong cluster structure KDD Cup, RNA, and synthetic datasets. The projection of the SIFT dataset is mostly uniform over region, signifying that it lacks such a structure compared to the other datasets displayed, and therefore ClusterTree advantage lower, as seen above, see in Figure 2 that ClusterTree superior to RP trees in the 1-NN experiments for KDD Cup, RNA, and synthetic datasets whereas it is comparable to RP trees for SIFT. Our other experiments above follow a similar pattern. Therefore, we believe ClusterTree is preferable over RP trees as many natural datasets have a strong underlying cluster structure.
Likewise,
Additional Experimental Results. Additional experimental results given in Appendix C including smoothness of the tree metric, and validation that ClusterTree preserves cluster structure of RP-trees. We also provide more results with additional data sets in appendix E and acceleration tables for additional tree benchmarks in appendix
5 Conclusion
We presented novel and fast construction of tree-based algorithm to perform fast nearest neighbor search in high dimension. Our approach utilizes randomness in RP trees while adapting to the underlying cluster structure of the dataset to create well-balanced and meaningful partition tree. This balancedness allows fast and accurate search of nearest neighbors. Our Theoretical analysis and the usage of the fast 1-dimensional graph-cuts provides a solid support to ClusterTree' empirical performance, particular to advantage over RP trees and other related benchmarks.
References
Kdd cup. http::/osmmot.c cornell. hwt.melll.ee///ddccpp/tttteeeee html 2004.
12

---

Published in Transactions on Machine Learning Research (03/2025)
ICML 2021 Workshop Theoretic Foundation, Criticism, and Application Trend of Explainable AI, 2021. URL https://icm120211 www..aitt..........i. 10/
A. Abdullah, Alexandr Andoni, R. Kannan, and Robert Krauthgamer. Spectral approaches to nearest neighbor search. 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 581-590, 2014.
Romina Ahumada, Carlos Allende Pricto, Andres Almeida, and et al. The 16th data re- lease of the sloan digital sky surveys: First release of manga-derived quantities, data visu- alization software, and stellar library. The Astrophysical Journal Supplement Series, 249(3): 3, 2020. doi: ing an SQL query on the SDSS database: SELECT TOP 50000 ra, dec, u, g. I, i, z. petroRad,, petroRadErr,, erpRad, eer OA OANDi OAND; > 0.
URL https: //www//wwww../ http://wwwws....eoeeeeeee wdds.orgg Data obtained us-
H0thoooooootoo > OANDg
Mohamad A. Akra and L. Bazzi. On the solution of linear recurrence equations. Computational Optimization and Applications, 10:195-210, 210, 1998.
Alexandr Andoni and P. Indyk. Near-optimal hashing algorithms for approximate nearest. neighbor in high dimensions. 2006 4 7th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), pp. 459 468, 2006.
Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Πya Razenshteyn, and Ludwig Schmidt. Practical and op- timal Ish for angular distance. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015. URL https: //proceedings.o /pppoeellns..errrppp..aaappp//pp https////ppppsas./////c/aaaaaaaa
Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Πlya Razenshteyn, and Ludwig Schmidt. Falcomn - fast lookups of cosine and other nearest neighbors. httpp://ggttaoooccoo/////ooooLLD 2018a.
Alexandr Andoni, Piotr Indyk, and Ilya P. Razenshtoyn, Approximate ncarest ncarest neighbor search in high dimen- sions. CoRR, bbss/180.009223, 2018b. URL
Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya Razenshteyn, and Erik Waingarten. Data-dependent hashing via nonlinear spectral gaps. In Proceedings of the 50th Anmual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pp. 787-800, New York, NY, USA, 2018c. Association for Computing Machinery. 03/5/33188755.188888 URL htttps://dat wtt.://......///1/////44441 .188844331886666
ISBN 9781550355599. doi:
Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya Razenshteyn, and Erik Waingarten. Hölder homeo- morphisms and approximate nearest neighbors. In 2018 IEFE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 159 10-,199,16 2018d. doi:
Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. Ann-benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. In International Conference on Similarity Search and Applications, pp. 34-49. Springer, 2017.
Artem Babenko and V. Lempitsky. Product split trees. 2017 IEEE Conference on Computer Vision and Pottern Recognition (CVPR), pp. 6316-636 6324, 2017.
Olivier Bachem, Mario Lucic, and Andreas Krause. Scalable k -means clustering via lightweight coresots. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Min- ing, KDD '18, pp. 1119-1127, New York, NY, USA, 2018. Association for Computing Machinery. ISBN URL
9781450355520. doi:
3219997
Bahman Bahmani, Ashish Goel, and Rajendra Shinde. Efficient distributed locality sensitive hashing. In Proceedings of the 21st ACM International Conference on Information and Knowledge Management, CIKM '12, pp. 2174-2178. New York, NY, USA, 2012, Association for Computing Machinery. ISBN 9781450311564. doi: 10.1145 00.1145/239615 /239676996677 2.2995969966 URL htttps://don wtt.:/...00/1.1..1.........
2398596.
13

---

Published in Transactions on Machine Learning Research (03/2025)
J. Bentley, Multidhmensional binary search trees used for associative searching. Commun. ACM, 18:509 181709-517, 1975.
A. Beygelzimer, S. Kakade, and J. Langford. Cover trees for nearest neighbor. Proceedings of the 23rd international conference Machine learning, 2006.
Aditya Bhaskara and Maheshakya Wijewardena. Distributed clustering via Ish based data partitioning, International Conference on Machine Learning, pp. 569 578, 2018.
Diogo V. Carvalho, Eduardo M. Pereira, and Jaime Cardoso. Machine learning interpretability: survey on methods and metrics. Electronics, 8(8), 2019. ISSN 2079-9292. doi: 10.339//cletrronicss38333222 URL
httpps//ww..ndgp..co//////199999
Moses Charikar, Monika Henzinger, Lunjia Hu, Maximilian Vötsch, and Erik Waingarten. Simple, scalable and effective clustering via one-dimensionall projections. In A. Oh, Naumann, A. Globerson, Saenko, M. Hardt, and S. Levine (eds.). Advances in Neural Information Processing Systems, volume 36, pp. 64618 64649. Curran Associates, Inc., 2023. URL Utt.attpee//prroceddgg...ooeooo.
www.:nng.....riis.comm wwwpc//ppprrr_ee http://cc///pppp...eaa//aaa////a filles/paaper//0233
file/ http:c/feeccccaaaaaaaaaaeaaeeee0
Hao Chen, Ilaria Chillotti, Yihe Dong, Oxana Poburinnaya, 1lya Razenshteyn, and M. Riazi. Sanns: Scaling up secure approximate k-nearest neighbors search. ArXiu, abs/1904.02033,, 2019.
P. Ciaccia, M. Patella, and P. Zezula. M-tree: An efficient access method for similarity search in metric spaces. In VLDB, 1997.
S. Dasgupta and Kaushik Sinha. Randomized partition trees for exact nearest neighbor search. In COLT, 2013.
S. Dasgupta and Kaushik Sinha. Randomized partition trees for nearest neighbor scarch. Algorithmica, 72: 237-263, 2014.
S. Dasgupta, Nave Frost, Michal Moshkovitz, and Cyrus Rashtchian. Explainable k-means and k-medians clustering. In ICML, 2020.
Mayur Datar, Nicole Immorlica, P. Indyk, and V. Mirrokni. Locality- hashing scheme based p-stable distributions. In SCG '04, 2004.
Yihe Dong, Piotr Indyk, Ilya Razenshteyn, and Tal Wagner. Learning space partitions for nearest neighbor search. In International Conference on Learning Representations, 2020. URL https://openreviee..ee ? kddrkeemErr.
Jordi Fonollosa. Gas sensor array under dynamic gas mixtures. httres//wwwr.kagggeee..//////ttr
gas arda--rr btt.yaaammigs--iiitteee.e.e
Pasi Fränti and Sami Sieranoja. K-means properties on six clustering benchmark datasets, 2018. URL http:
7/ss www..ef..e. wtt.ffisspddaaasseeeeee
Tiezhong Ge, Kaiming Hc, Q. Ke, and Jian Sun. Optimized product quantization. IEEE Transactions on Pollern Analysis and Machine Intelligence, 36:744 755, 2014.
A. Gionis, P. Indyk, and R. Motwani. Similarity search in high dimensions via hashing, In VLDB, 1999.
Kiana Hajebi, Yasin Abbasi- Yadkori Hossein Shahbazi, and H. Zhang. Fast approximate nearest-neighbor search with k-nearest neighbor graph. In IJCAI, 2011.
Ville Hyvönen, T. Pitkänen, S. Tasoulis, Elias Jaasaari, Risto Tuomainen, Liewu Wang, J. Corander, and T. Roos. Fast ncarest neighbor search through sparse random projections and voting. 2016 IEEE Interna- tional Conference Big Dota (Big Data), pp. 881-888, 2016.
P. Indyk and A. Naor. Nearest-neighies -oishbor----rsssnvin embeddings. ACM Trans. Algorithms, 3(3) cs, August 2007. ISSN 1549-6325. doi: 011145/127334012222 URT httppps//aa..rrr///111////////// 11tp///...1///23344.4.. 1273347
14

---

Published in Transactions on Machine Learning Research (03/2025)
H. Jégou, M. Douze, and C. Schmid. Product quantization for nearest neighbor search. IEEE Transactions Pollern Analysis and Machine Intelligence, 33:117-128, 2011.
Jeff Johnson, M. Douze, and H. Jégou. Sillion-scale similarity search with gpus. IEEE Transactions on Big Data, 7:535-547, 2021.
Kaggle. Comprehensive financial dataset: Nasdaq stocks, currency exchanges, and cryptos. https://www.
www...oooddaatttteee 2023. Accessed: 2025-01-15.
Norio Katayama and Satoh. The sr-tree: an index structure for high-dimensional nearest neighbor queries. In SIGMOD '97, 1997.
Omid Keivani and Kaushik Sinha. Random projection-based auxiliary information can improve tree-based near- est neighbor search. Information Sciences, 546:526 542, 2021. ISSN 0020-0255. doi: https://doo..or//1...000 j.ins.2020.60 08.04.. URL https://wwww htt////www.innndrrrettttttt cow htt.://cw..................////a
Neeraj Kumar, L. Zhang, and S. Nayar. What is good nearest neighbors algorithm for finding similar patches in images? In ECCV, 2008.
Dan Kushnir, Shirin Jalali, and Iraj Saniee. Towards clustering high-dimensional gaussian mixture clouds in linear running time. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics AISTATS, volume 89 of Proceedings of Machine Learning Research, pp. 1379-1387. PMLR, 16-18 Apr 2019.
Tom Leighton. Notes on better master theorems for divide-and-conquer recurrences. In Lecture notes, MIT, 1996.
Jinfeng Li, James Cheng, Fan Yang, Yuzhen Huang, Yunjian Zhao, Xiao Yan, and Ruihao Zhao. Losha: A general framework for scalable locality sensitive hashing. In Proceedings of the 40th International ACM SIGIR Conference Research and Development in Information Retrieval, pp. 635-644. ACM, 2017.
Ting Liu, A. Moore, Alexander G. Gray, and Ke Yang. An investigation of practical approximate nearest neighbor algorithms. In NIPS, 2004.
Mario Lucic, Matthew Faulkner, Andreas Krause, and Dan Feldman. Training gaussian mixture models scale via coresets. Journal of Machine Learning Research, 18(160):1-25 2018. URL http://jmlr... org/
papers/v18/15-506. 1htm
Yu A. Malkov and D. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 02:824-836, 2020.
Yury Malkov, Alexander Ponomarenko, A. Logvinov, and V. Krylov. Approximate nearest neighbor algorithm based on navigable small world graphs. Inf. Syst., 45:61-66 -68, 2014.
Mark McCartin-Lim, Andrew McGregor, and Rui Wang. Approximate principal direction trees. In Proceedings the 29th International Conference Machine Learning, ICML 2012, Edinburgh, Scotland, UK, June 26 Jull 2012. icml.ec / Omnipress, 2012. URL
p3tp:///2//ppppr/4...... .pdf
Marius Muja and D. Lowe. Fast approximate nearest neighbors with automatic algorithm configuration. VISAPP, 2009.
Y Ni, K Chu, and J Bradley. Detecting abuse at scale: Locality sensitive hashing at uber engineering, 2017.
Parikshit Ram and Kaushik Sinha. Revisiting kd-tree for nearest neighbor search. In Ankur Teredesai, Vipin Kumar, Ying Li, Rómer Rosales, Evimaria Terzi, and George Karypis (eds.), Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pp. org/ 11tp1/..114//222200.ooo 3330875
ACM, 2019a. doi: 10.1145/3292500.22 3330077.
URL https://aoi.
15

---

Published in Transactions on Machine Learning Research (03/2025)
Parikshit Ram and Kaushik Sinha. Revisiting kd-tree for nearest neighbor search. Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Dala Mining, 2019b.
Jason Rennie. 20 newsgroups dataset.
2016.
KEEL Dalaset Repository. Yearpredictionmssd dataset.
htt.://s..gggreekkke//tttaaeeeee smja. php?
cod=918 Accessed: 2025-01-15.
Kaushik Sinha. Lsh vs randomized partition trees: Which one to use for nearest neighbor search? 2014 13th International Conference on Machine Learning and Applications, pp. 41-46, 2014.
Kaushik Sinha. Fast 11-norm nearest neighbor search using simple variant of randomized partition tree. Tn INNS Conference on Big Data, 2015.
Kaushik Sinha and Omid Keivani. Sparse randomized partition trees for nearest neighbor search. In AISTATS, 2017.
R. Sproull. Refinements to nearest-neighbor searching ink-dimensional trees. Algorithmica, 6:579 589, 2005.
Yifang Sun, Wei Wang. Jianbin Qin, Ying Zhang, and Xuemin Lin. Sis: Solving c-approximate nearest neighbor queries in high dimensional euclidean space with a tiny index. Proc. VLDB Endow., 8:1 12, 2014.
Jeffrey K. Uhlmann. Satisfying general proximity / simillarity queries with metric trees. Information Processing Letters, 40(4):175-179, 1991. ISSN 0020-0190. doi: https://dbi..rrg/0000000,
00000/0000000000000000000000000) URL
https: http://wwww.cceneddeeeeeee. orw.aaaccc.....osseeee//////a/aa
Jan van Rijn. Bng spambase dataset.
2016.
Alvin Wan, Lisa Dunlap, Daniel Ho, Jihan Yin, Scott Lee, Suzanne Petryk, Sarah Adel Bargal, and Joseph E. Gonzalez. NBDT: neural-backed decision tree. In 9th International Conference on Learning Representaliins, ICLR 2021, Virtual Event, Austria, May 3- 7, 2021. OpenReview.nne, 2021. URL https://openrrevier net/ corooormmiiiieoooeeeeooooo VeLepppp
J. Wang, W. Liu, Sanjiv Kumar, and Chang. Learning to hash for indexing big data a survey. Proceedings of the IEEE, 104:34 57, 2016a.
Jingdong Wang, Heng Tao Shen, Jingkuan Song, and Jianqiu Ji. Hashing for similarity search: A survey. Arxin, abs/1 abs/1448.2999 2927, 2014.
Jun Wang, Wei Liu, Sanjiv Kumar, and Shih-Fu Chang. Learning to hash for indexing big data A survey. Proc. IEEE, 104(1):34-57, 2016b. doi: 10.100//PRO0::0152247777 URL https://aoi.org: 1109/ JPROC. 2487976
Xiang Wu, Ruiqi Guo, A. T. Suresh, Sanjiv Kumar, D. Holtmann-Rice, David Simcha, and F. Yu. Multiscale quantization for fast similarity search. In NIPS, 2017.
Yubao Wu, Ruoming Jin, and X. Zhang. Fast and unified local scarch for random walk based k-ncarest-ncighbor query in large graphs. Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, 2014.
16

---

Published in Transactions on Machine Learning Research (03/2025)
A Omitted Proofs
A.1 Proof of Lemma 3.1
Proof. Computing a single one dimensional projection takes time O(nd) and computing k-nearest neighbor graph can be done in time ((nk) after sorting the points in Onn logn) time. Note that this crucially depends on the fact that we perform one dimensional projection as nearest neighbors are determined by adjacent points on the real line. It computationally expensive to compute such a graph in arbitrary dimensions larger than 1. Finding the sparsest prefix cut after sorting is done in line 5 of Algorithm takes linear time once the k-nearest neighbor graph has been constructed. Overall, the runtime of each of the T procedures is Onn + n log + nk).
A.2 Proof of Lemma 3.2
Proof. The proof follows from the fact that if a cut does not respect the sorted ordering, then can switch two points in opposite parts of the cut to reduce the number of edges across the cut.
A.3 Proof of Lemma 3.4
Proof. Consider the computational cost of building ClusterTree tree. We claim that at every level of the tree, we do ( + n log + nk) work. To verify this, we note that en logg((n)) + (1 c)n log((1 - c)n S en log n + (1 - e)n log n = n logg.. n. Then from Assumption 3.3 there are O(logn) levels of the tree, leading to the stated runtime. (One can also use the Akra-Bazzi method to arrive at the same conclusion, see Akra
3.3
& Bazzi 1998) or Leighton 1996))
A.4 Proof of Lemma 3.6
Proof. Fix the dataset X. First note that for any fixed points x, y E X, we have
ElIP(= - y)1l = ||x y/1
since P is independent of X. Now for any x E X, the average distance squared from Pr to its k-nearest neighbors in PX is at most the average distance squared from Pr to the points that were originally its k-ncarest neighbors in X. This gives that apx I ax Finally, note that that the expected value of the sum of all pairwise distances after the projection is the same as the sum of all pairwise distances from our obsorvation above. This proves 3px = Bx, as desired.
A.5 Proof of Lemma 3.7
Proof. To prove Lemma 3.7 we will need the following auxiliary result.
Lemma A.1. Suppose N(1 Σn) and y ~ N(22, Eg) Then
B[[| y 1 |Im wzll + tr(Z1) + ir(E2).
Proof. Note that x-y is distributed N( 112 Σi - -2) and thus, y MI - 112 Az where N(, 1)
and A satisfies AAT = Ej + Eg. Thus,
|1 - y/12 = || - - + 2( - u2) Az Az + 2T AT Az.
Since E[2] = 0, have
E|||= y11 = |1 -221-22 E AT Az]
and
T -
22 (A A) (A' -
A) (AAA = = +Z))
Putting together the above calculations gives the desired result..
17

---

Published in Transactions on Machine Learning Research (03/2025)
Note that can upper bound ax by the expected distance squared between two points drawn form the same component. This is because the distance to the k-th nearest. neighbor from a fixed point will always be smaller than the distance to another point drawn from the same component (assuming our hypothesis that at least & points are drawn from each component). From Lemma A.1 it follows that ax S 2 max(tr(E1). tr(E2)).
To lower bound 0x, note that since min(w, 1 - w) 2(1), the expected distance squared between two uniformly random points is least asymptotically the expected distance squared between two points from separate components. Again using Lemma A.1 it follows that 3x D(llm) uall? + tr(E, + Σg)). ]
A.6 Proof of Lemma 3.8
Proof. Lemma 3.7 tells us that
ox ur(1 + E2)
1 2 c2
2
8x
| 12l
where we have used the fact that d(1((E) tr( for covariance matrix E E Rdxd
A.7 Proof of Lemma B.1
We first need the following auxiliary results from Indyk & Naor (007
Lemma A.2. Let x E Sd-1 and let P be random one-dimensional Gaussian projection.
Then for all
> 0,
Pr[[| - 1| 2 t) < exp(-t/88)
(1)
Pr[] < 1/t) < [
(2)
We now proceed with the proof of Lemma B.1
Proof. We first claim that the diameters and S' don't increase by a large factor after a random projection. Fix x, By Eq. equation 1 the probability that |P[( - y)ll increases by a factor of at most exp(-12/8). Thus for suitable constant c, we have that the probability [[P(xyv) log(1/e)) factor is at most e/(3[) Union bounding across all pairs in S and using similar argument for 5" gives that with probability at least 1 - 2e/3, have that diam(PS) S /log [S] diam(S) and diam(PS') I Vlog [S'] diam(S").
larger by a c( c [S|+
We now claim that the sets PS and PS' don't come 'too' close together. Indeed, take any point S and S". We have that ||x- v 2 d'S, Thus by Eq. equation 2 the probability that P( y) shrinks by a factor of (21/e) is at most O(e).
Altogethor, we know that with probability at least 1 - e, all three of the following events occur:
1. diam (Mam(PS) S Vlog |S| diam(S),
2. diam(PS') & Vlog |S diam(S'),
3. d(PS, PS') 2 c S") - diam - diammP5")
Thus by our assumption that S and S' are r-apart for the value of r in the lemma statement, it follows that
diam(PS) S Vlog SS diam(S) dPam(PS) diam(PS') S cd(S, S d(PS, PS')
and similar statement holds for S', proving the lemma.
18

---

Published in Transactions on Machine Learning Research (03/2025)
A.8 Proof of Lemma B.2
Proof. The proof follows from Lemma [..1 every point in PS will be closer to any other point in PS than any other point in PS'. A similar symmetric statement holds for PS'. Thus, any edges of the k-nearest neighbor graph starting from any point in PS must have its other vertex in PS as well. This implics that there is an empty cut between PS and PS", as desired.
Lemma A.3 (Follows from corollary 5 and 6 in Kushnir et al. (019))) ). Consider two c-separated Gaussian distributions in R with means μl, 42 and covariance matrices En and Σz. Define T(C, d) as in Lemma 3.9 Let 7 = 2d(c')² Amax/ /1/11 - pall? where Amax denotes the largest eigenvalue of the matric En + Ez. Then
lim T(d, 2Q(V7) d+000
B Hierarchical Clustering
In this section, we discuss the performance of ClusterTree for hierarchical clustering. Since our tree is designed to preserve the underlying cluster structure of the dataset, is very natural use for clustering applications, such hierarchical clustering. In hierarchical clustering, the goal is to design a tree over the input dataset which hopefully captures 'multi-scale' clustering relationships of the dataset.
To formalize this, we first define a natural hicrarchical clustering model and then prove results which suggest that ClusterTree is naturally suited to recover such a clustering. Note that traditional algorithms for hier- archical clustering, such as computing the minimum spanning tree, require 2(n²) time, which is prohibitive for large datasets, whereas ClusterTee construction is nearly linear time.
Definition B.1 (Hierarchical Clustering Model). Let be our dataset and P be a parameter. We assume there is a tree T over such that the following satisfied:
The leaves T are disjoint subsets of X of size at most some parameter P and together include all points of X,
Level 2 1 T
T is union of two subsets in level i of the tree where level O denotes the leaves. We assume that each subset at level i - contributes to eractly one subset in level i of the tree
The largest level of the tree is the entire dataset X.
Note that the above definition naturally describes a hierarchical clustering model over the dataset X where going up the tree indicates larger scale cluster structure over the dataset X. We further assume a separability critcria for our hicrarchical clustering model.
Definition B.2. Let dSam(S) denote the diameter of the subset S S X and d(S,S') denote the distance between two subsels S,S':
d(S,S)= min || yll. sES.veS'
We say that subsets S, are r-apart if
Cr Crmax(iiam()) diams") S d()
for some constant C',
If we assume the above definition applies to a pair of subsets of the tree T at any some fixed level, then intuitively we are requiring the two subsets constitute well separated clusters.
Given such an assumption, we want to argue that repeated application of Algorithm [ can successfully recover the underlying tree T. The intuition behind this that if the subsets are projected, they will also be separated after random projection with high probability. The following lemma shows that is indeed the case.
19

---

Published in Transactions on Machine Learning Research (03/2025)
Lemma B.1. Suppose subsets S and S' satisfy Definition B. with 2 Vlog(S + lse Let PS and PS' respeclively denole a random one-dimensional projection of the two subsets. Then with probability al least 1 e, we have
(aa d(PS,
for some constant c >> 1.
Lemma B.1 hints that with sufficient separability assumption, the k-nearest neighbor graph in one- dimension will mostly have edges within given cluster which leads to sparse cuts wetween different subsets. Thus, we can reasonably expect Algorithm [ to separate the distinct clusters in T since it optimizes for sparse cuts. Formally, we can prove the following statement.
Lemma B.2. Let S and S' be two r-apart subsels of dulasel X for the value of r in Lemma B.1 and P be a random one-dimensoo projection. If min([S), 2 k, then the k nearest neighbor graph of PS PS will have a cut that seporates PS and PS' with probability 1 ccc.
Now consider the hicrarchical clustering model given in Definition B.1 and let T denote the implicit tree over a dataset X. Consider a node of v of T and at some level let S and S' denote the subsets at level - that comprise v. If S and S' are r-apart for a sufficiently large value of r, then Lemma B.2 states that S and S' will have an empty cut between them after a random onc-dimensional projection. If we further assume that each of the two pieces of the k-nearest neighbor graph is connected, Algorithm will exactly split apart S and 5" intended in the tree T.
Preserving Cluster Structure of the Dataset. We empirically validate the hypothesis that ClusterTree is superior to RP trees in finding partitions that preserve the underlying cluster structure of the dataset. We designed two related experiments to demonstrate this. For the first set of experiments, we measured the diameter of the leaves (weighted by the leaf sizes) of each class of trees as the parameter P increases. Again the intuition here is that the diameter of the leaves are small, then it mostly contains points that are well-clustered together while conversely, the diameter large, then the tree has bucketed together points that belong to different clusters. Our results are shown in Figure [ Indeed, we see that for most datasets ClusterTree results in leaves that are much more tightly clustered than RP Trees, which again demonstrates that ClusterTree is adaptive the underlying cluster structure of the dataset.
We present additional experiments on how the weighted radius of leaves of various tree-based algorithms varies as function size in Figure 9 See Section 4 for more details on experimental setting. Overall, we see that ClusterTree has a smaller radius as a function of cluster size for the Gaussian Mixture, Spam, RNA, and KDD Cup datasets. Note that for Spam, 2-means tree was too costly to run and for Gaussian Mixture, the 2-means tree and ClusterTree have very identical curves for weighted radius as function of candidate size.
C Omitted Experimental Results
We give additional experimental results in this section.
Distance to k-th Nearest Neighbors. We created instances of ClusterTree and RP trees for all of our datasets where we set the leaf size, the parameter in Algorithm 2 to be equal to 10% of n. We then computed the distance from a query to the k-th ncarest neighbor among the candidates returned by a tree for various values of k and averaged this across all queries. The intuition here is that if a leaf node of a tree contains points from multiple distinct clusters, then there will be a substantial increase in this metric at some intermediate value of k. Indeod, this is what we observe in Figure 10 For example in the Gaussian Mixture, KDD Cup, and Spam datasets, there is a noticeable 'jump' in the plots for RP trees as it is 'mixing' multiple clusters in the leaf nodes while for ClusterTree, the relationship is much smoother.
To recap, the intuition here is that if a leaf node of a tree contains points from multiple distinct clusters, then there will be a substantial increase in this metric at some intermediate value of k. For example, suppose that the leaf of node contains points from two distinct well-separated clusters and consider query that
20

---

Published in Transactions on Machine Learning Research (03/2025)
Gaussian Mixture
Spam
100
20
Cluster Tree
90
Cluster Tree
RP Tree
5.0
Tree
Weighted Redius
Weighted Rard us
Cluster
60
3.5
RP Tree
18
50
2.5
17
20
2000
4000
6000
10000
2000
2500
3000 3500 4000
4500
5000
750 1000
1500 1750 2000
Candidate Size
Candidate Size
Candidate
RNA
SIFT
35
Cluster
KDO Cup
Weighted Rodlus
700
690
RP Tree
deigghtdd Radius
25
RP Tree
Veeigh sigted Radlus
6000
Cluster Tree
RP Tree
660
5000
670
20
4000
660
15-
3000
10
2000
640
1000
630
250
500
750 1000 1250 1500 1750
2000
500
1000
1500
2000
1000
2000
3000
4000
5000
Candidate Size
Candidate Size
Candidate Size
Figure 8: The leaves of ClusterTree have a smaller diameter than those of RP Trees.
Gaussian Mixture
5.5
Spam
News
100
20
Tree
RP Tree
19
Weightted Radius
2. McManns Tree
4.5
Weighted Radius
18
70
17.
Tree
3.0
PCA Tree
Cluster
RP Tree
30
2-Means Tree
2.0
2000
4000
6000
8000
10000
2000
2500
3000 3500 4000 Candidate Size
4500
5000
750 1000
2000
Candidate Size
Candidate Size
RNA
KDD Cup
700
Cluster Tree
Cluster
Weighted Radius
100
PCA Tree
2-Means Tree
Weighted Radius
12000
10000
RP Trea
2-Means Tree
80
Tree
600
Weighted
8000
6000
Ouster Tree
550
RP Tree
40
4000
2-Means Tree
2000
PCA Tree
1000 1250 1500 1750 2000 Candidate Size
1000
1500
2000
1000
2000
3000
4000
5000
Candidate Size
Candidate Size
Figure Expanded version of Figure using all tree-based algorithms.
lands in this leaf but is closer to only of the clusters. Then for large enough value of k, the k-th nearest neighbor for this query would come from the far away cluster, leading to significant increase in the distance to the k-th nearest neighbor in comparison to the (k 1)-th nearest neighbor. In contrast, if the leaf mostly contained points from one cluster, the distance would smoothly increase. To summarize, this is exactly the behaviour observed Figure 10 the Gaussian Mixture, KDD Cup, and Spam datasots, there is a noticeable 'jump' in the plots for RP trees as it is 'mixing' multiple clusters the leaf nodes while for ClusterTree, the relationship much smoother.
21

---

Published in Transactions on Machine Learning Research (03/2025)
Gaussian Mixture
Cluster Tree
0.14
Cluster Tree
13.8
RP Tree
13.5
Distance kean
0.12
Distance k.nn
0.10
13.0
8
0.08
12.8
0.06
Cluster
12.2
0.04
RP Tree
100
20
50
80
100
200
300
400
500
600
SIFT
12
Spam
KDD CUP
Cluster Tree
Cluster Tree
380
RP Tree
RP Tree
250
RP Tree
Distance konn
Distance to kenth
200
340
to
150
320
300
100
280
2
50
260
0
100
200
300
400
500
600
100
200
300
400
500
600
100
200
300
400
500
600
k
k
k
Figure 10: ClusterTree has a smoother trade-off curve for distance to the k-th neighbor as increases.
Additional Parameter Selection Details. If there are multiple cuts that have conductance 0, i.e., multiple separated pieces in the k-nearest neighbor graph constructed in Algorithm [ we pick the cut that is the most balanced. This because any choice the cuts would have been good with respect to preserving near neighbors so we should optimize for keeping the tree balanced.
Note that there have been recent works improving RP trees using additional techniques such sparse random projections (Sinha & Keivani 2017), using auxiliary information when performing search over the tree (Keivani & Sinha, 2021). and other methods (Hyvönen et al. 2016). For simplicity, we did not use these techniques as they can be used identically for ClusterTree as for RP trees.
Finally, we highlight that both RP tree and ClusterTree are randomized algorithus. Therefore, they have the following additional benefit: order to boost accuracy, we can initialize multiple instances of the data structure to create an ensemble of trees while keeping the overall number of candidates fixed. For example, instead of creating make a constant number of trees, this can be thought of as significantly boosting accuracy by increasing the amount of space used by only a constant factor. Note that 2-means trees and PCA trees are deterministic so they do not have this additional benefit. For simplicity however, we only compare single instantiation of each algorithm.
tree with leaf size P, we create two trees with leaf sizes P/2 cach. In general, if we
D Justifications for Assumption 3.3
We provide justification for Assumption 3.3 as its conditions hold true for onc-dimensional datascts with very different structural properties: both uniform and clustered inputs.
Suppose the input Algorithm is a set of uniformly spaced points one- dimensions. Then is clear that the with the lowest conductance will split the dataset exactly in half due to symmetry.
Uniform Points:
Clustered Points: Suppose the input consists of two well-soparated clusters, with each cluster consisting of least c-fraction of the total input size. Then the k-nearest neighbor graph for this input will be such that the edges of each cluster will be mostly to other points of the same cluster.
22

---

Published in Transactions on Machine Learning Research (03/2025)
Thus, the cut separating the two clusters will be extremely sparse and hence have low conductance as well. See Figure 1 for an example.
Average Split Ratio. We now empirically validate Assumption 3.3 To do so, we compute ClusterTree for of our datasets setting Algorithm 2 are shown in Table
5% of the size the dataset in each case. The results across one run of We observe that on average, each node of the tree splits the dataset into
two approximately balanced parts.
Dataset
Avg. Split Ratio
Dataset Spam
Avg. Split Ratio
KDD Cup
(.496)
0.50(0.27)
News
0.50(0.00)
SIFT
0.49(0.18)
RNA
0.45(0.29)
Gaussian Mixture
0.53(0.12)
Table The average split ratio across all nodes in the tree with standard deviation in the perenthesis using 5% of the number of points as the parameter P (leaf size).
E
Additional Datasets
We provide additional experiments for comparison between RP-trees and ClusterTree on set of additional data sets: two clustering benchmark data sets from Fränti Sieranoja 2018). 8776x13, 10126x15, Gas
sensor data set 120kx128 [Fonollosa, ) stocks 94701x6 (Kaggle 2023), mediamill 43907x120 Repository
skyserver Ahhumada el al. 2020) 500Kx11.
clust dim13
DitSooooow15
gas
1.0
Cluster Tree
1.NN Accuray
0.9-
Accuracy
I-N Accuracy
0.90
0.8
0.8
0.97
0.7
0.7
0.96
0.6
0.95
Cluster Tree
Cluster Tree
RP Tree
Tree
0.5
500
1000
1500
2000 2500 3000 3500
500
1000 1500 2000 2500 3000 3500 4000 Candidate Size
1000
2000
3000
4000
5000
6000
Candi date Size
Candidate Size
0.98
stocks standard
1.00
Cluster Tree Thee
mediamil
Cluster Tree RP
Skyserver
0.97
RP Tiee
0.95
1-NN Accuracy
1-NN Accuracy
0.85
0.95
0.85
0.80
0.80
0.93
0.75
0.75
0.92
0.70
0.65
1000
3,000
4000
5000
7500
5000
Candidate
Candidate
Candidate
Figure 11: Candidate Size vs 1-NN Error for ClusterTree and RP tree.
23

---

Published in Transactions on Machine Learning Research (03/2025)
dim13
clust d15
Sensor data
1.0
0.98
Cluster free
0.9
RP
10 10.NN Accurcy
Accuracy
0.8-
10-WN Accuracy
0.8-
0.7
0.94
0.7
3.66
Cluster Tree
Cluster Tree
Tree
0.4
0.90
1000
2000
1000
Candidate
Candidate Size
stocks standard
mediamill
Skyserver
0.96
0.85
Cluster Tree
RP Tree
10-NN Accuracy
0.94
Accuracy
10-NN Accuracy
0.80
0.8
0.65
0.86
Cluster Tree
RP Tree
0.60
1000
4000
5000
6009
2500
5000
7500 10000 12500 15000 17500
1000
2000
3000
5000
6:00
Candidate Size
Candidate Size
Candidate Size
Figure 12: Candidate Size vs 10-NN Error for ClusterTree and RP tree.
F Additional Running- Time Accleration Analysis
Accel.
factor max
CLTree bucket size
CTTree Acc. diff
PCATree
diff
Comments
Dataset
min
max
max
min
max
GMM
x1.12
x1.35
11180
17676
0.55
0.69
0.52
0.56
SPAM
x1.15
x2.7
3 10a
5 x 10*
0.9980
0.9985
0.9968
0.9975
News
NA
NA
NA
NA
1.0
1.0
0.9
0.95
shared values
RNA
2.45
2.49
0.99
0.99
0.12
0.17
KDD Cup
1965
200
0.61
0.93
Table 4: ClusterTree PCATree query rumning- time acceleration min and max values for 10-NN.
Accel.
CLTree bucket size
ClTree Acc. diff
KMsTrre diff
Comments
Dataset
min
max
max
min
max
max
GMM
NA
NA
NA
NA
NA
NA
NA
NA
no shared y and x values
SPAM
x1.15
x2.7
3x 10a
5 x
10*
0.9980
0.9985
0.9968
0.9975
News
NA
NA
NA
NA
1.0
1.0
0.44
0.15
shared values
RNA
NA
NA
NA
NA
0.98
0.96
0.15
0.05
shared y values
KDD Cup
NA
NA
NA
NA
0.60
0.86
0.07
0.18
shared y values
Table 5: ClusterTree vs. KMEANsTree query running-ting acceleration min and max values for 10-NN.
24


Reviews:
[{"review_id": "8PMpGLCHVZ", "reviewer": "Reviewer_K1CX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n- Simple yet effective algorithm to build a tree structure based on clustering\n- Algorithm offers strong theoretical guarantees\n- Experimental results support such theoretical claims in real world settings\n\nWeaknesses\n\n- The similarity search area has heavily been explored. The work mainly focuses on a narrow sub-area.\n- It's unclear how competitive is this sub-area vs. new product quantization variants, graph-based solutions, etc. \n- Missing baselines outside of the sub-area\n- Missing datasets (there are dozens of datasets)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper provides a comprehensive exploration of tree-based algorithms for Nearest Neighbor Search (NNS), focusing on the limitations of random partition (RP) trees, one of the most widely studied methods in this area. While RP trees are valued for their theoretical guarantees and practical performance, they lack adaptability to the structure of input datasets. To address this, the authors propose ClusterTree, a novel tree-based algorithm that combines the randomness of RP trees with a clustering-aware approach to create well-balanced and meaningful partitions. Through both theoretical analysis and empirical evaluations on real-world datasets, the paper demonstrates that ClusterTree outperforms RP trees and other tree-based methods, offering superior accuracy and better preservation of the underlying cluster structure.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The main concern has to do with the weak experimental evaluation. The paper mainly focus in this subarea. Unclear where the method stands (and this area in general) vs. strong quantization and graph-based solution. PQ outperforms most hash-based solutions, so someone wonders if outside of the nice theoretical contributions, these methods are not competitive in practice.\n\nMore datasets should also be used. Modern studies present results in dozens of datasets\n\nLi, Wen, et al. \"Approximate nearest neighbor search on high dimensional data—experiments, analyses, and improvement.\" IEEE Transactions on Knowledge and Data Engineering 32.8 (2019): 1475-1488.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "io08hWIBdz", "reviewer": "Reviewer_2srD", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The task that the article considers (ANN search) is important. The proposed method seems to improve performance of RP trees on the clustered data sets. The technical quality of the article is good. Theoretical guarantees are provided.\n\nWeaknesses: I disagree with the way the contribution of the article is formulated. The authors state as their contribution that they introduce a novel data structure called ClusterTree. However, ClusterTree is just a RP tree that uses a different split criterion instead of the median (or a uniformly random point from the midquartile range) of the projections (and tries multiple projection directions). As I outline above in Summary of Contributions, a clearer way of formulating the contribution of the article would be to state that it proposes a novel split criterion for RP trees. I do not think that every slight variation of an existing and established data structure should be named as a new data structure.\n\nSpecifically, hyperplane trees (see, e.g., Hyvönen 2023, p.15–18), such as RP trees, PCA trees, and $k$-d trees, first project the node points onto a line, and then split the node points by a hyperplane that is orthogonal to this line. Thus, there are two components in which the hyperplane trees can differ from each other: (1) a _projection vector_ $z \\in \\mathbb{R}^d$ that defines the line onto which the node points are projected and thus the orientation of the splitting hyperplane; (2) a _split criterion_ that defines the location of the splitting hyperplane given the projected node points.\n\nThe main novelty of the article on the second of these components (in addition, a method for selecting the projection vector among multiple candidates is proposed). In addition to being conceptually clearer, outlining the contribution as a novel split criterion would enable applying it immediately to the other hyperplane trees, such as $k$-d trees or PCA trees. Also there is very little systematic work studying split criteria of space partition trees, so this would make the article a more valuable contribution to literature.\n\nThe article is missing ablation experiments. Two related techniques for improving RP trees are proposed: (a) selecting a split point as a graph cut that minimizes graph conductance; (b) selecting the projection vector (among randomly generated candidates) whose optimal cut minimizes graph conductance. Experiments should be performed to show what is the performance improvement (over the original RP trees) of (a) alone; and (a) and (b) combined. \n\nThe results of the article are far away from the current state-of-the-art for approximate nearest neighbor search (see e.g., Aumüller et al., 2020 or https://github.com/erikbern/ann-benchmarks for a performance comparison of the current SOTA methods). However, improving tree-based ANN search may be of interest to at least some of TMLR's audience, so I do not see an issue with that.\n\nMartin Aumüller, Erik Bernhardsson, and Alexander Faithfull. ANN-benchmarks: A benchmarking\ntool for approximate nearest neighbor algorithms. _Information Systems_, 87:101374, 2020.\n\nVille Hyvönen: _A machine learning approach to approximate nearest neighbor search_. PhD dissertation, University of Helsinki, 2023.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The article considers the task approximate nearest neighbor (ANN) search, specifically partition-based methods for ANN search. The article improves the widely applied random projection (RP) tree data structure by making it more adapted to the cluster structure of the data. In particular, the authors propose a novel split criterion RP trees. Instead of splitting at the median of the projected node points, the authors propose building a one-dimensional $k$-nn graph of the node points, and splitting so that graph conductance, i.e., the normalized (by the smaller of the sums of the degrees of the nodes of two groups resulting from the split) number of cut edges is minimized. In addition, the authors propose a technique of trying multiple randomly chosen projection directions, and selecting one whose best split (selected via the method described above) minimizes the graph conductance. \n\nThe experimental results demonstrate that when defeatist search (a point is selected into the candidate set if and only if it belongs to the same leaf as the query point) is used to select the candidate set, on the data sets that have a cluster structure the proposed method outperforms the original RP tree that uses the median split. The authors also provide a theoretical guarantee in the special case where the data is from the well-separated Gaussian mixture model.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I have two requests that I describe in more detail above in Strengths and Weaknesses section. These are critical for securing my recommendation:\n* Outline the contribution of the article as a new split criterion for RP trees instead of a new type of data structure.\n* Perform the ablation experiment described above.", "broader_impact_concerns": "I do not find any unaddressed ethical concerns with the paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "FhP5lIMlaK", "reviewer": "Reviewer_ZSdM", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n1. Well-written paper, I enjoyed reading it. The authors laid out the main ideas nicely.\n2. Through theoretical analysis. The authors provided theoretical analysis for (a) runtime complexity (b) guarantees on nearest neighbours (c) analysis on hierarchical clustering\n3. The paper is accompanied with empirical results that demonstrates stronger performance.\n\n**Weakness**\n1. The assumptions are restricted. Data distribution has to be a mixture of 2 Gaussians.\n2. Lack of a runtime flop analysis. The exact compute overhead is still unclear.\n3. On that point, a similar table can be provided for run-time complexities of the ClusterTree and the baselines.\n4. Potential missing cases where there are multiple such clusters, would ClusterTree still outperform random partition/PCA trees?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces ClusterTree, a novel tree-based algorithm for nearest neighbor search that combines random projections with adaptation to dataset structure. The key innovation is modifying the traditional Random Partition tree approach by incorporating cluster-aware partitioning based on graph conductance minimization in 1D projected space. The authors demonstrate both theoretical guarantees and practical improvements over existing methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Here are my suggestions in addition to the weakness section (critical issues):\n\n1. Make better use of the \\cite and \\citep. Some references are put in the wrong format.\n2. Section 4 doesn't seem to adhere to the same topic. You might wanna consider (a) move it to appendix (b) explain why that matters -> add some experiments for that as well.\n\nOverall I think the paper is interesting and offers a novel solution to the nearest neighbor search problem.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper makes a clear technical contribution for a well defined problem, and detailed theoretical and empirical evaluation is provided for validating the claims. The reviewers found the contribution somewhat incremental and straightforward, but overall it is a solid contribution for the field that meets the TMLR evaluation criteria. All comments on writing and technical content were addressed during the discussion.
Decision: Accept (poster)