A query by humming system based on locality sensitive hashing indexes

Recently developed query by humming (QBH) system, which uses the humming clip to find the wanted song, has become a hot topic in the area of music retrieval. At present, the challenging issue is how to quickly and accurately find the song in a large scale database by an imperfect humming. Although the technique of locality sensitive hashing (LSH) has provided a superior scheme to build an efficient index, the practical implements of the building and searching of the index are still lacking. This paper presents a set of effective algorithms to realize an LSH based QBH system. Specifically, we present an index algorithm of note-based locality sensitive hashing (NLSH), a two-level filtering algorithm of NLSH and pitch-based locality sensitive hashing (PLSH) to screen candidate fragments, an algorithm of boundary alignment linear scaling (BALS) to locate the accurate boundary of candidates and an algorithm named key transposition recursive alignment (KTRA) to tackle the problem of key transposition. The experimental results show that the proposed approach can achieve mean reciprocal rank (MRR) of 0.873 (humming from anywhere) and 0.912 (humming from beginning), which is increased by 0.118 and 0.050, respectively compared with the current state-of-the-art method. (C) 2012 Elsevier B.V. All rights reserved.