FLANN - Fast Library for Approximate Nearest Neighbors

What is FLANN?

FLANN is a library for performing fast approximate nearest neighbor searches in high dimensional spaces. It contains a collection of algorithms we found to work best for nearest neighbor search and a system for automatically choosing the best algorithm and optimum parameters depending on the dataset.

FLANN is written in C++ and contains bindings for the following languages: C, MATLAB and Python.

News

  • (20 December 2011) Version 1.7.0 is out bringing two new index types and several other improvements.
  • You can find binary installers for FLANN on the Point Cloud Library project page. Thanks to the PCL developers!
  • Mac OS X users can install flann though MacPorts (thanks to Mark Moll for maintaining the Portfile)
  • New release introducing an easier way to use custom distances, kd-tree implementation optimized for low dimensionality search and experimental MPI support
  • New release introducing new C++ templated API, thread-safe search, save/load of indexes and more.
  • The FLANN license was changed from LGPL to BSD.

How fast is it?

In our experiments we have found FLANN to be about one order of magnitude faster on many datasets (in query time), than previously available approximate nearest neighbor search software.

Paper

More information and experimental results can be found in the following paper:

  • 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 [PDF] [BibTeX]

Getting FLANN

The latest version of FLANN can be downloaded from here:


  • Version 1.7.0 (20 December 2011)
    Note: there is a small breaking API change if upgrading from a previous version, check the manual on how to update your code.
    Changes:
    • new index type (HierarchicalClusteringIndex) for matching features using any metric distance (works well for binary features and Hamming distances)
    • LSH implementation for matching binary features contributed by Vincent Rabaud
    • GPU kd-tree matching for 3D features on CUDA compatible hardware contributed by Andreas Mützel
    • support for multithreaded search using the TBB library contributed by Nick Vanbaelen
    • better performance when searching for many neighbors
    • improvements to the MPI search support
    • support for radius search using multiple query points at once
    • bug fixes

If you don't want to compile FLANN from source you can try the binary installers prepared by the Point Cloud Library (PCL) project here (Ubuntu/Debian PPA, Windows Installers and Mac OS X Universal Binary).

If you want to try out the latest changes or contribute to FLANN, then it's recommended that you checkout the git source repository: git clone git://github.com/mariusmuja/flann.git

If you just want to browse the repository, you can do so by going here.

System requirements

The FLANN library was developed and tested under Linux. A C++ compiler is required to build FLANN. The Python bindings require the presence of the Numerical Python (numpy) package.

Conditions of use

FLANN is distributed under the terms of the BSD License.

Questions/Comments

If you have any questions or comments please email them to: .

Please report bugs or feature requests using github's issue tracker.