FAST NEAREST-NEIGHBOR SEARCH IN DISSIMILARITY SPACES

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.