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.

Lumbering

What is the dimensionality of your data? For 2D point data I would recommend using a Kd-tree. It's easy to implement. For other types of data/geometries you might want to look at R-trees (boost 1.54 supports rtree indexes) – Learning

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

Portie

Answer 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

Hardpan

how to use it,when for example i have (x1,y1)(x2,y2)...(xn,yn)? – Lumbering

@dato - the answer has been updated to include links to authoritative examples from each projects documentation. – Hardpan

i need instal yes FLANN library? – Lumbering

Yes, you would. Using FLANN (or ANN) requires that you make the appropriate files available on your include and library paths, just the same way that you would with any other non-trivial C++ library – Hardpan

@AndrewWalker Could you add nanoflann to the answer? It is a fork from FLANN and apparently faster. It is a C++11 header only library which is really convenient. Thanks and greetings – Matrilocal