2

FLANN (Fast Library for Approximate Nearest Neighbors) 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, Python, and Ruby. https://github.com/mariusmuja/flann

What are the algorithms available to FLANN and how does it choose which algorithm and parameters to use?

I ask because, I noticed a x10 speed decrease using a voxel filter prior to using FLANN and wish to figure out what to attribute it to. The voxel filter removes 70% of the points in the data, but the speed decrease seems to much greater.

harkib
  • 43
  • 1
  • 5

1 Answers1

3

FLANN uses these algorithms (defines.h):

FLANN_INDEX_LINEAR
FLANN_INDEX_KDTREE          
FLANN_INDEX_KMEANS 
FLANN_INDEX_COMPOSITE 
FLANN_INDEX_KDTREE_SINGLE
FLANN_INDEX_HIERARCHICAL
FLANN_INDEX_LSH

Section 2, last paragraph, from FAST APPROXIMATE NEAREST NEIGHBORS WITH AUTOMATIC ALGORITHM CONFIGURATION, Mins, Lowe, 2009, it mentions:

In our experiments, one of two algorithms obtained the best performance, depending on the dataset and desired precision. These algorithms used either the hierarchical k-means tree or multiple randomized kd-trees.

Section 3.3 answers your question about how FLANN chooses the algorithm it appears (from the sample) to be the best at hand. Here is half of it:

enter image description here

gsamaras
  • 71,951
  • 46
  • 188
  • 305