Really? I'd love to know how they do that? Can you _really_ cram a useable sized db of popular music fingerprints into something small enough to store locally on a phone these days?
Using a not particularly efficient but reliable fingerprinting algorithm such as http://www.ismir2002.ismir.net/proceedings/02-FP04-2.pdf, you need 2.6kbits/sec for the fingerprint. Popular songs tend to be short, so lets say 3:30 per song on average. That works out to about 70K per song, or 70MB per 1000 songs. But compression and/or other sorts of encoding cleverness could massively reduce this number. Bottom line is that it wouldn't be hard to store thousands of fingerprints given a few hundred megabytes of storage (out of 64GB or more).
I couldn't find anything which said how big their db is, but you could do some artist/song popularity smarts to figure out the tracks a user is most likely to listen to.
But to constantly be searching through fingerprints for every sound? I'd be interested to see what Googles solution to this may be.
No way you can fit their fingerprints and the metadata into 64GB, compressed or not.
Shazam has 40M fingerprints in their DB, and they definitely don't have everything. Their software runs on beefy servers.
That won't satisfy the jazz nerd's needs, but they probably know their entire catalog by heart anyway.
This is just passive recognition which can have much less coverage since you aren't relying on it.