Fast high-dimensional K-nearest neighbors

Question

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.

Answer 1

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

Answer 2

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