<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T18:05:21Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/1132" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/1132</identifier><datestamp>2017-03-21T19:23:10Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9930</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author" lang="en" authority="cd9aa7ce-e263-44cb-a3b4-e27ac4f531d4" confidence="600">Tanur, Luke</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2006-08-22T14:21:06Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2006-08-22T14:21:06Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued" lang="en">2005</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted" lang="en">2005</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/1132</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">The music pattern matching problem involves finding matches of a small fragment of music called the &amp;quot;pattern&amp;quot; into a larger body of music called the &amp;quot;score&amp;quot;.   We represent music as a series of horizontal line segments in the plane, and reformulate the problem as finding the best translation of a small set of horizontal line segments into a larger set of horizontal line segments.   We present an efficient algorithm that can handle general weight models that measure the musical quality of a match of the pattern into the score, allowing for approximate pattern matching.      
We give an algorithm with running time &amp;lt;em&amp;gt;O&amp;lt;/em&amp;gt;(&amp;lt;em&amp;gt;nm&amp;lt;/em&amp;gt;(&amp;lt;em&amp;gt;d&amp;lt;/em&amp;gt; + log &amp;lt;em&amp;gt;m&amp;lt;/em&amp;gt;)), where &amp;lt;em&amp;gt;n&amp;lt;/em&amp;gt; is the size of the score, &amp;lt;em&amp;gt;m&amp;lt;/em&amp;gt; is the size of the pattern, and &amp;lt;em&amp;gt;d&amp;lt;/em&amp;gt; is the size of the discrete set of musical pitches used.   Our algorithm compares favourably to previous approaches to the music pattern matching problem.   We also demonstrate that this geometric formulation of the music pattern matching problem is unlikely to have a significantly faster algorithm since it is at least as hard as 3SUM, a basic problem that is conjectured to have no subquadratic algorithm.   Lastly, we present experiments to show how our algorithm can find musically sensible variations of a theme, as well as polyphonic musical patterns in a polyphonic score.</dim:field>
   <dim:field mdschema="dc" element="format" lang="en">application/pdf</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="extent">1021022 bytes</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="mimetype">application/pdf</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="rights" lang="en">Copyright: 2005, 
  Tanur, Luke. All rights reserved.</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Computer Science</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">music information retrieval</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">algorithms</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">geometry</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">A Geometric Approach to Pattern Matching in Polyphonic Music</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Master Thesis</dim:field>
   <dim:field mdschema="dc" element="pending" lang="en">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">School of Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Master of Mathematics</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>