A FILTER-AND-REFINE INDEXING METHOD FOR FAST SIMILARITY SEARCH IN MILLIONS OF MUSIC TRACKS

摘要: We present a filter-and-refine method to speed up acoustic audio similarity queries which use the Kullback-Leibler divergence as measure. The proposed rescales and uses modified FastMap [1] implementation accelerate nearest-neighbor queries. search for similar music pieces is accelerated by factor of 10 30 compared linear scan but still offers high recall values (relative scan) 95 99%. show how can be used query several million songs their neighbors very fast while producing almost same results that over whole database would return. working prototype able process on 2:5 collection in about half second standard CPU.