Top-K Similarity Search for Query-By-Humming

As an important way of music retrieval, Query-By-Humming has gained wide attention because of its effectiveness and convenience. This paper proposes a novel Top-K similarity search technique, which provides fast retrieval for Query-By-Humming. We propose a distance function MDTW for multi-dimensional sequence matching as well as a subsequence matching method \(MDTW_{sub}\). We show that the proposed method is highly applicable to music retrieval. In our paper, music pieces are represented by 2-dimensional time series, where each dimension holds information about the pitch or duration of each note, respectively. In order to improve the efficiency, we utilize inverted lists and q-gram technique to process music database, and utilize q-chunk technique to process hummed piece. Then, we calculate the MDTW distances between hummed q-chunks and music q-grams, and we can get the candidate music and their sensitive data areas. We proposes TopK-Brute and TopK-LB Algorithm to search the Top-K songs. The experimental results demonstrate both the efficiency and effectiveness of our approach.