Query-by-humming: a time series subsequence matching approach

Abstract:
Suppose you hear a song but you cannot recall its name; one solution is to hum a short part of the song and
perform a search on a large music repository to find the song you are looking for or even songs with similar melody.
The main task of a Query-By-Humming (QBH) system is, given a hummed query song, to search a music database for the
K most similar songs.

In this talk, I will show how the above problem can be solved using subsequence matching.  Each song can be mapped to a time series while the hummed query can be typically seen as a very small part of the target sequence. A novel subsequence matching framework has been proposed that allows for gaps in both the query and target sequences, variable matching tolerance levels efficiently tuned for each query and tar
get sequence, and also constrains the maximum match length. Using this framework, a space and time efficient dynamic programming
method has been developed: given a short query sequence and a large database, the method identifies the subsequence of the database
that best matches the query, and further bounds the number of consecutive gaps in both sequences. In addition, it allows the user to
constrain the minimum number of matching elements between a query and a database sequence. We show that the proposed method
is highly applicable to music retrieval. Music pieces are represented by 2-dimensional time series, where each dimension holds information about the pitch and duration of each note, respectively.  At runtime, the query song is transformed to the same 2-dimensional representation. Experiments have been performed on synthetic and real hummed queries, where the described method outperforms existing dynamic programming methods and an HMM-based approach.

Bio:
Dr. Panagiotis Papapetrou is lecturer (equivalent to tenure-track assistant professor) at the Department of Computer Science and Information Systems at Birkbeck, University of London, since September 2012. He is also director of the Information Technologies Applications Programme within the same institution. Panagiotis was a post-doctoral researcher at the Department of Information and Computer Science at Aalto University, from September 2009 until August 2012.  He received his Bachelor's degree from the Department of Computer Science at the University of Ioannina, Greece in 1999, and both Master's and Ph.D. degrees from the Department of Computer Science at Boston University, USA. His research interests are concentrated within the areas of algorithmic data analysis, indexing complex data, time series and symbolic sequence analysis, and algorithmic methods for bibliometrics. He is regular PC member for SIGKDD, ICDM, ECML-PKDD, CIKM, and others.