K-nearest neighbour C/C++ implementation

Question

Where can I find an serial C/C++ implementation of the k-nearest neighbour algorithm?
Do you know of any library that has this?
I have found openCV but the implementation is already parallel.
I want to start from a serial implementation and parallelize it with pthreads openMP and MPI.

Thanks,
Alex

Solution 1

How about ANN? http://www.cs.umd.edu/~mount/ANN/. I have once used the kdtree implementation, but there are other options.

Quoting from the website: "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."

Solution 2

I wrote a C++ implementation for a KD-tree with nearest neighbor search. You can easily extend it for K-nearest neighbors by adding a priority queue.

Update: I added support for k-nearest neighbor search in N dimensions

Solution 3

The simplest way to implement this is to loop through all elements and store K nearest. (just comparing). Complexity of this is O(n) which is not so good but no preprocessing is needed. So now really depends on your application. You should use some spatial index to partition area where you search for knn. For some application grid based spatial structure is just fine (just divide your world into fixed block and search only within closes blocks first). This is good when your entities are evenly distributed. Better approach is to use some hierarchical structure like kd-tree... It really all depends on what you need

for more information including pseudocode look in these presentations:

http://www.ulozto.net/xCTidts/dpg06-pdf

http://www.ulozto.net/xoh6TSD/dpg07-pdf

Comments

[alexsardan]

Thanks for the reply. Actually I have to start from an already implemented version.