Efficient implementation of the Nearest Neighbour Search

c++ tree nearest-neighbor
dato datuashvili picture dato datuashvili · Apr 6, 2012 · Viewed 13.9k times · Source

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.

Answer

Andrew Walker picture Andrew Walker · Apr 6, 2012

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

Related questions

Why does the C++ STL not provide any "tree" containers?

Why does the C++ STL not provide any "tree" containers, and what's the best thing to use instead? I want to store a hierarchy of objects as a tree, rather than use a tree as a performance enhancement...

Read More
Is there pointer in C# like C++? Is it safe?

I'm writing an application that work with a tree data structure. I've written it with C++, now i want to write it by C#. I use pointers for implementing the tree data structure. Is there a pointer in C# too? …

Read More
What's a good and stable C++ tree implementation?

I'm wondering if anyone can recommend a good C++ tree implementation, hopefully one that is stl compatible if at all possible. For the record, I've written tree algorithms many times before, and I know it can be fun, but I …

Read More