According to a friend who works at Google, they only store a catalog of ~20k popular songs that updates periodically. Fingerprints are small, so an archive of that size isn't too big.