Dahua Lin, on Aug 10, 2007
ANN MATLAB Wrapper is a MATLAB port of the Approximate Nearest Neighbor Library, which is a C++ library to facilitate both exact and approximate nearest neighbor searching. This wrapper is based on ANN C++ Lib version 1.1.1.
The tool aims at solving the problem of searching k nearest neighbors in a large set of multi-dimensional points. To this end, it first builds a data structure based on the set of reference points, and then search neighbors for each query point using this structure. The ANN library implements two types of data structures for searching, including kd-trees and bd-trees (box-decomposition tree). In addition, we also offer the function to visualize the neighboring relations for 2D points.
Here are two important suggestions from ANN C++ Library's authors:
ANN performs quite efficiently for point sets ranging in size from thousands to hundreds of thousands, and in dimensions as high as 20. (For applications in significantly higher dimensions, the results are rather spotty.)
Computing exact nearest neighbors in dimensions much higher than 8 seems to be a very difficult task. Few methods seem to be significantly better than a brute-force computation of all distances. However, it has been shown that by computing nearest neighbors approximately, it is possible to achieve significantly faster running times (on the order of 10's to 100's) often with a relatively small actual errors. ANN allows the user to specify a maximum approximation error bound, thus allowing the user to control the tradeoff between accuracy and running time.
This MATLAB wrapper is a freeware released with the GNU Lesser General Public License, version 2.1. You can redistribute and/or modify it under the terms of the license.
To install the ANN MATLAB Wrapper into your MATLAB environment, you may follow the instructions below:
ann_compile_mex
If you intend to re-compile the mex file, an ANSI C++ compiler that supports standard C++ is required.
Elaborate help has been provided within each m-function, with sufficient examples to show their usage. In addition, well-formated HTML help of this toolbox is made available in the MATLAB Help Browser. You can readily refer to it by using -doc as the input argument for each function.
All functions in the toolbox are sufficiently documented. There are a variety of ways to get help.
help function_nameto get the help of a specified function. This displays the text help in the command window.
function_name -docto get the help of a specified function in form of HTML Web page. This opens the built-in help browser of MATLAB and shows the help page.
Though the usage of the m-functions is explained in the documentation. However, it is beyond our scope to offer a tutorial on the fundamental knowledge in kd-tree and approximate nearest neighbor searching. To get more information about this, you may refer to the ANN Programming Manual.
Please feel free to write to me via dhlin@mit.edu if you have any questions about the toolbox.