Abstract
The goal of this thesis is to improve the speed of our CBMR (content-based music retrieval) system, which was developed by previous labmates. Because the CBMR system retrieves songs based on the user’s acoustic input, the tradeoffs between speed and accuracy are two important factors in determining the system’s overall performance. The new CBMR system is developed in C++ language, which is much faster than the old one developed in MATLAB. Moreover, the new system uses some data structure and pre-processing techniques to accelerate the computing speed of retrieval without losing too much accuracy.This system compares songs based on their melodies, so users can query songs by acoustic input directly. Every template song in the database is a vocal (or melody) track extracted from a MIDI file. The system first sequentially compares the input pitch vector with that of each song in the database, and then generates a song list ranked by the similarity scores.We have tried several speedup methods for nearest neighbor search in our research. Not all of them were suitable for our CBMR system. After many trials and errors, we finally found two methods to improve our system. First, we use linear scaling method to implement two-level comparison. Second, we use equal-average hyperplane partitioning method to accelerate whole-song comparison. Currently there are about 8500 songs in the database. On a Pentium PC of 800 MHz, our new CBMR system takes about 0.5 second to do a “match beginning” search, and about 12 seconds to do a “match anywhere” search.