No idea but I'd guess instead of simply comparing the received signal with an internal database of time domain signals, one's database is split into different c

No idea but I'd guess instead of simply comparing the received signal with an internal database of time domain signals, one's database is split into different categories (according to certain features). So you could then quickly go down a tree of options until you end up a song with the most similar ones (features). The unique combination of features would make up the "acoustic fingerprint" they're talking about. That's probably too obvious though I'd imagine there's something else going on as well.