## A True O n ( log n ) Algorithm for the All-k-Nearest-Neighbors Problem

Hengzhao Ma 1 and Jianzhong Li 2

1 hzma@stu.hit.edu.cn 2 lijzh@hit.edu.cn

Harbin Institute of Technology, Harbin, Heilongjiang 150001, China

Abstract. In this paper we examined an algorithm for the All-k-NearestNeighbor problem proposed in 1980s, which was claimed to have an O n ( log n ) upper bound on the running time. We find the algorithm actually exceeds the so claimed upper bound, and prove that it has an Ω n ( 2 ) lower bound on the time complexity. Besides, we propose a new algorithm that truly achieves the O n ( log n ) bound. Detailed and rigorous theoretical proofs are provided to show the proposed algorithm runs exactly in O n ( log n ) time.

Keywords: Computation Geometry · All k-Nearest-Neighbors

## 1 Introduction

The All-k-Nearest-Neighbors problem, or All-kNN for short, is an important problem that draws intensive research efforts. Early works about All-kNN date back to 1980s [6], and there are still some new results about this problem published in recent years [16,17]. The reason why the All-kNN problem has been continuously studied is that many applications invoke All-kNN as an important sub-procedure, such as classification [18], agglomerative clustering [10], image retrieval [24], recommendation systems [13], and outlier detection [3]. For many of these applications, solving All-kNN is reported as the main bottleneck [10].

The All-kNN problem can be briefly defined as follows. Let ( X,D ) be a metric space, where D , ( · · ) is a distance function and X is a point set. The input of All-kNN is a point set P ⊆ X , and the output is the k -nearest-neighbor for all points p ∈ P , where the k -nearest-neighbor of a point p is a set of k points in P that are closest to p according to the distance function D , ( · · ). The formal definition will be given in Section 2.

There is an obvious brute-force solution for All-kNN, which is to compute the pairwise distances for all points in P , and select the k points with smallest distance to p for each point p . This solution takes O n ( 2 ) time, which is unacceptable when the size n of the input is large. There have been a lot of algorithms proposed to efficiently solve the All-kNN problem, which can be categorized into the following three classes.

The first class of algorithms uses different techniques to accelerate the empirical running time of the algorithm, while the theoretical O n ( 2 ) upper bound

is unchanged. There are basically three different kinds of techniques. The first kind is based on tree-like spacial indexes, such as k d -trees [11] and Voronoi diagram [9] based index. The second kind is based on space filling curves, including Hilbert curve [12] and Z-order curves [15]. The space filling curve is a useful method to build an one-dimensional index on multidimensional data. There is an important property about the index based on the space filling curves, that is, the elements near to each other tend to be indexed into near entries. This property helps to reduce the number of distance computation to solve the AllkNN problem, as reported in [7,17,25]. The third kind is based on the idea of neighborhood propagation , which uses the intuition that the neighbors of neighbors are also likely to be neighbors. The NN-descent algorithm proposed in [8] is seminal work on neighborhood propagation, and it is still one of the best algorithms for All-kNN problem. Other works use the neighborhood propagation technique to refine the primary result returned by some preprocessing step. For example, the authors of [22] use a multiple random divide and conquer approach as preprocessing, and the Locality Sensitive Hashing is used in [28].

The second class of algorithms turns to solve the problem on parallel systems. The theoretical work [4] states that there is an optimal solution for All-kNN which needs O (log n ) time and O n ( ) processors on CREW PRAM model. Other works tries to solve All-kNN on different parallel platforms, such as MapReduce platform [23,19] and GPU environment [14].

Different from the most algorithms in the above two classes which do not reduce the theoretical O n ( 2 ) upper bound on running time, the fourth class of algorithms is proved to have lower upper bounds. And they are all serial algorithms, different with the work in [4]. For example, Bentley gives an multidimensional divide-and-conquer framework that can sole the All-kNN problem in O n ( (log n ) d -1 ) time [2], where d is the number of dimension. Besides, the algorithm given in [6] takes O n ( (log δ )) time, where δ is the ratio of the maximum and minimum distance between any two points in the input. Finally, the algorithm proposed by Vaidya [21] is claimed to have upper bound of O kd n ( d log n ) on the running time.

After all, it can be summarized that most of the works about the All-kNN problem focus on improving the empirical running time of the algorithms, but few of them succeed in reducing the O n ( 2 ) worst case upper bound. To the best of our knowledge, the algorithms proposed by [2,6,21] are the only ones that have lower upper bound that O n ( 2 ). We will not consider the parallel situation so that the work in [4] is excluded. Unfortunately, it has been as long as 30 years since the theoretical results are published. There is an urgent demand to renew and improve these historical results, and that is exactly the main work in this paper.

Among the three theoretical works, the one proposed by Vaidya [21] has the best upper bound on n , which is O kd n ( d log n ). We have carefully examined the algorithm and the proofs in [21], and unfortunately a major mistake is found, which is that some part of the algorithm proposed in [21] actually exceeds the O n ( log n ) bound. Since the work has been cited over 300 times combined with

the conference version [20], it is necessary to point out the mistake and fix it. Here the contributions of this paper are listed as follows.

- 1. We point out that the algorithm proposed in [21] needs Ω n ( 2 ) + kd n d log n time, contradicting with the claimed O n ( log n ) upper bound.
- 2. A modified algorithm is proposed whose running time is proved to be upbounded by O k k ( ( + ( √ d ) d ) · n log n ). The algorithm only applies to the Euclidean space.
- 3. While the algorithm proposed in [21] is designed for All-1NN and needs nontrivial modifications to generalize to All-kNN, the algorithm in this paper can directly solve the All-kNN problem for arbitrary integral value of k .

The rest of the paper is organized as follows. In Section 2 the definition of the problem and some prerequisite knowledge are introduced. Then the algorithm proposed in [21] is described and analyzed in Section 3. The modified algorithm is proposed in Section 4, and the correctness and the upper bound on running time is formally proved in Section 5. Finally we conclude the paper in Section 6.

## 2 Problem Definitions and Preliminaries

The problem studied in this paper is the All-k-Nearest-Neighbors problem under Euclidean Space. In the following discussions we will assume that the input is a set P of points where each p ∈ P is a d-dimensional vector ( p (1) , p (2) , · · · , p ( d ) ). The distance between two points p and p ′ is measured by the Euclidean dis- tance, which is D p, p ( ′ ) = √ d ∑ i =1 ( p ( ) i -p ′ ( ) i ) 2 . The formal definition of the Allk-Nearest-Neighbors problem is given below.

Definition 2.1 (k-NN). Given the input point set P ⊆ R d and a query point q ∈ R d , define kNN q,P ( ) to be the set of k points in P that are nearest to q . Formally,

- 1. kNN q,P ( ) ⊆ P , and | kNN q,P ( ) | = k ;
- 2. D p, q ( ) ≤ D p , q ( ′ ) for ∀ p ∈ kNN q,P ( ) and ∀ p ′ ∈ P \ kNN q,P ( ) .

Definition 2.2 (All-k-Nearest-Neighbors, All-kNN). Given the input point set P ⊆ R d , find kNN p,P ( \ { p } ) for all p ∈ P .

There is an equivalent definition for the All-kNN problem, that is the k -NN graph construction problem whose definition is given below. The k -NN graph is intuitively the graph representation of the result of All-kNN problem. In the rest of the paper we will use All-kNN to refer to the problem.

Definition 2.3 (kNN-graph). Given the input point set P ⊆ R d , the kNNgraph for P is a directed graph G = ( V, E ) satisfying:

$$1. \, V = P ;$$

## 2. For any two points p , p 1 2 ∈ V , ( p , p 1 2 ) ∈ E iff p 2 ∈ kNN p ,P ( 1 \ { p 1 } ) .

Define a rectangle r in R d to be the product of d intervals, i.e., I 1 × I 2 ×···× I d , where each interval I i can be open, closed or semi-closed for 1 ≤ i ≤ d . For a rectangle r , let Lmax ( ) r , Lmin ( ) r be the longest and shortest length of the intervals defining r , respectively. When Lmax ( ) = r Lmin ( ), r r is called a d-cube, and denote the side length of the d-cube r as Len ( ) = r Lmax ( ) = r Lmin ( ). For r a point set P , r is called the bounding rectangle if r is the smallest rectangle containing all the points in P , then let | r | to be equivalent to | P | that is the number of points in P . Besides, a d-cube r is a Minimal Cubical Rectangle (MCR) for a given point set P iff r contains all the points in P and has the minimal side length. Note that for a specific point set P , its bounding rectangle is unique but its MCR may not.

On the other hand, define a d-ball to be the set B c, r ( ) = { x ∈ R d | D x,c ( ) ≤ r } , where c is the center and r is the radius of the d-ball. For a point set P , define the Minimum Enclosing Ball (MEB) of P to be the minimum radius ball containing all the points in P , denoted as MEB P ( ). It is known that the there exists one unique MEB P ( ) for a given P , which can be computed by solving a quadratic-programming problem [26]. From now on let C P and R P denote the unique center and radius of MEB P ( ) respectively. Besides the exact MEB, the approximate MEB is equally useful and easier to compute. A d-ball B c ( P , r P ) is an /epsilon1 -MEB of a point set P iff P ⊆ B c ( P , r P ) and r P ≤ /epsilon1 · R P . The following algorithm can compute an 3 2 -MEB for a given set P in linear time, which is proposed in [27].

## Algorithm 1: Compute 3 -MEB

```
algorithm can compute an 3-MEB for a given set P in linear time, which is
proposed in [27].

| Algorithm 1: Compute 3-MEB
| Input: B(cP, rP) which is a 3-MEB of P, and another point set Q
| Output: a 3-MEB of P \cup Q
| If (cP, rP) == Null then
| 2
| |   c0 \leftarrow a random point in Q;
| 3
| |   r0 \leftarrow 0;
| 4
| else
| 5
| |   c0 \leftarrow cP, r0 \leftarrow rp;
| 6
| end
| while \exists q \in Q do
| 8
| |   if d(q, c0) > r0 then
| 9
| |      \left |   \delta \leftarrow \frac { 1 } { 2 } ( D ( q, c0) - r0);
| 10
| |      r1 \leftarrow r0 + \delta;
| 11
| |      c1 \leftarrow c0 + \frac { 8 } { D ( q, c0) } ( q - c0);
| 12
| |      c0 \leftarrow c1, r0 \leftarrow r1;
| 13
| end
| |   P \leftarrow P \cup \{ q \}, Q \leftarrow Q \left \{ q \} ;
| end
|
| The main characteristic of Algorithm 1 is that it can be viewed as a dynamic
| algorithm, where the 3-MEB of P is precomputed, and the set Q is an update to
```

The main characteristic of Algorithm 1 is that it can be viewed as a dynamic algorithm, where the 3 2 -MEB of P is precomputed, and the set Q is an update to

P . The algorithm runs in O Q ( | | ) time to compute the 3 2 -MEB of P ∪ Q based on the precomputed 3 2 -MEB of P . This characteristic will play an important part in the algorithm proposed in Section 4.

## 3 The Algorithm in [21] and analysis of it

In this section we cite the outlines of the algorithm proposed in [21], and give the analysis why this algorithm is not an O n ( log n ) algorithm. Note that the algorithm focuses on the situation that k = 1. The generalization to k &gt; 1 is non-trivial but the author did not give the generalized algorithm in detail in [21]. This is a disadvantage of the algorithm, as was pointed out in Section 1.

## 3.1 The algorithm

The algorithm mainly consists of two parts, i.e., building the Cube Split Tree, and maintain the Nbr and Frd sets for each node in the cube split tree. The definitions of the Cube Split Tree, Nbr and Frd sets are given in the discussions below.

The Cube Split Tree. Given the input point set P , the algorithm will start from the MCR of P , split it into a set of d-cubes, and organize the d-cubes into a tree structure, which is called the Cube Split Tree (CST). Let Succ ( ) r denote the set of the sub-rectangles generated by splitting r , then the CST can be defined as follows.

Definition 3.1 (Cube Split Tree, CST). Given a point set P , a CST based on P is a tree structure T satisfying the following properties:

- 1. the root of T is MCR P ( ) ,
- 2. each of the nodes of T represents a d-cube, which is an MCR of a subset of P , and

Besides, T is called fully built if all the leaf nodes contains only one point.

- 3. there is an edge between r and each r ′ ∈ Succ ( ) r .

The structure of the CST is determined by the method to split a rectangle r and generate Succ ( ). Now we introduce the method described in [21]. Given r a d-cube r , let α ( ) denote the geometric center of r r . Then let h i ( ) denote the r hyperplane passing through α ( ) r and orthogonal to the i -th coordinate axis, 1 ≤ i ≤ d . The d hyperplanes divide r into 2 d cells. Discard the cells containing no points, shrink the non-empty cells to MCR's and Succ ( ) r is obtained. The following lemma shows the property of the CST constructed by using the above split method. The detailed proof can be found in [21].

Lemma 3.1 ([21]). Given a point set P where | P | = n , the CST T built based on P has the following properties:

- 1. there are at most 2 n d-cubes in T , and
- 2. the total time to conduct the above split method and build a fully-built CST is O (2 d n log n ) .

The Nbr and Frd sets. For each rectangle r in the CST T , two sets Nbr ( ) r and Frd ( ) will be maintained, whose definitions are given below. r

For any two rectangles r and r ′ in the CST T , define D max ( ) r , D min ( r , r ′ ) , D max ( r , r ′ ) as follows:

$$D _ { m a x } ( \mathfrak { r } ) & = \max _ { p, p ^ { \prime } \in \mathfrak { r } } \{ D ( p, p ^ { \prime } ) \} \\ \omega & = \nu \quad \varepsilon \quad \varepsilon \quad \varepsilon \quad \varepsilon$$

$$D _ { m i n } ( \mathfrak { r }, \mathfrak { r } ^ { \prime } ) & = \min _ { p \in \mathfrak { r }, p ^ { \prime } \in \mathfrak { r } ^ { \prime } } \{ D ( p, p ^ { \prime } ) \} \\ \psi \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu$$

$$D _ { \max } ( \mathfrak { r }, \mathfrak { r } ^ { \prime } ) = \max _ { p \in \mathfrak { r }, p ^ { \prime } \in \mathfrak { r } ^ { \prime } } \{ D ( p, p ^ { \prime } ) \} \\ \dots \cdots \cdots \cdots$$

Then define Est ( ) by the following equation: r

$$E s t ( \mathfrak { r } ) = \begin{cases} D _ { m a x } ( \mathfrak { r } ), & i f \left | \mathfrak { r } \right | \geq 2 \\ \min _ { \mathfrak { r } ^ { \prime } \in T } \{ D _ { m a x } ( \mathfrak { r }, \mathfrak { r } ^ { \prime } ) \}, & o t h e r w i s e \end{cases} ( 1 ) \\ \ t h e \text{ definitions of the } N h r \text{ and } F r d \text{ sets can be given using the denotes.}$$

Now the definitions of the Nbr and Frd sets can be given using the denotations above.

Definition 3.2. Nbr ( ) = r { r ′ ∈ T | D min ( r , r ′ ) ≤ Est ( ) r } .

Definition 3.3. Frd ( ) = r { r ′ ∈ T | r ∈ Nbr ( r ′ ) } .

The algorithm will ensure that kNN p,P ( \ { p } ) ⊆ Nbr ( ) for r ∀ p ∈ r . When the algorithm terminates and each rectangle r contains only one point, there will be Nbr ( ) = r kNN p,P ( \ { p } ) where p is the only one point in r .

The following two lemma shows the size of Nbr and Frd sets maintained for each rectangle in the CST T .

$$\text{Lemma $3.2$ ([21])}. \, | N b r ( \mathfrak { r } ) | \leq 2 ^ { d } ( 2 d + 3 ) ^ { d }, \, \text{for $\forall \mathfrak { r } \in T$}. \\ \text{$- \quad \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \,$- \quad \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot\cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cd.$$

$$\text{Lemma $3.3$ ([21])}. \, | F r d ( \mathfrak { r } ) | \leq 1 2 ^ { d } + 2 ^ { d } ( 8 d + 3 ) ^ { d }, \, f o r \, \forall \mathfrak { r } \in T.$$

The overall algorithm. Now we are ready to give the overall algorithm proposed in [21]. The pseudo codes are divided into the main procedure and the MntnNbrFrd sub-procedure.

## Algorithm 2: The algorithm

Input: A point set P

Output: The result of All-kNN

- 1 r 0 ← MCR P ( ), Nbr ( r 0 ) ←∅ , Frd ( r 0 ) ←∅ S ← { , r 0 } ;
- 2 Create a tree rooted at r 0 ;
- 3 while |S| ≤ | P | do
- 5 Split r and generates Succ ( ); r
- 4 r ← the rectangle in S that has the largest volume;
- 6 MntnNbrFrd( r , Succ ( ) r ) ;
- 7 S ← S \ { } ∪ r Succ ( ); r
- 8 end

## Algorithm 3: The MntnNbrFrd sub-procedure

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00159v2-figure-4449bc28-9378-4f0e-976e-fbc62b56d04a.jpg)

It can be deduced from Algorithm 3 that when the MntnNbrFrd subprocedure is invoked, there are at most 2 | Succ ( ) ( r | | Succ ( ) + r | | Nbr ( ) + r | | Frd ( )) r | additions to the Nbr and Frd sets. On the other hand, the while loop in Algorithm 2 is executed for at most 2 n times, because there are at most 2 n d-cubes in the CST T and each execution of the while loop visits at least one d-cube in T . And thus the MntnNbrFrd sub-procedure is invoked for at most 2 n times. Combing with Lemma 3.2 and 3.3, the following lemma can be easily proved.

Lemma 3.4 ([21]). The total time to maintain the Nbr and Frd sets, which is the total time to execute Algorithm 3, is O d ( d · n ) .

## 3.2 Analysis of Algorithm 2

The total time to execute Algorithm 2 can be divided into three parts, i.e., the time to conduct the split method and build the split tree, the time to maintain the Nbr and Frd sets, and the time to maintain the Est value for each d-cube. The former two parts are already solved by Lemma 3.1 and 3.4. For the last part, the author of [21] claims that the total time to maintain the Est value is O n ( ), but this is impossible. The following lemma shows the impossibility.

Lemma 3.5. The time to create and maintain the Est ( ) r value for all r in the CST T is Ω n ( 2 ) .

Proof. We recite the definition of Est ( ) here, where r

$$E s t ( \mathfrak { r } ) = \begin{cases} D _ { m a x } ( \mathfrak { r } ), & i f \left | \mathfrak { r } \right | \geq 2 \\ \min _ { \mathfrak { r } ^ { \prime } \in N b r ( \mathfrak { r } ) } \{ D _ { m a x } ( \mathfrak { r }, \mathfrak { r } ^ { \prime } ) \}, & o t h e r w i s e \end{cases}$$

Please pay attention to the first term. When | r | ≥ 2, Est ( ) r is defined by Est ( ) r = D max ( ), r where D max ( ) r = max p ,p 1 2 ∈ r D p , p ( 1 2 ). We assure that this is the original definition in [21]. According to this definition, it will exceed the O n ( log n ) bound merely to compute Est ( r 0 ), where r 0 is the MCR of the input point set P . Actually, it needs Θ n ( 2 ) time to compute Est ( r 0 ), because it needs to compute the pairwise distance between each pair of points in P , and there are obviously n n ( -1) 2 pairs. Then the time to compute Est ( ) for all r r in the CST T is obviously Ω n ( 2 ). /intersectionsq /unionsq

Finally, we give the following theorem stating a lower bound of the time complexity of Algorithm 2, contradicting with the analysis given in [21].

Theorem 3.1. An lower bound of the time complexity of Algorithm 2 is Ω n ( 2 ) .

## 4 The algorithm in this paper

According to the analysis in Section 3.2, the main defect of Algorithm 2 is that the Est value defined in Equation 1 can not be efficiently computed. In this section we propose our algorithm that solves this problem elegantly.

The algorithm is divided into tree parts, which will be introduced one by one in the rest of this section.

## 4.1 Constructing the Rectangle Split Tree

The first part of our algorithm is to build the Rectangle Split Tree (RST), which is very similar to the algorithm for building the CST. There are several differences between the two algorithms. First, our algorithm represents the subsets of the input point set P by bounding rectangles, rather than MCR's. Second, each time when a rectangle r is chosen, it is split into two sub-rectangles by cutting the longest edge of r into two equal halves. Let r large denote the one in the two sub-rectangles of r that contains more points, and r small denotes the other. The Rectangle Split Tree is defined in the following Definition 4.1.

Definition 4.1 (Rectangle Split Tree, RST). Given a point set P , a RST based on P is a tree structure satisfying:

- 1. the root of T is the bounding rectangle of P ,

- 2. each node in T represents a rectangle, which is the bounding rectangle of a subset of P , and
- 3. there is an edge from r to r large and r small .

Besides, T is called fully built if all the leaf nodes contain only one point.

Next we give the algorithm to build the RST. The complexity of Algorithm 4 will be proved to be O dn ( log n ) in Section 5.

```
        Next we give the algorithm to build the RST. The complexity of Algorithm
        will be proved to be O(dn log n) in Section 5.
        Algorithm 4: Constructing the RST
        Input: a point set P, and the bounding rectangular t_P of P
        Output: an RST T
        Create a tree T rooted at t_P;
        S_0 <- {t}, S_1 <- 0;
        while |S_1| < |P| do
            |                                                                                                                                                                                                        
        |                                                                                                                                                                                               
            |
```

## 4.2 Computing the Approximate MEB

## Algorithm 5: Compute the approximate MES

```
                                                                                                                                                                                                       
    Algorithm  5: Compute the approximate MES                                                                                                                                                                                                       

    Input: a RST T
```

The second part of the proposed algorithm is to compute the approximate MES for each node in the RST, which is given as Algorithm 5. This algorithm receives the constructed RST T as input, and traverse T with post-root order, where Algorithm 1 will be invoked at each node. It will be shown in Section 5 that the algorithm takes O dn ( log n ) time.

## 4.3 Computing All-kNN

Based on the algorithm for constructing the RST and computing MES, the algorithm for All-kNN is given as Algorithm 6. It is worthy to point out that the algorithm naturally applies to all integer k ≥ 1, which is an advantage against Algorithm 2.

The algorithm first invoke Algorithm 4 on P to construct an RST T (Line 1) . Then Algorithm 5 is invoked at Line 2 to compute the approximate MES for each node in T . The rest of the algorithm aims to traverse T and construct kNbr ( ) and r kFrd ( ) sets for each r r ∈ T . The formal definition of the two sets along with two auxiliary definitions are given below. In these definitions, assume that a set H of rectangles is given, and the approximate MES ( c , r r r ) of each r ∈ H is precomputed.

Definition 4.2. Given two rectangles r and r ′ ∈ H , define the relative quality of r ′ against r as follows:

$$Q l t y ( \mathfrak { r } ^ { \prime }, \mathfrak { r } ) = \sqrt { ( D ( c _ { \mathfrak { r } ^ { \prime } }, c _ { \mathfrak { r } } ) + \frac { 1 } { 2 } r _ { \mathfrak { r } ^ { \prime } } ) ^ { 2 } + r _ { \mathfrak { r } ^ { \prime } } ^ { 2 } } \\.. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \.$$

Definition 4.3. Let min k { x ∈ S | f ( x ) } be the k-th smallest value in the set { x ∈ S | f ( x ) } . Define kThres ( ) r for each r ∈ H as follow:

$$\ k T h r e s ( \mathfrak { r } ) = \begin{cases} 2 \cdot r _ { \mathfrak { r } }, & i f | \mathfrak { r } | \geq k + 1 \\ \min _ { k } \{ \mathfrak { r } ^ { \prime } \in H \, \subset \{ \mathfrak { r } \} \, | \, Q l t y ( \mathfrak { r } ^ { \prime }, \mathfrak { r } ) \}, & i f | \mathfrak { r } | < k + 1 \end{cases} ( 2 )$$

Definition 4.4. kNbr ( ) = r { r ′ ∈ H | D c ( r ′ , c r ) ≤ r r + r r ′ + kThres ( ) r } .

Definition 4.5. kFrd ( ) = r { r ′ ∈ H | r ∈ kNbr ( r ′ ) } .

Next we describe how Algorithm 6 works to construct the desired kNbr and kFrd sets.

The algorithm will visit all the rectangles in the RST T by a descending order on the radius of the approximate MES. To do so, a heap H is maintained to store the rectangles in T ordered by the radius of the approximate MES of them. The main part of Algorithm 6 is a While loop. Each time the While loop is executed, the top element r of H , which is the one with the largest approximate MES radius, will be popped out of H . Then the algorithm will determine the S son set, push all the rectangles in S son into H and process the rectangles in S son by invoking the MntnNbrFrd process (Algorithm 7) . The While loop will terminate when | H | = | P | and that is when all the rectangles in T are processed.

The set S son is determined by the following criterion. First, S son is set to be { r large , r small } . Then, if any r i ∈ S son satisfies | r i | &lt; k + 1, r i will be replaced by the set of the leaf nodes in the subtree of T rooted at r i . Such work is done by Line 9 to Line 16 in Algorithm 6.

## Algorithm 6: All-kNN

- Input: a point set P Output: All-kNN on P 1 Invoke Algorithm 4 on P , and construct an RST T ; 2 Invoke ComputeMES( root T ( ) ) where root T ( ) is the root of T ; 3 kNbr root T ( ( )) = ∅ , kF rd root T ( ( )) = ∅ ; 4 Initialize a heap H = { root T ( ) } , which is order by the radius of the approximate MES; 5 while | H &lt; P | | | do 6 r ← H.pop (); 7 S son ←{ r large , r small } ; 8 foreach r i ∈ S son do 9 if | r i | &lt; k +1 then 10 S leaf ← the set of the leaf nodes in the subtree rooted at r i ; 11 S ← S son \ { r i } ∪ S leaf ; 12 Delete the non-leaf nodes in the sub-tree; 13 Hang the leaf nodes directly under r ; 14 end 15 Push r i into H ; 16 end 17 MntnNbrFrd( r , S son ) ; 18 end

After the S son is determined, Algorithm 6 invokes the MntnNbrFrm process to construct the kNbr and kFrd sets for each r i ∈ S son . Though the algorithm is named the same with Algorithm 3, they actually work very differently. Algorithm 7 relies on four sub-procedures, which are AddInNbr , DelFromNbr , DelFromFrd and TruncateNbr , respectively. The name of these sub-procedures intuitively shows their functionality, and the pseudo codes are given in Algorithm 8. Back to the MntnNbrFrd process, Algorithm 7 conducts the following four steps.

Step 1. In Lines 2 to 7, the algorithm iterates over kNbr ( ). r For each r ′ ∈ kNbr ( ), r r will be deleted from kFrd ( r ′ ) since r is split and replaced by S son . Then the algorithm invokes the AddInNbr sub-procedure to try to add r ′ into kNbr ( r i ) for each r i ∈ S son . It can be seen from the pseudo codes of the AddInNbr sub-procedure that if r ′ is added into kNbr ( r i ) then r i will be added into kFrd ( r ′ ).

Step 2. In Lines 8 to 13, the algorithm iterates over kFrd ( ). r For each r ′ ∈ kFrd ( ), the algorithm will delete r r from kNbr ( r ′ ) and invoke AddInNbr to try to add each r i ∈ S son into kNbr ( r ′ ).

Step 3. In Lines 14 to 18, the algorithm iterates over S son . For each r i ∈ S son , the AddInNbr sub-procedure will be invoked to try adding each rectangle r j ∈ S son \ { r i } into kNbr ( r i ).

Step 4. In Lines 19 to 23, the TruncateNbr sub-procedure is invoked on each r ′ ∈ S son ∪ kFrd ( ) where r | r ′ | = 1. The word truncate indicates that it will delete a section of kNbr ( ), as will be explained next. r

## Algorithm 7: The MntnNbrFrd process

```
                                                                                                                                                                                                       
                                                                                                                                                                                                       

                                                                                                                                                                                                        }
                                                                                                                                                                                                      

                                                                                                                                                                                                       }

                                                                                                                                                                                                       }                                                                                                                                                                                                        |
                                                                                                                                                                                                       |                                                                                                                                                                                                        <?>                                                                                                                                                                                                        </?>
```

Algorithm 8 shows the functionalities of the sub-procedures mentioned in Algorithm 7, including DelFromNbr DelFromFrd AddInNbr , , and TruncateNbr . Among them, the AddInNbr sub-procedure needs to be explained in more details. It can be seen that an extra set Cand ( ) r is used in the special case of | r | = 1, which stores the candidate rectangles that might contain the k-NN of the only point in r . The Cand set is formally defined as follows.

Definition 4.6. The Cand ( ) r set maintained for r where | r | = 1 , is a set satisfies:

- 1. Cand ( ) r ⊆ kNbr ( ) r ,
- 3. Qlty ( r ′ , r ) ≤ Qlty ( r ′′ , r ) for ∀ r ′ ∈ Cand ( ) r and ∀ r ′′ ∈ kNbr ( ) r .
- 2. | Cand ( ) r | = k , and

Recall that kThres ( ) is r defined to be min k { r ′ ∈ H \ { } | r Qlty ( r ′ , r ) } when | r | &lt; k + 1. And then with Cand ( ) r defined, kThres ( ) r can be equivalently defined as max r ′ ∈ Cand ( r ) { Qlty ( r ′ , r ) } , as is shown at Line 15 in Algorithm 8.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00159v2-figure-c3b83427-3107-4229-89c2-4c90be4b3fdb.jpg)

Last but not least, these sub-procedures above require the kNbr , kFrd and Cand sets to be stored in specific data structures. The requirements and the data structures are discussed below.

- 1. The data structure for the kNbr sets should support insertion and deletion both efficiently, and it should be an ordered set to support the TruncateNbr procedure. It is possible to use a B+ tree to support such operations efficiently. It is known that insertion and deletion of B+ tree takes O (log n ) time. For the operation of truncating, it is also possible to delete a section of elements in B+ tree in O (log n ) amortized time, regardless of the number of elements deleted. Besides, the TruncateNbr sub-procedure requires the

elements r ′ ∈ kNbr ( ) being ordered by the value of r D c , c ( ′ r r ) -r r ′ . Because only such ordering can ensure the truncating operation would delete each rectangle r ′ that satisfies D c ( r ′ , c r ) &gt; r r ′ + r r + kThres ( ) r and keep the kNbr ( ) set conforming to its definition. r

- 2. The operations on kFrd sets include insertion and deletion by specific key. It is appropriate to implement it by red-black trees, which takes O (log n ) time for both insertion and deletion. There is no specific requirement on how to order the elements r ′ ∈ kFrd ( ), r and an natural choice is to use r r ′ as the key to order them.
- 3. For the Cand set, the operations on it include pushing, popping, and finding the maximum value. Thus it can be implemented by a heap, and the elements r ′ ∈ Cand ( ) should be ordered by r Qlty ( r ′ , r ).

The correctness and complexities of the above proposed algorithms will be proved in the next section.

## 5 Analysis

## 5.1 Correctness

Lemma 5.1. Each time when the while loop begins, Algorithm 6 ensures the following two invariants:

- 1. kNbr ( ) r ⊆ H and kFrd ( ) r ⊆ H for ∀ r ∈ H , and
- 2. if r ′ ∈ kNbr ( ) r , then r ∈ kFrd ( r ′ ) , for ∀ r , r ′ ∈ H .

Proof. We prove the two statements by induction on the while loop.

Before the work-flow goes into the while loop, H contains only the root of T , and kNbr root T ( ( )) = kFrd root T ( ( )) = ∅ . Then it can be easily verified that the two statements in the lemma are true at this time.

As induction hypothesis, suppose that the two statements are true before the i -th execution of the while loop starts. The while loop body only changes the kNbr ( r ′ ) and kFrd ( r ′ ) sets of r ′ ∈ kNbr ( ) r ∪ kFrd ( ) r ∪ S son , where r is the top element of H . First we consider the rectangles r ′ ∈ kNbr ( ) r ∪ kFrd ( ) r . It can be seen that r is popped out of H (Line 6), and r is deleted from kNbr ( r ′ ) and kFrd ( r ′ ) (Line 3 and 9). This operation does not violate the first statement. On the other and, the boxes in S son are pushed into H , so adding r i ∈ S son into kNbr ( r ′ ) or kFrd ( r ′ ) does not violate the first statement. Thus the first statement holds for ∀ r ′ ∈ kNbr ( ) r ∪ kFrd ( ). Then for r ∀ r i ∈ S son , the rectangles in kNbr ( r i ) ∪ kFrd ( r i ) are either inherited from kNbr ( ) r ∪ kFrd ( ), r which are subsets of H according to the induction hypothesis, or other rectangles in S son that are added into H in this while loop. Thus the first statement holds for r i ∈ S son . Since the execution of the while loop does not influence the kNbr and kFrd sets of other rectangles, we arrive at the conclusion that the first statement holds for ∀ r ∈ H before the next while loop starts.

The second statement is ensured by the AddInNbr and TruncateNbr subprocedures. It can be seen that adding (deleting) r into kNbr ( r ′ ) always appears

along with adding (or deleting) r ′ into kFrd ( ). Thus the second statement can r be easily proved to be true. /intersectionsq /unionsq

Lemma 5.2. The kNbr ( ) r , kFrd ( ) r and Cand ( ) r sets constructed in Algorithm 8 meets their definition which are given in Definition 4.4, 4.5 and 4.6.

Proof. We write this as a lemma to ensure the rigorousness of the whole proof. Actually it can be easily verified and thus the proof is omitted.

Lemma 5.3 ([1]). Given a point set P ⊆ R d whose MEB is B ( C P , R P ) , then for any point q ∈ R d , there exists a point p ∈ P such that D q, p ( ) ≤ √ D q, ( C P ) 2 + R 2 P .

Proof. The proof can be found in [1].

Lemma 5.4. Given a point set P ⊆ R d along with its 3 2 -MEB B c ( P , r P ) , then for any point q ∈ R d , there exists a point p ∈ P such that D q, p ( ) ≤ √ ( D q, c ( P ) + 1 2 r P ) 2 + r 2 P .

Proof. Since B c ( P , r P ) is the 3 2 -MEB of P , we have R P ≤ r P ≤ 3 2 R P , where R P is the radius of the exact MEB of P . Pick a point p 0 such that D ( C P , p 0 ) = R P (such point definitely exists), then

$$D ( c _ { P }, \mathcal { C } _ { P } ) \leq D ( c _ { P }, p _ { 0 } ) - D ( p _ { 0 }, \mathcal { C } _ { P } ) \leq r _ { P } - \mathcal { R } _ { P } \leq \frac { 1 } { 2 } \mathcal { R } _ { P } \leq \frac { 1 } { 2 } r _ { P }.$$

Thus,

$$\varepsilon, \\ D ( q, \mathcal { C } _ { P } ) \leq D ( q, c _ { P } ) + D ( c _ { P }, \mathcal { C } _ { P } ) \leq D ( q, c _ { P } ) + \frac { 1 } { 2 } r _ { P }.$$

Now just choose the point p stated in Lemma 5.3, we have

$$D ( q, p ) & \leq \sqrt { D ( q, \mathcal { C } _ { P } ) ^ { 2 } + \mathcal { R } _ { P } ^ { 2 } } \leq \sqrt { ( D ( q, c _ { P } ) + \frac { 1 } { 2 } r _ { P } ) ^ { 2 } + r _ { P } ^ { 2 } }. \\ \intertext { a m a t i n d } \tilde { \varkappa } \tilde { \varkappa } \tilde { \varkappa } \tilde { \varkappa } \tilde { \varkappa } \tilde { \varkappa } \tilde { \varkappa } \tilde { \varkappa } \tilde { \varkappa } \tilde { \varkappa } \tilde { \varkappa } \tilde { \varkappa } \tilde { \varkappa } \tilde { \varkappa } \tilde { \varkappa } \tilde { \varkappa } \tilde { \varkappa } \tilde { \varkappa } \tilde { \varkappa } \tilde { \varkappa } \tilde { \varkappa } \tilde { \varkappa } \tilde { \varkappa }.$$

Lemma 5.5. For any point p ∈ P , define T k ( p ) = max p ′ ∈ kNN p,P ( \{ p } ) { D p, p ( ′ ) } . Then T k ( p ) ≤ kThres ( ) r holds for any p ∈ r .

Proof. The proof considers the non-leaf nodes and leaf nodes separately.

For a non-leaf node r , the number of points inside r is at least k +1 since the rectangles containing fewer points are already deleted by Line 12. On the other side, kThres ( ) is r set to 2 r r according to Equation 2. Note that for any point p ∈ r , the distance from p ′ ∈ r \ { p } to p is at most 2 R ≤ r 2 r r . Then it can be deduced that there is at least k +1 points within the range of kThres ( ) around r p . Since there is exactly k points within the range of T k ( p ) around p , we get the conclusion that T k ( p ) ≤ kThres ( ) for a non-leaf node r r and ∀ p ∈ r .

For a leaf node r , first there is only one point c r ∈ r . According to Lemma 5.4, there exist a point p ′ ∈ r ′ at a distance of at most √ ( D c ( r ′ , c r ) 2 + 1 2 r r ′ ) + r 2 r ′ from c r for each rectangle r ′ ∈ kNbr ( ). Note that this is exactly the r Qlty ( r ′ , r )

defined in Definition 4.2. According to Definition 4.6 for the Cand ( ) r set, it stores the k rectangles with the smallest Qlty ( r ′ , r ) value. Equivalently, there exists at least k points in Cand ( ). r On the other hand, there are exactly k points within the range of T k ( p ) around p . Thus it is easy to see that T k ( p ) ≤ max r ′ { Qlty ( r ′ , r ) } = kThres ( ), where r r is a leaf node and p = c r is the only point in r . /intersectionsq /unionsq

Lemma 5.6. kNN p,P ( \{ } p ) ⊆ { }∪ r kNbr ( ) r for any rectangle r ∈ T and any point p ∈ r .

Proof. Given an arbitrary rectangle r ∈ T and an arbitrary point p ∈ r , the following proofs applies to an arbitrary point q ∈ kNN p,P ( \ { p } ). First we have D q, p ( ) ≤ T k ( p ) since q is one of the k-NN's of p . If q ∈ r then the lemma trivially holds. Otherwise p lies in another rectangle r ′ , which indicates that D q, c ( r ′ ) ≤ r r ′ . On the other hand, D p, c ( r ) ≤ r r since p ∈ r . Thus, the following inequality can be derived based on the triangle inequality and Lemma 5.5:

D c , c ( r r ′ ) ≤ D c , p ( r )+ D p, q ( )+ D q, c ( r ′ ) ≤ r r + T k ( p )+ r r ′ ≤ r r + kThres ( )+ r r r ′ .

This inequality indicates that r ′ ∈ kNbr ( ) according to Definition 4.4. r Finally, it can be concluded that kNN p,P ( \ { p } ) ⊆ { } ∪ r kNbr ( ) since the r point p is arbitrary in kNN p,P ( \ { p } ). /intersectionsq /unionsq

By now we have proved that Cand ( ) and r kNN p,P ( \ { p } ) are both subsets of kNbr ( ). r Next we will show that the three sets collapse to the same one when Algorithm 6 terminates, which fulfills the proof of the correctness of the algorithm that it can correctly compute kNN p,P ( \ { p } ) for all point p ∈ P . This

Lemma 5.7. Let r to be a leaf node in T , then all r ′ ∈ kNbr ( ) r \ Cand ( ) r are non-leaf nodes.

Proof. Recall the definitions of kNbr and Cand sets in Definition 4.4 and 4.6. Suppose to the contrary that there exists r ′ ∈ kNbr ( ) r \ Cand ( ) and r r ′ is a leaf node that contains only one point. In such case, Qlty ( r ′ , r ) = D c ( r ′ , c r ) since r r ′ = 0. Then Qlty ( r ′ , r ) = D c ( r ′ , c r ) &gt; kThres ( ) r because r ′ / Cand ∈ ( ). r On the other hand, D c ( r ′ , c r ) ≤ r r ′ + r r + kThres ( ) r according to r ′ ∈ kNbr ( ) r and the definition of kNbr ( ). r Further, the last inequality can be simplified to D c ( r ′ , c r ) ≤ kThres ( ) since r r r = r r ′ = 0. Thus, we get D c ( r ′ , c r ) ≤ kThres ( ) r &lt; D c ( r ′ , c r ), which is a contradiction. Finally, it is proved that r ′ is a non-leaf node.

Theorem 5.1. When Algorithm 6 terminates, kNbr ( ) = r Cand ( ) = r kNN p,P ( \ { p } ) holds for any leaf node r , where p = c r is the only point in r .

Proof. When Algorithm 6 terminates, all rectangles contains only one point, which indicates that r r = 0 for all r . In such case, Qlty ( r ′ , r ) is simplified to the form of D c ( r ′ , c r ). And then it can be verified that the definition of Cand ( ) is r simplified to the same form with kNN c ,P ( r \{ c r } ). On the other hand, Lemma

5.2 ensures that the Cand ( ) set constructed in the algorithm meets its definition, r then Cand ( ) = r kNN c ,P ( r \ { c r } ) is proved.

Lemma 5.7 shows all r in kNbr ( ) r \ Cand ( ) r are non-leaf nodes. Since all r ∈ H are leaf nodes when Algorithm 6 terminates, and Lemma 5.1 shows that kNbr ( ) r ⊆ H , there will be kNbr ( ) r \ Cand ( ) = r ∅ which is equivalent to kNbr ( ) = r Cand ( ). r

After all, it is proved that kNbr ( ) = r Cand ( ) = r kNN c ,P ( r \ { c r } ), i.e., the three sets collapse to the same one. /intersectionsq /unionsq

## 5.2 Complexities

## 5.2.1 Complexity of Algorithm 4

Lemma 5.8. There are at most 2 n nodes in the RST T .

Proof. The construction of T indicates that T is binary but may not be a full binary tree. It is a known result that a full binary tree with n leaf nodes contains 2 n -1 nodes, and thus the number of nodes in T is no more than 2 n . /intersectionsq /unionsq

Definition 5.1. Given a RST T and any r ∈ T , call r large and r small as the larger and smaller son of r , respectively. Then define lsa ( ) r (lowest smaller ancestor) for r as follows. Let P be the path from r to the root of T . If all the rectangles in P are the larger son of its farther, then lsa ( ) r is the root. Otherwise lsa ( ) r is the lowest rectangle in P that is the smaller son of its parent.

Lemma 5.9 ([21]). For any r in the RST T , the process of splitting r into r large and r small can be done in O d ( · | r small | · (1 + log | lsa ( ) r | +log | r small | )) time.

Lemma 5.10 ([21]). Let w ( ) = r d · | r small | · (1+log | lsa ( ) r | +log | r small | ) . Then ∑ r ∈ T w ( ) = r O dn ( log n ) .

The detailed proof of Lemma 5.9 and 5.10 can be found in [21]. And the following lemma can be directly deduced by the above two lemmas.

Theorem 5.2. The time complexity of Algorithm 4 is O dn ( log n ) .

## 5.2.2 Complexity of Algorithm 5

Theorem 5.3. The time complexity of Algorithm 5 is O dn ( log n ) .

Proof. According to Algorithm 5, the time to compute the 3 2 -MES of any rectangle r is O d ( | r small | ), which is strictly less than w ( ). r Then The complexity of Algorithm 5 can be expressed by r O ( r small ). Since Lemma 5.10 shows that

∑ r ∈ T w ( ) r ≤ O dn ( log n ), it rithm 5 is O dn ( log n ).

∑ ∈ T | | can be concluded that the time complexity of Algo/intersectionsq /unionsq

## 5.2.3 Complexity of Algorithm 6

Lemma 5.11. For any point set P , let r be the bounding rectangle of P , and let B ( C P , R P ) be the MES of P , then Lmax ( ) r ≤ 2 · R P ≤ √ d · Lmax ( ) r , where Lmax ( ) r is the length of the longest side of r .

Proof. Let r c be an MCR of P .It is easy to see that √ dLmax is the length of the longest diagonal of r c . Thus the diameter of the circumscribed d-ball of r c is exactly √ dLmax . Since it is a enclosing ball and B ( C P , R P ) is the minimum enclosing ball, we have 2 R P ≤ √ dLmax .

For the other side of the inequality, suppose to the contrary that 2 R P &lt; Lmax ( ). Let r p and p ′ be the pair of points that are farthest to each other in P , then D p, p ( ′ ) ≥ Lmax ( ) since otherwise r r would not be the bounding rectangle of P . Thus 2 R P &lt; Lmax ( ) r ≤ D p, p ( ′ ) and the d-ball with a diameter of 2 R P can not enclose both p and p ′ . This conflicts with the definition of MES. And thus Lmax ( ) r ≤ 2 R P is proved.

Lemma 5.12. For any point set P , let r be the bounding rectangle of P , and c r and r r be the center and radius of the 3 2 -MES of P , then Lmax ( ) r ≤ 2 · r r ≤ 3 2 √ d · Lmax ( ) r .

Proof. This lemma can be easily proved by combing Lemma 5.11 and the definition of the 3 2 -MES. /intersectionsq /unionsq

Now we introduce two denotations for the following proofs.

Definition 5.2 ( P ( ) r , the parent rectangle). Given a rectangle r in the RST T , let P ( ) r be the rectangle at the parent node of r . If r is the root then P ( ) = r r .

Definition 5.3 ( O ( ) r , the outer rectangle). Given a rectangle r in the RST T , define O ( ) r recursively as follows. If r is the root of T then O ( ) r is the minimal d-cube that contains r . For non root r , recall that when P ( ) r is split, it is split by cutting the longest side of it into two equal halves. This split in the meantime split O P ( ( )) r into two rectangles. Then let O ( ) r be the one that contains r .

Lemma 5.13. Lmin O ( ( )) r ≥ 1 2 · Lmax P ( ( )) r .

Proof. This lemma is an imitation of Lemma 4.1 in [5], and thus the lemma can be proved using similar techniques. The details are omitted. /intersectionsq /unionsq

Lemma 5.14. For any rectangle r ∈ H in the execution of Algorithm 6, there exists a set S of d-cubes that satisfies:

- 1. S can be mapped to kNbr ( ) r one-to-one,
- 2. Len ( r ′ ) ≥ 1 √ d r r top holds for ∀ r ′ ∈ S , where r top is the top element of H , and
- 3. the rectangles in S are disjoint.

Proof. For each r ′ ∈ kNbr ( ), r it is true that Lmin O ( ( r ′ )) ≥ 1 2 Lmax P ( ( r ′ )) according to Lemma 5.13. Then by Lemma 5.11 we have Lmax P ( ( r ′ )) ≥ 2 √ d r P ( r ′ ) . On the other hand, r P ( r ′ ) ≥ r r top since r top is the current element in H and P ( ) was popped out of r H before r top . In summary, Lmin O ( ( r ′ )) ≥ 1 √ d · r r top for ∀ r ′ ∈ kNbr ( ). Thus, r O ( r ′ ) contains a d-cube with side length 1 √ d · r r top . Besides, it is easy to see that for arbitrary r ′ and r ′′ in kNbr ( ), r O ( r ′ ) and O ( r ′′ ) are disjoint.

Based on the above analysis, the mapping f from kNbr ( ) to r S is as follows: for each r ∈ kNbr ( ), r f ( r ′ ) is the d-cube contained in O ( r ′ ) and with side length 1 √ d · r r top described above. It can be verified that such S satisfies the properties required in the lemma. /intersectionsq /unionsq

Lemma 5.15. During the executions of Algorithm 5, | kNbr ( ) r | = ( √ d ) d holds for all non leaf node r .

Proof. For a non leaf node r , kNbr ( ) is defined to be the set of r

$$\{ \mathfrak { r } ^ { \prime } \in H \ | \ D ( c _ { \mathfrak { r } ^ { \prime } } + c _ { \mathfrak { r } } ) \leq r _ { \mathfrak { r } ^ { \prime } } + r _ { \mathfrak { r } } + k T h r e s ( \mathfrak { r } ) \},$$

where kThres ( ) = 2 r r r . Since r ∈ H and kNbr ( ) r ⊆ H , we have r r ≤ r r top and r r ′ ≤ r r top , where r top is the top element in H . Thus it can be deduced that

$$\ k N b r ( \mathfrak { r } ) \subseteq \{ \mathfrak { r } ^ { \prime } \in H \ | \ D ( c _ { \mathfrak { r } ^ { \prime } }, c _ { \mathfrak { r } } ) \leq 4 \cdot r _ { \mathfrak { r } _ { t o p } } \}.$$

Now let S ′ = { r ′ ∈ H | D c ( r ′ , c r ) ≤ 4 · r r top } . To establish the connections between S ′ and the size of kNbr ( ), r the idea is to enclose S ′ with a d-cube r outer , and divide r outer into small d-cubes with side length 1 √ d r r top , and then Lemma 5.14 can be used to derive the size of kNbr ( ). r

Let c r to be the center of r ourter , it can be verified that then the side length of r outer should be at least 10 r r top to enclose S .

Lemma 5.16. During the executions of Algorithm 5, | kFrd ( ) r | = O ( √ d ) d holds for all non-leaf node ∀ r .

On the other hand, Lemma 5.14 shows that each r ′ ∈ kNbr ( ) can be mapped r to a d-cube with side length 1 √ d r r top . Since the side length of r outer is 10 r r top , r outer contains at most (10 √ d ) d small d-cubes with side length of 1 √ d r r top . Considering the one-to-one mapping between the d-cubes with side length 1 √ d r r top and the rectangles in kNbr ( ), r it can be deduced that kNbr ( ) r ≤ (10 √ d ) d = O (( √ d ) d ) /intersectionsq /unionsq

Proof. There is a similar lemma given in [21]. The detailed proof can be found in that paper and is omitted here. /intersectionsq /unionsq

Theorem 5.4. The time complexity of Algorithm 6 is O k k ( ( +( √ d ) d ) · n log n ) .

Proof. The time to execute Algorithm 6 consists of the following four parts: (1) the time to invoke Algorithm 4, (2) the time to invoke Algorithm 5, (3) the

time to manipulate the heap H , and (4) the time to execute Algorithm 7. The former two parts are already proved to be O dn ( log n ) in Theorem 5.2 and 5.3. According to Lemma 5.8 there are at most 2 n nodes in the RST T , so that | H | ≤ 2 n . And thus the time to manipulate the heap H is O n ( log n ).

In the rest of the proof we deal with the last part of the time complexity. First we introduce some denotations for ease of discussion. Let Df , Dn Ad , and Tr to be the time to execute the DelFromFrd , DelFromNbr , AddInNbr and TruncateNbr sub-procedures respectively. Under these denotations, the time complexity of Algorithm 7 can be expressed as follows:

$$| k N b r | ( D f + | \mathcal { S } _ { s o n } | \cdot A d ) + | k F r d | ( D n + | \mathcal { S } _ { s o n } \cdot A d ) + | \mathcal { S } _ { s o n } | ^ { 2 } \cdot A d + ( | \mathcal { S } _ { s o n } | + | k F r d | ) \cdot T r \\........................................................................................................................................................................................................$$

According to Lemma 5.15 and 5.16, | kNbr ( ) r | and | kFrd ( ) r | are only bounded for non-leaf nodes. However, it can be verified that the MntnNbrFrd procedure will not be invoked on leaf nodes. Thus, the | kNbr | and | kFrd | term can be safely up-bounded by O (( √ d ) d ).

It is already mentioned in the last part of Section 4.3 that kNbr , kFrd and Cand sets should be implemented by specific kind of data structures. By such implementation, DelFromNbr and TruncateNbr take O (log | kNbr | ) time, AddInNbr take O (log | Cand | +log | kNbr | ) time, and DelFromFrd takes O (log | kFrd | ) time. Since these sub-procedures may be invoked on leaf nodes, and the only available bound on | kNbr | and | kFrd | for leaf nodes is O n ( ), then the Df , Dn , Tr can be replaced by O (log n ), and Ad can be replaced by O (log k +log n ).

Since S son ≤ k +1, Equation 3 is up-bounded by the following term:

which is O ((( k ( √ d ) d ) + ( k +1) )log 2 n ).

$$( \sqrt { d } ) ^ { d } ( \log n + ( k + 1 ) \log n ) \times 2 + ( k + 1 ) ^ { 2 } \log n + ( k + 1 + ( \sqrt { d } ) ^ { d } ) \log n,$$

On the other hand, the while loop in Algorithm 6 can be executed for at most n times, since there are at most 2 n nodes in T and each execution of the while loop visits 2 nodes. Then the time to execute Algorithm 3 is O k k ( ( + ( √ d ) d ) · n log n ).

Finally, adding the four parts of time and the time complexity of Algorithm 6 is proved to be O k k ( ( +( √ d ) d ) · n log n ). /intersectionsq /unionsq

Theorem 5.5. The space complexity of Algorithm 6 is O n ( 2 ) .

Proof. Only the rectangles in H will store their kNbr and kFrd sets. Thus the space complexity of Algorithm 6 can be computed by multiplying the size of kNbr and kFrd sets and the size of H , which is O n ( 2 ).

In the proof of Theorem 5.4 and 5.5 we use O n ( ) as the bound on | kNbr ( ) r | for leaf node r , which is sufficient to prove the desired O n ( log n ) bound on the running time. Though we can not give an tighter upper bound of the size of kNbr ( ) for leaf node r r , we have the following lemma depicting the structure of it.

Lemma 5.17. Let r to be a leaf node in T , and let r ′ be an arbitrary rectangle in kNbr ( ) r \ Cand ( ) r . Then any r ′′ ∈ kNbr ( r \ Cand ( )) r must satisfy d c ( r ′′ , c r ′ ) ≤ d c , c ( r r ′ ) + 5 2 r r top , where r top is the top element in the heap H .

Proof. Since r ′ / Cand ∈ ( ), r

$$Q l t y ( \mathfrak { r } ^ { \prime }, \mathfrak { r } ) = \sqrt { D ( c _ { \mathfrak { r } ^ { \prime } }, c _ { \mathfrak { r } } + \frac { 1 } { 2 } r _ { \mathfrak { r } ^ { \prime } } ) ^ { 2 } + r _ { \mathfrak { r } ^ { \prime 2 } } } > k T h r e s ( \mathfrak { r } ). \\. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad.$$

Next, since r top is the top element in the heap H and r ′ is an element in H , we have

$$& k T h r e s ( \mathfrak { t } ) < \sqrt { D ( c _ { \mathfrak { t } ^ { \prime } }, c _ { \mathfrak { t } } + \frac { 1 } { 2 } r _ { \mathfrak { t } ^ { \prime } } ) ^ { 2 } + r _ { \mathfrak { t } ^ { \prime 2 } } } < D ( c _ { \mathfrak { t } ^ { \prime } }, c _ { \mathfrak { t } } ) + \frac { 1 } { 2 } r _ { \mathfrak { t } ^ { \prime } } + r _ { \mathfrak { t } ^ { \prime } } < D ( c _ { \mathfrak { t } ^ { \prime } }, c _ { \mathfrak { t } } ) + \frac { 3 } { 2 } r _ { \mathfrak { t } _ { t o p } }. \\ & \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad........................................................................................................................................................................................................$$

On the other hand, D c ( r ′′ , c r ) ≤ r r ′′ + r r + kThres ( ) = r r r ′′ + kThres ( ) since r r ′′ ∈ kNbr and r r = 0. Finally, we have

$$D ( c _ { \tau ^ { \prime \prime } }, c _ { \tau } ) & \leq r _ { \tau ^ { \prime \prime } } + k T h r e s ( \tau ) \leq r _ { \tau _ { t o p } } + D ( c _ { \tau ^ { \prime } }, c _ { \tau } ) + \frac { 3 } { 2 } r _ { \tau _ { t o p } } = D ( c _ { \tau ^ { \prime } }, c _ { \tau } ) + \frac { 5 } { 2 } r _ { \tau _ { t o p } }. \\ & \text{which proves the desired result.}$$

## 6 Conclusion

In this paper the All-k-Nearest-Neighbors problem is considered. An algorithm proposed in [21] is the inspiring work of this paper. In [21] the author claimed that the algorithm has an upper bound of O d n ( d log n ) on the time complexity. However, we find that this bound is unachievable according to the descriptions in [21]. We give formal analysis that the algorithm needs at least Ω n ( 2 ) time. On the other hand, we propose another algorithm for the All-k-Nearest-Neighbor problem whose time complexity is truly up-bounded by O k k ( ( + d d ) n log n ). After all, we have renewed an result that has an history of over 30 years and has been cited mor than 300 times. Considering the importance of the All-kNearest-Neighbor problem, this work should be considered valuable.

## References

- 1. Bˆ adoiu, M., Bˆdoiu, M., Clarkson, K.L., Clarkson, K.L.: Smaller core-sets for balls. a In: Proceedings of the Fourteenth Annual { ACM-SIAM } Symposium on Discrete Algorithms. pp. 801-802 (2003)
- 2. Bentley, J.L.: Multidimensional divide-and-conquer. Communications of the ACM 23 (4), 214-229 (apr 1980). https://doi.org/10.1145/358841.358850, http://portal.acm.org/citation.cfm?doid=358841.358850
- 3. Brito, M., Ch´ avez, E., Quiroz, A., Yukich, J.: Connectivity of the mutual knearest-neighbor graph in clustering and outlier detection. Statistics &amp; Probability Letters 35 (1), 33-42 (aug 1997). https://doi.org/10.1016/S0167-7152(96)00213-1, https://linkinghub.elsevier.com/retrieve/pii/S0167715296002131

- 4. Callahan, P.B.: Optimal Parallel All-nearest-neighbors Using the Well-separated Pair Decomposition. In: Proceedings of the 1993 IEEE 34th Annual Foundations of Computer Science. pp. 332-340. SFCS '93, IEEE Computer Society, Washington, DC, USA (1993). https://doi.org/10.1109/SFCS.1993.366854, https://doi.org/10.1109/SFCS.1993.366854
- 5. Callahan, P.B., Kosaraju, S.R.: A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. Journal of the ACM 42 (1), 67-90 (jan 1995). https://doi.org/10.1145/200836.200853, http://portal.acm.org/citation.cfm?doid=200836.200853
- 6. Clarkson, K.L.: Fast algorithms for the all nearest neighbors problem. In: 24th Annual Symposium on Foundations of Computer Science (sfcs 1983). pp. 226-232. IEEE (1983). https://doi.org/10.1109/SFCS.1983.16
- 7. Connor, M., Kumar, P.: Fast Construction of k-Nearest Neighbor Graphs for Point Clouds. IEEE Transactions on Visualization and Computer Graphics 16 (4), 599-608 (2010). https://doi.org/10.1109/TVCG.2010.9, http://dx.doi.org/10.1109/TVCG.2010.9
- 8. Dong, W., Moses, C., Li, K.: Efficient k-nearest neighbor graph construction for generic similarity measures. In: Proceedings of the 20th international conference on World wide web -WWW '11. p. 577. ACM Press, New York, New York, USA (2011). https://doi.org/10.1145/1963405.1963487, http://portal.acm.org/citation.cfm?doid=1963405.1963487
- 9. Edelsbrunner, H.: Algorithms in Combinatorial Geometry. Springer Publishing Company, Incorporated, 1st edn. (2012)
- 10. Franti, P., Virmajoki, O., Hautamaki, V.: Fast Agglomerative Clustering Using a k-Nearest Neighbor Graph. IEEE Transactions on Pattern Analysis and Machine Intelligence 28 (11), 1875-1881 (nov 2006). https://doi.org/10.1109/TPAMI.2006.227,

https://doi.org/10.1109/TPAMI.2006.227http://ieeexplore.ieee.org/document/1704843/

- 11. Friedman, J.H.: An Algorithm fQr Finding Best Matches in Logarithmic Expected Time 3 (3), 209-226 (1977). https://doi.org/10.1145/355744.355745
- 12. Hilbert, D.: Uber die stetige Abbildung einer Linie auf ein Fl¨chenst¨ck. In: Drit-¨ a u ter Band: Analysis Grundlagen · der Mathematik Physik Verschiedenes, · pp. 1-2. Springer (1935)
- 13. Karypis, G.: Evaluation of Item-Based TopN Recommendation Algorithms. In: Proceedings of the tenth international conference on Information and knowledge management -CIKM'01. p. 247. ACM Press, New York, New York, USA (2001). https://doi.org/10.1145/502585.502627, http://portal.acm.org/citation.cfm?doid=502585.502627
- 14. Komarov, I., Dashti, A., D'Souza, R.: Fast $ k -NNG $ construction with GPU-based quick multi-select pp. 120 (sep 2013). https://doi.org/10.1371/journal.pone.0092409, http://arxiv.org/abs/1309.5478http://dx.doi.org/10.1371/journal.pone.0092409
- 15. Morton, G.M.: A computer oriented geodetic data base and a new technique in file sequencing (1966)
- 16. Park, Y., Lee, S.g.: A novel algorithm for scalable k -nearest neighbour graph construction (2016). https://doi.org/10.1177/1045389X14554132
- 17. Sieranoja, S.: High dimensional k NN-graph construction using space filling curves (April) (2015)
- 18. Szummer, M., Jaakkola, T.: Partially Labeled Classification with Markov Random Walks. In: Proceedings of the 14th International Confer-

ence on Neural Information Processing Systems: Natural and Synthetic. pp. 945-952. NIPS'01, MIT Press, Cambridge, MA, USA (2001), http://dl.acm.org/citation.cfm?id=2980539.2980661

- 19. Trad, M.R., Joly, A., Boujemaa, N.: Distributed KNN-graph approximation via hashing. In: Proceedings of the 2nd ACM International Conference on Multimedia Retrieval -ICMR '12. p. 1. No. section 3, ACM Press, New York, New York, USA (2012). https://doi.org/10.1145/2324796.2324847, http://dl.acm.org/citation.cfm?doid=2324796.2324847
- 20. Vaidya, P.M.: An optimal algorithm for the all-nearest-neighbors problem. In: Intergovernmental Panel on Climate Change (ed.) 27th Annual Symposium on Foundations of Computer Science (sfcs 1986). pp. 117-122. IEEE, Cambridge (oct 1986). https://doi.org/10.1109/SFCS.1986.8
- 21. Vaidya, P.M.: AnO(n logn) algorithm for the all-nearest-neighbors Problem. Discrete &amp; Computational Geometry 4 (2), 101-115 (mar 1989). https://doi.org/10.1007/BF02187718
- 22. Wang, J., Wang, J., Zeng, G., Tu, Z., Gan, R., Li, S.: Scalable k-nn graph construction for visual descriptors. In: 2012 IEEE Conference on Computer Vision and Pattern Recognition. pp. 1106-1113. IEEE (2012)
- 23. WARASHINA, T., AOYAMA, K., SAWADA, H., HATTORI, T.: Efficient K-Nearest Neighbor Graph Construction Using MapReduce for LargeScale Data Sets. IEICE Transactions on Information and Systems 97D (12), 3142-3154 (2014). https://doi.org/10.1587/transinf.2014EDP7108, http://jlc.jst.go.jp/DN/JST.JSTAGE/transinf/2014EDP7108?lang=en { &amp; from=CrossRef }
- 24. Yang, X., Latecki, L.J.: Affinity Learning on a Tensor Product Graph with Applications to Shape and Image Retrieval. In: Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition. pp. 2369-2376. CVPR '11, IEEE Computer Society, Washington, DC, USA (2011). https://doi.org/10.1109/CVPR.2011.5995325, http://dx.doi.org/10.1109/CVPR.2011.5995325
- 25. Yao, B., Li, F., Kumar, P.: K nearest neighbor queries and kNNJoins in large relational databases (almost) for free. In: 2010 IEEE 26th International Conference on Data Engineering (ICDE 2010). pp. 4-15. IEEE (2010). https://doi.org/10.1109/ICDE.2010.5447837, http://ieeexplore.ieee.org/document/5447837/
- 26. Yildirim, E.A.: Two Algorithms for the Minimum Enclosing Ball Problem. SIAM Journal on Optimization 19 (3), 1368-1391 (jan 2008). https://doi.org/10.1137/070690419, http://epubs.siam.org/doi/10.1137/070690419
- 27. Zarrabi-Zadeh, H., Chan, T.: A simple streaming algorithm for minimum enclosing balls. Proc. 18th Annual Canadian Conf. Comput. . . . pp. 14-17 (2006), http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.68.1421 { &amp; rep=rep1 &amp; type=pdf } { }
- 28. Zhang, Y.m., Huang, K., Geng, G., Liu, C.l.: Fast k NN Graph Construction with Locality pp. 660-674 (2013)

{

&amp; type=abstract

}
Hengzhao Ma Jianzhong Li
A True $O(n \log{n}) $ Algorithm for the All-k-Nearest-Neighbors Problem
In this paper we examined an algorithm for the All-k-Nearest-Neighbor problem
proposed in 1980s, which was claimed to have an $O(n\log{n})$ upper bound on
the running time. We find the algorithm actually exceeds the so claimed upper
bound, and prove that it has an $\Omega(n^2)$ lower bound on the time
complexity. Besides, we propose a new algorithm that truly achieves the
$O(n\log{n})$ bound. Detailed and rigorous theoretical proofs are provided to
show the proposed algorithm runs exactly in $$O(n\log{n})$$ time.