According to Shazam Paper[1] (I can't find publication date), there were nothing fancy, just keypoints extraction on spectrogram. No deep learning with 100 layers or something like that which wouldn't be possible in 2000.

[1] https://www.ee.columbia.edu/~dpwe/papers/Wang03-shazam.pdf