P. Zakarauskas et Jm. Ozard, COMPLEXITY ANALYSIS FOR PARTITIONING NEAREST-NEIGHBOR SEARCHING ALGORITHMS, IEEE transactions on pattern analysis and machine intelligence, 18(6), 1996, pp. 663-668
In this paper we present cost estimates for finding the k-nearest neig
hbors to a test pattern according to a Minkowski p-metric, as a functi
on of the size of the buckets in partitioning searching algorithms. Th
e asymptotic expected number of operations to find the nearest neighbo
r is presented as a function of the average number of patterns per buc
ket n and is shown to contain a global minimum.