A fast algorithm for music search by similarity in large databases based on modified Symetrized Kullback Leibler Divergence

State of the art on music similarity search is based on the pairwise comparison of statistical models representing audio features. The comparison is often obtained by the Symetrized Kullback-Leibler Divergence (SKLD). When dealing with very large databases (over one million items), usual search by similarity algorithms - sequential or exhaustive search - cannot be used. In these cases, optimized search strategies such as the M-tree reduces the search time but requires the dissimilarity measure to be a metric. Unfortunately, this is not the case of the SKLD. In this paper, we propose and successfully test on a large-scale a modification of the Symetrized Kullback-Leibler Divergence which allows to use it as a metric.