[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.