Fast nearest-neighbor searching for nonlinear signal processing

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.