Fast nearest-neighbor searching for nonlinear signal processing

A fast algorithm for exact and approximate nearest-neighbor searching is pr esented that is suitable for tasks encountered in nonlinear signal processi ng. Empirical benchmarks show that the algorithm's performance depends main ly 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 em bedded. We also compare the running time of our algorithm with those of two previously proposed algorithms for nearest-neighbor searching.