Identical audios may look quite differently in time and frequency domain because of various codecs, bit rates or transferring channels. Audio identification is needed for many scenarios. An enhanced audio fingerprint is proposed based on Haitsma’s approach whose robustness is improved significantly. A Beam-based search approach is also presented in this paper which prunes unpromising branches as early as possible in order to achieve high search efficiency.