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

(14 December 2012) Version 1.8.0 is out bringing incremental addition/removal of points to/from indexes
(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.

Publications

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

Marius Muja and David G. Lowe: "Scalable Nearest Neighbor Algorithms for High Dimensional Data". Pattern Analysis and Machine Intelligence (PAMI), Vol. 36, 2014. [PDF] [BibTeX]

@article{flann_pami_2014,
  title={Scalable Nearest Neighbor Algorithms for High Dimensional Data},
  author={Marius Muja and David G. Lowe},
  journal={Pattern Analysis and Machine Intelligence, IEEE Transactions on},
  volume={36},
  year={2014},
  publisher={IEEE}
}

Marius Muja and David G. Lowe: "Fast Matching of Binary Features". Conference on Computer and Robot Vision (CRV) 2012. [PDF] [BibTeX]

@inproceedings{Attach:binary_matching_crv2012,
	author    = {Marius Muja and David G. Lowe},
	title = {Fast Matching of Binary Features},
	booktitle = {Computer and Robot Vision {(CRV)}},
	year = {2012},
	pages = {404-410}
}

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]

@inproceedings{muja_flann_2009,
  author    = {Marius Muja and David G. Lowe},
  title     = {Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration},
  booktitle = {International Conference on Computer Vision Theory and Application 
               VISSAPP'09)},
  publisher = {INSTICC Press},
  year      = {2009},
  pages     = {331-340}
}

Getting FLANN

The latest version of FLANN can be downloaded from here:

Version 1.8.4 (15 January 2013)
Changes from 1.8.3:
- Fixed memory leak and OpenMP compilation under MSVC
flann-1.8.4-src.zip (Source code)
User manual
Changelog

Version 1.8.0 (14 December 2012)
Changes:
- incremental addition and removal of points to/from indexes
- more flexible index serialization
- replaced TBB multi-threading support with OpenMP
- bug fixes
- NOTE: Due to changes in the library, the on-disk format of the saved indexes has changed and it is not possible to load indexes saved with an older version of the library.

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: mailto:mariusm@cs.ubc.ca.

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