VP-tree based multi-stage matching algorithm for query-by-humming systems

Query by humming (QBH) is an important application for musical information retrieval. The key challenges in QBH are the unstructured data modules in audio songs and the balance between searching speed and accuracy. This paper presents a data structure for audio songs using a hand labeling method to label the melody and to divide the songs into natural segments. The search index uses the segmentation structure rather than the entire lyrics for the song. The system generates a VP-tree search structure with a multi-level searching algorithm that includes coarse searching for fast match and dynamic time warping (DTW) that leads to a fine match. Evaluations with 2 213 melody segments reduce the search time by over 40% without greatly reducing the recognition accuracy.