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

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