Geometric Algorithms for Transposition Invariant Content-Based Music Retrieval
Esko Ukkonen, Kjell Lemström and Veli Mäkinen
We represent music as sets of points or sets of horizontal line segments in
the Euclidea plane. Via this geometric representation we cast transposition
invariant content-based music retrieval problems as ones of matching sets of points
or sets of horizontal line segments in the plane under translations. For finding the exact occurrences
of a point set (the query pattern) of size m within another point set (representing
database) of size n, we give an algorithm with running time O(mn), and for
finding partial occurrences, another algorithm with running time O(mn log m).
We also use the total length of the overlap between the line segments of a
translated query and a database (i.e., the shared time) as a quality measure of
an occurrence and present an O(n log n+mn log m) algorithm for finding
translations giving the largest possible overlap. Some experimental results on the
performance of the algorithms are reported.