An Industrial-Strength Audio Search Algorithm
📜 Abstract
We have developed and commercially deployed a flexible audio search engine. The algorithm is noise and distortion resistant, computationally efficient, and massively scalable, capable of quickly identifying a short segment of music captured through a cellphone microphone in the presence of foreground voices and other dominant noise, and through voice codec compression, out of a database of over a million tracks. The algorithm uses a combinatorially hashed time-frequency constellation analysis of the audio, yielding unusual properties such as transparency, in which multiple tracks mixed together may each be identified. Furthermore, for applications such as radio monitoring, search times on the order of a few milliseconds per query are attained, even on a massive music database.
✨ Summary
The paper describes the audio-fingerprinting system developed and commercially deployed by Shazam. It represents audio as a sparse constellation map of robust spectrogram peaks, discarding amplitude information to reduce sensitivity to equalization and other filtering. Nearby peaks are paired within target zones to form compact hashes containing two frequency coordinates and their temporal separation. These hashes are indexed with track and time-offset information, allowing a query to retrieve candidate matches efficiently from a large database.
Candidate tracks are scored by examining whether matched hashes share a common time offset. A genuine match produces a concentrated peak in the offset histogram, whereas accidental hash collisions are dispersed. This provides a computationally inexpensive alternative to more general geometric-registration methods and supports rapid rejection of false matches. The system is designed to balance hash entropy, robustness, storage overhead, recognition probability, and false-positive thresholds.
The reported experiments show recognition under substantial additive noise, GSM compression, dropouts, voice interference, and mixtures of multiple tracks. For the tested 10,000-track database, 50% recognition occurred at approximately −9, −6, and −3 dB signal-to-noise ratio for 15-, 10-, and 5-second samples without GSM compression; with GSM compression, the corresponding levels were approximately −3, 0, and +4 dB. Reported search times ranged from roughly 5–500 milliseconds for a 20,000-track database, with radio-quality queries taking less than 10 milliseconds under suitable settings.
The work became a foundational reference for spectral-peak audio fingerprinting. Later music-information-retrieval teaching materials present its peak-based constellation approach as a widely used audio-identification method, and subsequent fingerprinting systems—including open implementations and research on robust retrieval—explicitly reproduce or build on its constellation maps, pairwise hashes, and time-offset voting strategy. (audiolabs-erlangen.de) The paper is bibliographically identified as an ISMIR 2003 conference paper by independent scholarly indexes, with the conference publication dated October 27, 2003. (dblp.org)