pitch and span to normalize the key and tempo. These
relative-value sequences are then transmitted to the
server.
After receiving the relative-value sequences, the server executes a matching process. It compares the input sequences with relative-value sequences for each
database melody by using the database index that the
server generated in advance. The titles of the corresponding melodies are then ranked based on the distance calculated by the matching process.
Finally, the list of ranked titles is transmitted to the
client system.
2.2 Indexing Method
The most important process is a matching process
which uses the melody database index. The results of
our estimations, presented in section 6.3, showed that
it is quite difficult to reduce the retrieval time without
indexes.
Traditional text-matching method such as sorting,
hashing, or n-gram often use the first character of an input query to reduce the retrieval space and time. Those
matching method, however, can not be easily applied
to melody matching. A user's input melody consists
of various errors and even the first note in the input is
uncertain.
To solve this problem, we propose an effective matching for generating a melody database index. In this
"short DP matching", the distance between two melody
sequences is calculated by comparing short parts of each
sequence with each other.
3 Normal DP Matching
This section describes a normal DP matching method
and the problem in applying it for indexing melody sequences.
3.1 Overview
assumed to take the integer set represented by C, and
the penalty between elements Q and S is represented
by d.
Q
S
d(qi, sj)
= qo, ql,..., qI-1, qi E C
= So, Si, S2,.., SJ-1, Sj E C
= qi - sj: penalty between qi and sj. qi, sj E C
Under these assumptions, D is calculated as follows.
* Step A
m(O,j) = d(qo, sj), where 0 < j < J.
* Step B
m(i,0) =
* Step C
m(i,j) =
1), m(i,j
oo, where 0 < i < I.
d(qi, s) + min(m(i -, j), m(i - 1,j -
-1)), where 1 < i<Iand 1 < j<J.
* Step D
D(Q, S) = min{m(l - 1,) 11 < j < J}
3.2 Problems
As shown in the Fig. 2, DP matching takes O(I * J)
calculation time for a database melody and a lot of time
is needed for the entire database melodies. To solve this
problem, several approaches that utilize DP matching
can be thought as follows.
1. An approach which assumes that the user sings the
melody from one of only a few points in the piece
of music. This method omits retrieval space by
calculating only limited parts of a melody in using
DP matching [Kageyama et al., 1993].
2. An approach which executes DP matching with al1 input patterns against the database in advance.
This approach uses the matching results when a
user inputs a query and quickly obtains the list of
ranked music titles without calculation.
These methods, however, respectively has the following problems.
1. It is difficult to set the adequate points on each
database melody because the limiting points are
hard to identify.
2. DP matching for a large database took enormous
retrieval time even for one time retrieval and it
was difficult to calculate matching distances for all
input patterns.
As explained in the next section, our short DP matching method overcomes these problems.
Database Sequence...J-1
m(ij)
0)
o 6
Q<) 1
I 2
0)
I-1
0 1 2
A
B C
- D
Figure 2: DP matching.
In normal DP matching, a DP matching matrix,
m(i,j) like that illustrated in Fig. 2, is used to obtain distance D between sequence Q, with length I,
and sequence S, with length J. Elements Q and S are
0
