Efficient implementation of the Nearest Neighbour Search

Question

I am trying to implement an efficient algorithm for nearest-neighbour search problem.

I have read tutorials about some data structures, which support operations for this kind of problems (for example, R-tree, cover tree, etc.), but all of them are difficult to implement.

Also I cannot find sample source code for these data structures. I know C++ and I am trying to solve this problem in this language.

Ideally, I need links that describe how to implement these data structures using source code.

Solution 1

You could try a linesweep algorithm to find the closest pair of points: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lineSweep.

Solution 2

There are several good choices of fast nearest neighbor search libraries.

• ANN, which is based on the work of Mount and Arya. This work is documented in a paper by S. Arya and D. M. Mount. "Approximate nearest neighbor queries in fixed dimensions". In Proc. 4th ACM-SIAM Sympos. Discrete Algorithms, pages 271–280, 1993.

• FLANN, which is based on the work of Marius Muja & Co. There is a paper by Marius Muja and David G. Lowe, "Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration", in International Conference on Computer Vision Theory and Applications (VISAPP'09), 2009. The code for FLANN is available on github

FLANN seems to be quicker in some cases, and is a more modern version of the code with solid bindings for a number of other languages, that can incorporate changes rapidly. ANN is probably a good choice if you want a solid well-tested standard library.

Edit in Response to Comment

Both of these libraries have extensive documentation and examples.

Sample code for ANN is available in the Manual, In section 2.1.4

Sample code for FLANN is available in the FLANN repository examples directory, for example /examples/flann_examples.c