Timbre Similarity Search with Metric Data Structures

Abstract

Similarity search is essential in music collections, and involves finding all the music documents in a collection, which are similar to a desired music, based on some distance measure. Comparing the desired music to all the music in a large collection is prohibitively slow. If music can be placed in a metric space, search can be sped up by using a metric data structure. In this work, we evaluate the performance of the timbre range query in music collections with 6 metric data structures (LAESA, GNAT, VP-Tree, HDSAT2, LC and RLC) in 2 metric spaces. The similarity measures used are the city-block and the Euclidean distances. The experimental results show that all the metric data structures speeds the search operation, i.e. the number of distance computed in each search process is small when compares to the number of objects in the database. Moreover, the LAESA data structure has the best performance in the two metric spaces used, but the RLC data structure is the only data structure that never degraded its performance and competes with the other metric data structures, in all the experimental cases.