TSTOOL home page | TSTOOL documentation page | TSTOOL link page |

Approximate nearest neighbors algorithms report neighbors to the query point **q** with
distances
possibly greater than the true nearest neighbors distances. The maximal allowed relative error *epsilon*
is given as a parameter to the algorithm. For *epsilon*=0, the approximate search returns the true (exact) nearest
neighbor(s).

Computing exact nearest neighbors for data set with *fractal dimension* much higher than 6
seems to be a very time-consuming task. Few algorithms seem to perform
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 execution times with relatively small actual errors in the reported distances.

Copyright © 1997-2009 DPI Göttingen