<p>For high-dimensional exact nearest neighbor search the theoretical guarantees are pretty dismal: the best algorithms are based on fast matrix multiplication and have running time of the form $O(N^2D^\alpha)$ for some $\alpha &lt; 1$. </p>

<p>On the other hand you can do better if you are ok with approximation. <a href="http://www.mit.edu/~andoni/LSH/" rel="nofollow">Locality sensitive hashing</a> can be used to achieve subquadratic in $N$ running times while reporting points which are not much further than the nearest neighbors. </p>

<p>For subsets of Euclidean space with doubling dimension $d$ (which captures the lower-dimensional manifold situation), <a href="https://web.math.princeton.edu/~naor/homepage%20files/lowdim-journal-new2.pdf" rel="nofollow">Indyk and Naor</a> show that there is an embedding into $O(d)$ dimensions (in fact a random projection in the style of the Johnson-Lindenstrauss lemma) which approximately preserves nearest neighbors. If $d$ is small enough you could first apply the embedding, then use a nearest neighbor data structure for low dimension.</p>

<p>You could also try the <a href="http://dl.acm.org/citation.cfm?doid=1374376.1374452" rel="nofollow">random projection trees</a> (RP-trees) of Dasgupta and Freund. They are a natural variant of kd-trees in which the cut in each level is done in a random direction, rather than a coordinate direction. I don't think there are any known provable guarantee for how well RP-trees do on nearest neighbor problems, but the paper I have linked does prove that the trees adapt nicely to doubling dimension, so there is hope. The guarantee they give is that, if a point set inside a cell has doubling dimension $d$, then the descendants of the cell $O(d\log d)$ levels down the tree have diameter at most half that of the cell.</p>

CC BY-SA 3.0
2014-11-13T19:55:40.177Z
2014-11-14T06:33:32.300Z
2014-11-14T06:33:32.300Z
Sasho Nikolov
<p>Several state of the art approximate nearest neighbor methods in high dimensions are based on reducing the dimension of the space through randomized techniques.</p>

<p>The main idea is that you can exploit <a href="http://www.math.lsa.umich.edu/~barvinok/total710.pdf" rel="nofollow">concentration of measure</a> to greatly reduce the dimension of the space while preserving distances up to tolerance $\epsilon$. </p>

<p>In particular, following from the Johnson-Lindenstrauss lemma (upper bound) and a result of Noga Alon (lower bound), there exists a subspace of reduced dimension 
$$C_1 \frac{\log(N)}{\epsilon^2 \log(1/\epsilon)} \le \text{reduced dimension} \le C_2\frac{\log(N)}{\epsilon^2}$$</p>

<p>such that for any two points $u,v$ in your collection, their projections $\tilde{u}, \tilde{v}$ onto the reduced dimensional space satisfy 
$$(1-\epsilon)||u-v||^2 \le ||\tilde{u} - \tilde{v}||^2 \le (1+\epsilon)||u-v||^2.$$</p>

<p>Indeed, such subspaces are "typical" in a sense, and you can find such a subspace with high probability by simply projecting your points onto a completely random hyperplane (and in the unlikely event that such a hyperplane is not good enough, just pick another random one and project again). </p>

<p>Now you have a nearest neighbor problem on a much much lower dimensional space.</p>

<p>A key paper is,</p>

<blockquote>
  <p>Ailon, Nir, and Bernard Chazelle. 
  "Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform." 
  Proceedings of the thirty-eighth annual ACM symposium on Theory of computing. ACM, 2006.
  <a href="http://www.cs.technion.ac.il/~nailon/fjlt.pdf" rel="nofollow">http://www.cs.technion.ac.il/~nailon/fjlt.pdf</a></p>
</blockquote>

CC BY-SA 3.0
2014-11-14T06:25:44.073Z
There is something wrong with your reduced dimension bound. First, the lemma gives an upper bound on dimension, so the big-omega is not the right kind of asymptotics. Second, the expression in the parenthesis is negative for $1> \epsilon > 0$.
Sasho Nikolov
CC BY-SA 3.0
2014-11-14T07:34:55.943Z
@SashoNikolov Indeed there was a typo in the expression in the parenthesis that has been fixed now ($\log(1-\epsilon)$ should have been $\log(1/\epsilon)$ ). The big-omega asymptotics is correct though, as the bound is tight. There exist collections of points that require such a dimension to be well-approximated.
Nick Alger
CC BY-SA 3.0
2014-11-14T09:18:02.050Z
There do exist such sets, but this is *not* the JL lemma, this is a result by Noga Alon which shows that the JL lemma is close to being tight. The JL lemma itself says that the dimension of the embedding is at most $O(\epsilon^{-2}\log(N))$. Notice that there is a gap between Alon's lower bound and the JL upper bound. There is some strong evidence that it is the upper bound which is the correct answer, and not the lower bound which you cite.
Sasho Nikolov
CC BY-SA 3.0
2014-11-14T09:52:26.373Z
Interesting, I stand corrected. I always thought the bound was tight. Do you have a good reference for Noga Alon's result?
Nick Alger
CC BY-SA 3.0
2014-11-14T16:21:19.343Z
Last section of http://www.math.tau.ac.il/~nogaa/PDFS/extremal1.pdf. The point set is just an orthonormal system.
Sasho Nikolov
CC BY-SA 3.0
2014-11-14T17:48:03.647Z
Tight lower bounds $\Omega(\epsilon^{-2}\log N)$ have been proven for [distributional JL](http://researcher.ibm.com/files/us-dpwoodru/jw13.pdf) and, very recently, for [linear embeddings](http://arxiv.org/abs/1411.2404). The last paper has a nice discussion.
Sasho Nikolov
CC BY-SA 3.0
2014-11-13T20:39:38.830Z
2014-11-14T10:04:35.323Z
2014-11-14T10:04:35.323Z
Nick Alger
<p>I'm aware of this question
<a href="https://stackoverflow.com/questions/4350215/fastest-nearest-neighbor-algorithm">https://stackoverflow.com/questions/4350215/fastest-nearest-neighbor-algorithm</a>
But it's not the same question as I'm asking. Because, Octree and its generalization are only applicable to very small $D$, and they increase exponentially with regard to it. But I'm interested in very high dimensional cases, like $D&gt;1000$. Assume we have a cloud of $N$ points in a $D$ dimensional space. But they might have a lower inherent dimension $d$, i.e., they lie on a $d$ dimensional manifold. Now, what is the most efficient way to compute K-nearest neighbors for each point? I've researched this topic a little bit, but most of the literature focuses on KNN clustering which is slightly different from what I'm asking. First, I don't have any labels here and those methods which rely on labels to reduce complexity are not of any interest. Second, many methods focus on reducing query processing time, which means they pre-process the data, build a database, and quickly process new queries. But I'm interested in reducing the overall time complexity rather than queries. What is the state-of-the-art method and its time complexity? </p>

<p><strong>UPDATE:</strong>
One might assume that these points are uniformly spread in a hyper-cube. I suppose anything which holds for uniform distribution, to a lesser extent will hold for a smoothly changing distribution. </p>

CC BY-SA 3.0
2014-11-13T19:05:33.280Z
Is approximation ok? If it is, you should have a look at [locality sensitive hashing](http://www.mit.edu/~andoni/LSH/)
Sasho Nikolov
<cg.comp-geom><time-complexity><computational-geometry>
Fast high-dimensional K-nearest neighbors
AmeerJ
# Fast high-dimensional K-nearest neighbors

(Asked by: username_0 on 2014-11-13)

I'm aware of this question
<https://stackoverflow.com/questions/4350215/fastest-nearest-neighbor-algorithm>
But it's not the same question as I'm asking. Because, Octree and its generalization are only applicable to very small $D$, and they increase exponentially with regard to it. But I'm interested in very high dimensional cases, like $D>1000$. Assume we have a cloud of $N$ points in a $D$ dimensional space. But they might have a lower inherent dimension $d$, i.e., they lie on a $d$ dimensional manifold. Now, what is the most efficient way to compute K-nearest neighbors for each point? I've researched this topic a little bit, but most of the literature focuses on KNN clustering which is slightly different from what I'm asking. First, I don't have any labels here and those methods which rely on labels to reduce complexity are not of any interest. Second, many methods focus on reducing query processing time, which means they pre-process the data, build a database, and quickly process new queries. But I'm interested in reducing the overall time complexity rather than queries. What is the state-of-the-art method and its time complexity?

**UPDATE:**
One might assume that these points are uniformly spread in a hyper-cube. I suppose anything which holds for uniform distribution, to a lesser extent will hold for a smoothly changing distribution.

**Tags:** cg.comp-geom, time-complexity, computational-geometry
> **Comments:**
> **username_1**: Is approximation ok? If it is, you should have a look at [locality sensitive hashing](http://www.mit.edu/~andoni/LSH/)  

---

## 2 answers

### Answer by username_1 on 2014-11-13. Score: 5 | Accepted answer

For high-dimensional exact nearest neighbor search the theoretical guarantees are pretty dismal: the best algorithms are based on fast matrix multiplication and have running time of the form $O(N^2D^\alpha)$ for some $\alpha < 1$.

On the other hand you can do better if you are ok with approximation. [Locality sensitive hashing](http://www.mit.edu/~andoni/LSH/) can be used to achieve subquadratic in $N$ running times while reporting points which are not much further than the nearest neighbors.

For subsets of Euclidean space with doubling dimension $d$ (which captures the lower-dimensional manifold situation), [Indyk and Naor](https://web.math.princeton.edu/~naor/homepage%20files/lowdim-journal-new2.pdf) show that there is an embedding into $O(d)$ dimensions (in fact a random projection in the style of the Johnson-Lindenstrauss lemma) which approximately preserves nearest neighbors. If $d$ is small enough you could first apply the embedding, then use a nearest neighbor data structure for low dimension.

You could also try the [random projection trees](http://dl.acm.org/citation.cfm?doid=1374376.1374452) (RP-trees) of Dasgupta and Freund. They are a natural variant of kd-trees in which the cut in each level is done in a random direction, rather than a coordinate direction. I don't think there are any known provable guarantee for how well RP-trees do on nearest neighbor problems, but the paper I have linked does prove that the trees adapt nicely to doubling dimension, so there is hope. The guarantee they give is that, if a point set inside a cell has doubling dimension $d$, then the descendants of the cell $O(d\log d)$ levels down the tree have diameter at most half that of the cell.


---

### Answer by username_2 on 2014-11-13. Score: 4

Several state of the art approximate nearest neighbor methods in high dimensions are based on reducing the dimension of the space through randomized techniques.

The main idea is that you can exploit [concentration of measure](http://www.math.lsa.umich.edu/~barvinok/total710.pdf) to greatly reduce the dimension of the space while preserving distances up to tolerance $\epsilon$.

In particular, following from the Johnson-Lindenstrauss lemma (upper bound) and a result of Noga Alon (lower bound), there exists a subspace of reduced dimension
$$C\_1 \frac{\log(N)}{\epsilon^2 \log(1/\epsilon)} \le \text{reduced dimension} \le C\_2\frac{\log(N)}{\epsilon^2}$$

such that for any two points $u,v$ in your collection, their projections $\tilde{u}, \tilde{v}$ onto the reduced dimensional space satisfy
$$(1-\epsilon)||u-v||^2 \le ||\tilde{u} - \tilde{v}||^2 \le (1+\epsilon)||u-v||^2.$$

Indeed, such subspaces are "typical" in a sense, and you can find such a subspace with high probability by simply projecting your points onto a completely random hyperplane (and in the unlikely event that such a hyperplane is not good enough, just pick another random one and project again).

Now you have a nearest neighbor problem on a much much lower dimensional space.

A key paper is,

> Ailon, Nir, and Bernard Chazelle.
> "Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform."
> Proceedings of the thirty-eighth annual ACM symposium on Theory of computing. ACM, 2006.
> <http://www.cs.technion.ac.il/~nailon/fjlt.pdf>

> **Comments:**
> **username_1**: There is something wrong with your reduced dimension bound. First, the lemma gives an upper bound on dimension, so the big-omega is not the right kind of asymptotics. Second, the expression in the parenthesis is negative for $1> \epsilon > 0$.  
> **username_2**: @SashoNikolov Indeed there was a typo in the expression in the parenthesis that has been fixed now ($\log(1-\epsilon)$ should have been $\log(1/\epsilon)$ ). The big-omega asymptotics is correct though, as the bound is tight. There exist collections of points that require such a dimension to be well-approximated.  
> **username_1**: There do exist such sets, but this is *not* the JL lemma, this is a result by Noga Alon which shows that the JL lemma is close to being tight. The JL lemma itself says that the dimension of the embedding is at most $O(\epsilon^{-2}\log(N))$. Notice that there is a gap between Alon's lower bound and the JL upper bound. There is some strong evidence that it is the upper bound which is the correct answer, and not the lower bound which you cite.  
> **username_2**: Interesting, I stand corrected. I always thought the bound was tight. Do you have a good reference for Noga Alon's result?  
> **username_1**: Last section of http://www.math.tau.ac.il/~nogaa/PDFS/extremal1.pdf. The point set is just an orthonormal system.  
> **username_1**: Tight lower bounds $\Omega(\epsilon^{-2}\log N)$ have been proven for [distributional JL](http://researcher.ibm.com/files/us-dpwoodru/jw13.pdf) and, very recently, for [linear embeddings](http://arxiv.org/abs/1411.2404). The last paper has a nice discussion.  

---

