Fast high-dimensional K-nearest neighbors 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&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? 

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.
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$. 

On the other hand you can do better if you are ok with approximation. Locality sensitive hashing 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 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 (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.