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

Next: 4.3 Range searching Up: 4. Nearest Neighbors Searching Previous: 4.1 Definition

# 4.2 Approximate nearest neighbors searching

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.