A. Farago et al., FAST NEAREST-NEIGHBOR SEARCH IN DISSIMILARITY SPACES, IEEE transactions on pattern analysis and machine intelligence, 15(9), 1993, pp. 957-962
A fast nearest-neighbor algorithm is presented. It works in general sp
aces where the known cell (bucketing) techniques cannot be implemented
for various reasons, such as the absence of coordinate structure and/
or high dimensionality. The central idea has already appeared several
times in the literature with extensive computer simulation results. Th
is paper provides an exact probabilistic analysis or this family of al
gorithms, proving its O(1) asymptotic average complexity measured in t
he number of dissimilarity calculations.