# How approximate are “approximate” nearest neighbor (ANN) search algorithms?

Starting to use nanoflann to do some point cloud nearest neighbor searching and it got me thinking about just how "approximate" ANN methods are.

If I have a (more or less) randomly distributed point cloud what is the likelihood that I get the exact nearest neighbor given a target point within the clouds bounding box? I know that it is dataset dependent... but does anyone have a good numerical study somewhere that shows trends?

• Which algorithm(s) are you interested in in particular? Have you done research? (It's unlikely people will dig into some tool documentation for you.) – Raphael May 28 '13 at 6:47

## 1 Answer

nanoflann is a library for building KD-trees. For the best bin first (BBF) approximate nearest neighbor algorithm (which is based on KD-trees), the authors report the following performance results:

In 12 dimensions, for example, BBF recovers the closest neighbor 94% of the time (versus 59% for restricted search) while on average examining only 200 of the 100,000 leaf nodes. For this same case, the “exact” search has to examine over 2400 leaves. [Even] when the method does not discover the exact nearest neighbor, it does not fail by much. Even up to dimension 20, the average distance of recovered neighbors is only 2% greater than the true NN distances.

However, that paper does not contain a formal analysis of the error bounds in this particular $\varepsilon$-approximation.