Exploiting the Tradeoff Between Precision and CPU Time to Speed Up Nearest Neighbor Search

By Pierre Roy, Jean-Julien Aucouturier, François Pachet, and Anthony Beurivé.

In the Proceedings of the 6th International Conference on Music Information Retrieval (ISMIR 2005), pp. 230–237, London, 2005.

Read the paper (PDF)

About the paper

Searching a large music catalog for similar tracks can be slow when each comparison is expensive. This paper examines how to use multiple levels of precision to speed up nearest-neighbor search.

Abstract summary

The method starts with inexpensive estimates across the catalog and uses more expensive comparisons on progressively smaller candidate sets. The authors illustrate the technique with a timbre similarity measure whose precision depends on the number of Monte Carlo samples.

Related work

See Timbre Similarity and Hubness for the catalog browsing research and Finding Songs That Sound the Same for the similarity method.

Back to Publications