1 Introduction
We can define the nearest neighbor search (NSS) problem in the following way:
given a set of points P = p
1
, p
2
, . . . , p
n
in a metric space X, these points must
be preprocessed in such a way that given a new query point q ∈ X, finding the
point in P that is nearest to q can be done quickly.
The problem of nearest neighbor search is one of major importance in a
variety of applications such as image recognition, data compression, pattern
recognition and classification, machine learning, document retrieval systems,
statistics and data analysis. However, solving this problem in high dimensional
spaces seems to be a very difficult task and there is no algorithm that performs
significantly better than the standard brute-force search. This has lead to an
increasing interest in a class of algorithms that perform approximate nearest
neighbor searches, which have proven to be a good-enough approximation in
most practical applications and in most cases, orders of magnitude faster that
the algorithms performing the exact searches.
FLANN (Fast Library for Approximate Nearest Neighbors) is a library for
performing fast approximate nearest neighbor searches. FLANN is written in
the C++ programming language. FLANN can be easily used in many contexts
through the C, MATLAB and Python bindings provided with the library.
1.1 Quick Start
This section contains small examples of how to use the FLANN library from
different programming languages (C++, C, MATLAB and Python).
• C++
// file flann_example.cpp
#include <flann/flann.hpp>
#include <flann/io/hdf5.h>
#include <stdio.h>
int main(int argc, char** argv)
{
int nn = 3;
flann::Matrix<float> dataset;
flann::Matrix<float> query;
flann::load_from_file(dataset, "dataset.hdf5","dataset");
flann::load_from_file(query, "dataset.hdf5","query");
flann::Matrix<int> indices(new int[query.rows*nn], query.rows, nn);
flann::Matrix<float> dists(new float[query.rows*nn], query.rows, nn);
// construct an randomized kd-tree index using 4 kd-trees
flann::Index<flann::L2<float> > index(dataset, flann::KDTreeIndexParams(4));
index.buildIndex();
// do a knn search, using 128 checks
index.knnSearch(query, indices, dists, nn, flann::SearchParams(128));
flann::save_to_file(indices,"result.hdf5","result");
1
