Exploiting the Tradeoff Between Precision and Cpu-time to Speed Up Nearest Neighbor Search

摘要: We describe a recursive algorithm to quickly compute the N nearest neighbors according similarity measure in metric space. The exploits an intrinsic property of large class measures for which some parameter p has positive influence both on precision and cpu cost (precision-cputime tradeoff). uses successive approximations first cheap distances whole set possible items, then more expensive smaller sets. illustrate case timbre algorithm, compares gaussian mixture models using Monte Carlo approximation Kullback-Leibler distance, where is number points drawn from distributions. several algorithmic variants, improve convergence speed approximation. On this problem, performs than 30 times faster naive approach.