Fast k-nearest-neighbours searching through extended versions of the approximating and eliminating search algorithm (AESA)
Alfons Juan, Enrique Vidal, Pablo Aibar · 2002
The approximating and eliminating search algorithm (AESA) is probably the technique requiring the fewest distance computations for nearest-neighbour searching in general metric spaces. In this paper we propose direct and refined extensions to the AESA for finding k-nearest-neighbours. Results of a number of experiments involving synthetic data are reported, showing that both extensions, and especially the last one, lead to computational savings similar to that of the original (1-NN) AESA.