How to efficiently find k-nearest neighbours in high-dimensional data?

Question

So I have about 16,000 75-dimensional data points, and for each point I want to find its k nearest neighbours (using euclidean distance, currently k=2 if this makes it easiser)

My first thought was to use a kd-tree for this, but as it turns out they become rather inefficient as the number of dimension grows. In my sample implementation, its only slightly faster than exhaustive search.

My next idea would be using PCA (Principal Component Analysis) to reduce the number of dimensions, but I was wondering: Is there some clever algorithm or data structure to solve this exactly in reasonable time?

Junie

I think this is similar to one of these: facebook.com/careers/puzzles.php – Enchiridion

As far as exact solutions I suspect the answer is no, but I wanted to suggest random projections and the Johnson Lindenstrauss theorem might help – Trudytrue

+1 for the previous comment which is along the same lines as LSH and ANN. – Tatman

I would recommend Hanan Samet's book, Foundations of Multidimensional and Metric Data Structures. It has some chapters specifically on structures suited to high-dimensional data. – Modulation

My library actually has this, so I'll definitely have a look. Most of the answers seem to involve a good bit of reading, so I guess it'll take some time until i can accept one :) – Junie

I've removed my answer, as thinking about it made me realize it was both misleading and incorrect. – Indigestion

Answer 1

The Wikipedia article for kd-trees has a link to the ANN library:

ANN is a library written in C++, which supports data structures and algorithms for both exact and approximate nearest neighbor searching in arbitrarily high dimensions.

Based on our own experience, ANN performs quite efficiently for point sets ranging in size from thousands to hundreds of thousands, and in dimensions as high as 20. (For applications in significantly higher dimensions, the results are rather spotty, but you might try it anyway.)

As far as algorithm/data structures are concerned:

The library implements a number of different data structures, based on kd-trees and box-decomposition trees, and employs a couple of different search strategies.

I'd try it first directly and if that doesn't produce satisfactory results I'd use it with the data set after applying PCA/ICA (since it's quite unlikely your going to end up with few enough dimensions for a kd-tree to handle).

Amphictyon

+1 for ANN, a pretty hot topic in information retrieval lately. Search "FLANN" for one implementation by Lowe, and "ANN" by David Mount. Also search for the related "locality sensitive hashing". – Tatman

@Steve: Tnx for the FLANN & locality sensitive hashing tips, very interesting stuff! – Amphictyon

Thats what I ended up using, and (along with a re-write of the program in c++) its pretty fast (<1 second). – Junie

@Benno: Glad it worked for you. As a curiosity, did you applied it to the original data (75 dimensions) or on what resulted after doing PCA/ICA? – Amphictyon

I did apply PCA, but only to change base vectors, not to reduce the dimension. It has its limits though, for another dataset with 240,000 points it took about 15 minutes. – Junie

Answer 2

use a kd-tree

Unfortunately, in high dimensions this data structure suffers severely from the curse of dimensionality, which causes its search time to be comparable to the brute force search.

reduce the number of dimensions

Dimensionality reduction is a good approach, which offers a fair trade-off between accuracy and speed. You lose some information when you reduce your dimensions, but gain some speed.

By accuracy I mean finding the exact Nearest Neighbor (NN).

Principal Component Analysis(PCA) is a good idea when you want to reduce the dimensional space your data live on.

Is there some clever algorithm or data structure to solve this exactly in reasonable time?

Approximate nearest neighbor search (ANNS), where you are satisfied with finding a point that might not be the exact Nearest Neighbor, but rather a good approximation of it (that is the 4th for example NN to your query, while you are looking for the 1st NN).

That approach cost you accuracy, but increases performance significantly. Moreover, the probability of finding a good NN (close enough to the query) is relatively high.

You could read more about ANNS in the introduction our kd-GeRaF paper.

A good idea is to combine ANNS with dimensionality reduction.

Locality Sensitive Hashing (LSH) is a modern approach to solve the Nearest Neighbor problem in high dimensions. The key idea is that points that lie close to each other are hashed to the same bucket. So when a query arrives, it will be hashed to a bucket, where that bucket (and usually its neighboring ones) contain good NN candidates).

FALCONN is a good C++ implementation, which focuses in cosine similarity. Another good implementation is our DOLPHINN, which is a more general library.

Warfeld

Answer 3

You could conceivably use Morton Codes, but with 75 dimensions they're going to be huge. And if all you have is 16,000 data points, exhaustive search shouldn't take too long.

Deuterium

Thats 16,000 comparisons for each point, so 16,000^2 comparisons overall. Its not taking forever, but at least hours to days. I'll read up on Morton codes, though. – Junie

@Benno: Ah, I assumed that you were looking at nearest neighbors for arriving points. If you're looking to order by locality, then Morton Codes are probably the way to go, large or not. You should Google for searching Z-order curves, as there's some weirdness to it. And you might want to look at the Wikipedia article on GeoHash, which is essentially a text translation of a Morton Code. (and finally, note that Morton codes as described are for 2 dimensions, but there's no real limit to the number of dimensions you can interleave) – Deuterium

Answer 4

No reason to believe this is NP-complete. You're not really optimizing anything and I'd have a hard time figure out how to convert this to another NP-complete problem (I have Garey and Johnson on my shelf and can't find anything similar). Really, I'd just pursue more efficient methods of searching and sorting. If you have n observations, you have to calculate n x n distances right up front. Then for every observation, you need to pick out the top k nearest neighbors. That's n squared for the distance calculation, n log (n) for the sort, but you have to do the sort n times (different for EVERY value of n). Messy, but still polynomial time to get your answers.

Redundant

Answer 5

BK-Tree isn't such a bad thought. Take a look at Nick's Blog on Levenshtein Automata. While his focus is strings it should give you a spring board for other approaches. The other thing I can think of are R-Trees, however I don't know if they've been generalized for large dimensions. I can't say more than that since I neither have used them directly nor implemented them myself.

Nevil

Answer 6

One very common implementation would be to sort the Nearest Neighbours array that you have computed for each data point. As sorting the entire array can be very expensive, you can use methods like indirect sorting, example Numpy.argpartition in Python Numpy library to sort only the closest K values you are interested in. No need to sort the entire array.

@Grembo's answer above should be reduced significantly. as you only need K nearest Values. and there is no need to sort the entire distances from each point.

If you just need K neighbours this method will work very well reducing your computational cost, and time complexity.

if you need sorted K neighbours, sort the output again

see

Documentation for argpartition

Margarettmargaretta