Complexity analysis for partitioning nearest neighbor searching algorithms
Pierre Zakarauskas, John M. Ozard · IEEE Transactions on Pattern Analysis and Machine Intelligence · 1996
Presents cost estimates for finding the k-nearest neighbors to a test pattern according to a Minkowski p-metric, as a function of the size of the buckets in partitioning searching algorithms. The asymptotic expected number of operations to find the nearest neighbor is presented as a function of the average number of patterns per bucket n and is shown to contain a global minimum.