Approximate lower-bounding functions for the speedup of DTW for melody recognition

Conventional methods for melody recognition (or the so-called query by humming) are primarily based on dynamic programming, such as dynamic time warping (DTW). However, the computation load of DTW becomes prohibitively massive when the database has more than, say, 10,000 songs. To lessen the computation while keeping a reasonable recognition rates, this paper present a lower-bound based method that can reduce the computation effectively.