[Problems of Control and information Theory vol. 20, no. 6, 1991,
pp. 383-395]
Nearest neighbor search and classification in O(1) time
András Faragó, Tamás Linder and Gábor Lugosi
Abstract
A method of finding the nearest neighbor is
presented. The effectiveness of the algorithm has been shown in
computer simulations. This paper gives a probabilistic analysis of the
performance. The algorithm is shown to have an $O(1)$ expected
asymptotic complexity, measured in the number of distance calculations
for $n$ sample points. A reduced complexity classification rule is
derived which has the same error probability as the nearest neighbor
discrimination rule.