[pedalpete]

You don't need then entire song for a fingerprint, and the MusicBrainz (MetaBrainz) project has long been supported by Google.

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.