4
$\begingroup$

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.

|cite|improve this question
$\endgroup$
5
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
4
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Sasho Nikolov Nov 14 '14 at 6:25
  • $\begingroup$ @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. $\endgroup$ – Nick Alger Nov 14 '14 at 7:34
  • $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Nov 14 '14 at 9:18
  • $\begingroup$ Interesting, I stand corrected. I always thought the bound was tight. Do you have a good reference for Noga Alon's result? $\endgroup$ – Nick Alger Nov 14 '14 at 9:52
  • $\begingroup$ Last section of math.tau.ac.il/~nogaa/PDFS/extremal1.pdf. The point set is just an orthonormal system. $\endgroup$ – Sasho Nikolov Nov 14 '14 at 16:21
-2
$\begingroup$

Have you considered a kd-tree? More optimal algorithms usually require a less general case problem.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ But is it scalable to high dimensions? My impression was that kd-tree time and memory demands increase exponentially with respect to D. $\endgroup$ – AmeerJ Nov 13 '14 at 15:28
  • 1
    $\begingroup$ In general, kNN breaks down in high-dimensional space because of the 'curse of dimensionality'. Is it possible for you to use dimensional reduction techniques such as principal components analysis? $\endgroup$ – Daniel Henneberger Nov 13 '14 at 16:28
  • 1
    $\begingroup$ Take a look at algorithms such as iDistance which uses arbitrary reference points which allows for ranking and indexing despite the high dimensionality. This algorithm is frequently used in practical applications. 'New' algorithms for exact kNN include iDStar(2014) which is a bit of a hybrid of a few methods. If you are okay with approximating kNN then Locality sensitive B-tree has offered considerable success (cse.ust.hk/~yike/sigmod09-lsb.pdf). Also, lookat Dimensional reduction techniques such as distance learning metrics. Distance learning functions are an active research area. $\endgroup$ – Daniel Henneberger Nov 13 '14 at 16:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.