How does music fingerprinting work (for sites such as Shazam and Lala.com)?

Question

My large (120gb) music collection contains many duplicate songs, and I've been trying to fingerprint tracks in the hopes of detecting duplicates. And since I'm a CS Major I'm very curious as to what is done out there? Nothing I do has nearly the accuracy of something like Shazam or Lala.com. How do they "hash" tracks? I have run a standard MD5 hash on all my files (26,000 files) and I found hundreds of equal hashes on different tracks, so that doesn't work.

I'm more interested in Lala.com since they work with full files, unlike Shazam, but I'm assuming both use a similar technique. Can anyone explain how to generate unique identifiers for music?

Answer 1

The seminal paper on audio fingerprinting is the work by Haitsma and Kalker in 2002-03. For each frame of audio, it preprocesses (differences across time frames and frequency bands) and then stores a binarized version of the frame's spectrum.

This procedure adds robustness. If the entire signal is shifted in time, it still works (at least, one can derive a lower bound on performance degradation). It is pretty robust to environmental noise. Since its inception, there have been many papers on low-level music similarity, so there is no single answer.

Do you have absolutely identical files, i.e., the signals are time aligned, bit depth is the same, sampling rate is the same? Then I would think a hash like MD5 should work. But if any of those parameters are changed, so will the hashes. In such an event, a procedure like the one mentioned earlier would work better.

Take a look at the ISMIR proceedings available free online. Fun stuff. http://www.ismir.net/

Answer 2

There are a lot of algorithms for acoustic fingerprinting. Some of the more popular ones are:

1. AMG LASSO
2. AudioID
3. LibFooID

In fact libfooId is opensource , so you can check out its code in google-code!!

Answer 3

Take a look at he Acoustic Fingerprint page on Wikipedia. It has references for some papers as well as links to implementations (including the open source fdmf).

Answer 4

After some more research (although this is not conclusive at all!), I happened across the wiki at MusicBrainz.org which details some of the approaches they use:

http://musicbrainz.org/doc/Audio_Fingerprint

http://musicbrainz.org/doc/How_PUIDs_Work