Roy, P., Aucouturier, J.-J., Pachet, F. and Beurive, A.
Exploiting the Tradeoff Between Precision and Cpu-time to Speed Up Nearest Neighbor Search.
Proceedings of the International Conference on Music Information Retrieval,
pages 230-237,
September
2005
London, UK

Sony CSL authors: Jean-Julien Aucouturier, Anthony BeurivĂ©, FranĂ§ois Pachet, Pierre Roy

### Abstract

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

Keywords: Timbre, Similarity, Algorithm

### Downloads

Adobe Acrobat PDF file

### BibTeX entry

@INPROCEEDINGS { roy:05b,
AUTHOR="Roy, P. and Aucouturier, J.-J. and Pachet, F. and Beurive, A.",
BOOKTITLE="Proceedings of the International Conference on Music Information Retrieval",
MONTH="September",
ORGANIZATION="London, UK",
PAGES="230-237",
TITLE="Exploiting the Tradeoff Between Precision and Cpu-time to Speed Up Nearest Neighbor Search",
YEAR="2005",
}