Fast nearest-neighbor searching for nonlinear signal processing

Abstract

A fast algorithm for exact and approximate nearest-neighbor searching is presented that is suitable for tasks encountered in nonlinear signal processing. Empirical benchmarks show that the algorithm's performance depends mainly on the (fractal) dimension D(d) of the data set, which is usually smaller than the dimension D(s) of the vector space in which the data points are embedded. We also compare the running time of our algorithm with those of two previously proposed algorithms for nearest-neighbor searching.