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

[PDF] 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", }