A Re-ordering Strategy for Accelerating Index-based Audio Fingerprinting

Abstract

The Haitsma/Kalker audio fingerprinting system has been in use for years, but its search algorithm’s scalability has not been researched very well. In this paper we show that by simple re-ordering of the query fingerprint’s sub-prints in the index-based retrieval step, the overall search performance can be increased significantly. Furthermore, we show that combining longer fingerprints with re-ordering can lead to even higher performance gains, up to a factor of 9.8. The proposed re-ordering scheme is based on the observation that sub-prints, which are elements of n-runs of identical consecutive sub-prints, have a higher survival rate in distorted copies of a signal (e.g. after mp3 compression) than other sub-prints.