# ANN MATLAB Wrapper (ver 1.2) Readme

Dahua Lin, on Aug 10, 2007

## Introduction

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.

## Installation

To install the ANN MATLAB Wrapper into your MATLAB environment, you may follow the instructions below:

1. Unzip the package to any place that you like;
2. Enter MATLAB Environment;
3. Add the directory path to MATLAB
4. The core function is based on C-MEX files. The downloaded package includes the pre-compiled mex file for MATLAB R2007a. If you are in a lower MATLAB version, you may need to re-compile the mex file by ann_compile_mex

If all steps go well, you can now start using it.

If you intend to re-compile the mex file, an ANSI C++ compiler that supports standard C++ is required.

## Get Help

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.

- Type in help function_name to get the help of a specified function. This displays the text help in the command window.
- Type in function_name -doc to 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.

## Version History

- Version 1.2 (2007-08-10)
  - Fix a bug that leads to crash by invalid memory accessing
  - Add the annquery_demo.m
- Version 1.0 (2007-07-01)
  - The first released version
  - Based on ANN C++ Library 1.1.1

Copyright © 2007 Dahua Lin. All rights reserved.