A WWW-based Melody-Retrieval System
- An Indexing Method for A Large Melody Database -
Tomonari Sonoda and Yoichi Muraoka
School of Science and Engineering, Waseda University
3-4-1 Ohkubo Shinjuku-ku, Tokyo 169-8555, Japan.
sonoda@muraoka.info.waseda.ac.jp, muraoka@muraoka.info.waseda.ac.jp
ABSTRACT:
This paper describes an indexing method for a WWW-based melody-retrieval system, takes a melody sung by a user
as a search clue and sent over the Internet and uses it to retrieve the song's title from a large database. In previous
works, it was difficult to reduce the melody-retrieval time since it was difficult to make indexes for melody sequences.
We therefore propose an efficient indexing method which is based on DP (dynamic-programming) matching. Testing
of our method against a database containing about 10,000 melody sequences showed that its retrieval time is about
1/1,000 that without an index and that its matching is highly accurate.
1 Introduction
A WWW-based melody-retrieval system that takes a
melody sung by a user as a query requires a robust
matching method that can quickly and accurately identify the desired melody in a large database.
The biggest challenge to developing such a method is
creating an index of the melody sequences that reduces
the retrieval time to an acceptable level. Because several notes in the input melody, including even the first
note, will likely be wrong, it is difficult to apply general
indexing methods, such as sorting or hashing. It was
also difficult to build a WWW-based melody-retrieval
service without utilizing an database index since the
system can not process a lot of network accesses at a
time.
Previous systems [Kageyama et al., 1993, Sonoda et
al., 1998] utilized DP matching to calculate the distance
between a user's input melody and each melody in a
database when the input melody does not completely match a database melody. DP matching, however,
requires a long time to complete its calculations.
We propose an effective indexing method which takes
advantage of DP matching and reduces the retrieval
time. In this method, if the distance calculated by DP
matching for two long melody sequences is close, there
is assumed to exist similar shorter sequences in those
two sequences and the shorter sequences are used for
indexing.
Testing of our method against a database containing
about 10,000 melody sequences showed that its retrieval
time is about 0.78 seconds, about 1/1,000 that without
an index. Its matching accuracy was highly accurate,
about 92% for 120 inputs from 12 different people. This
level is high enough for a melody-retrieval over the Internet.
2 WWW-based
Melody-Retrieval System
This section describes the overview of our system and
proposes a method for indexing melody sequences.
2.1 Overview
Clients
user A/D
ur " IcA/oversion extraction of
( conversion pitch / span of
(Q _matching 1 notes
relativeWWW sequeces of
Server pitch/span
database index
[ -fa -r matching
Figure 1: Melody-retrieval system with a large
database.
Our current system differs from the one we proposed
in 1998 [Sonoda et al., 1998]. As shown in Fig. 1, our
current system consists of a melody-retrieval server and
user-side client for use by a Netscape Plug-in or a JAVA
applet. The server has a database consisting of standard MIDI file (SMF) data and melody data generated
by singing and an index of the database.
A user inputs a melody by singing from an any part of
a piece of music. The key and tempo can be arbitrarily
chosen. The client system assumes that each input note
begins with a voiceless consonant and ends with a vowel
(e.g. ta-ta-ta).
After A/D conversion, the client extracts sequences
of pitch and span of notes from the input. These sequences are converted into relative-value sequences of
0
