Colloquium Speaker
Speaker:

Prof. Anna Lubiw, School of Computer Science, University of Waterloo 
Topic:

A Geometric Approach to Music Pattern Matching

Date: 
Thursday, February 10, 2005 
Time: 
11:00AM

Place: 
GouldSimpson, Room 701 


Refreshments will be served in the 7th floor lobby of GouldSimpson at 10:45 AM 
Abstract
The music pattern matching problem is to find occurrences of a small fragment of music called the "pattern" in a larger body of music called the "score". String matching approaches have been most thoroughly investigated, but they cannot cope with polyphonic music (where multiple notes are played simultaneously). A geometric interpretation converts the problem to that of translating a set of horizontal line segments in the plane to find the best match in a larger set of horizontal line segments. Our contribution is that we use fairly general weight functions to measure the quality of a match, thus enabling approximate pattern matching. We give an algorithm with running time $O(nm \log m)$, where $n$ is the size of the score and $m$ is the size of the pattern. We show that the problem, in this geometric formulation, is unlikely to have a significantly faster algorithm because it is at least as hard as a basic problem called 3SUM that is conjectured to have no subquadratic algorithm. We present some examples to show the potential of this method for finding minor variations of a theme, and for finding polyphonic musical patterns in a polyphonic score.
For a paper copy, please see:
http://www.cs.uwaterloo.ca/~alubiw/research.html

