Audio Fingerprinting

I am working on a project where I want to identify songs via recording a short snippet of the song.

My thought is to us the Arduino to record a bit of the song (http://apcmag.com/arduino-projects-digital-audio-recorder.htm/) and then use either echoprint (http://echoprint.me) or gracenote(http://www.gracenote.com/music/recognition/) to generate a fingerprint.

I know some people have done this with a Pi but I would really like to see if this is possible to do with Arduino AKA something not running linux. Any thoughts on major blockers? I am thinking if I use an arduino mega I should have enough space to compile the code but not sure if the processor would be able to handle it. Any thoughts or pointers would be a huge help.

Any luck with this? I am interested in the same idea. I was using Echoprint to fingerprint but I could not get the FFT library to fit.

Any thoughts on major blockers?

The poor resolution and slow speed of the Arduino’s analog to digital converter.
The Arduino’s limited memory will severely restrict how many samples you can store.
The relatively slow speed at which you can get data out of the Arduino.