Indexing Musical Sequences in Large Datasets Using Relational Databases

Introduction

In this paper, we present compact and efficient models that index data sequences and retrieve continuations and the longest repeated suffix (LRS) for a query using relational databases. Multimedia data, such as music recordings, are sequences of events recorded over time. In the existing information retrieval and recommendation systems, the processing of such data is often song-based (Mandel & Ellis, 2005). Each song is indexed by its meta-data, such as artist name and song title, or by the overall acoustic features summarized for the entire duration of the song (Levy & Sandler, 2009; Lops et al., 2011). The details, such as the order of the note events, are excluded. This approach is sufficient to search for songs by artist name and to recommend songs based on similarity between other songs with certain features. However, tasks such as modeling compositional styles (Chuan & Chew, 2011; Cope, 2001; Dannenberg et al., 1994) and automatic music generation (Eigenfeldt & Pasquier, 2009) require note-level indexing and retrieval. Consider a system that supports interactive music playing, i.e., a system that mimics a jazz musician improvising with the user). This kind of systems must be able to retrieve all suitable note sequences so that it can quickly respond and continue the music stream.

Several computer systems have been proposed for interactive music playing and creation. For example, Continuator (Pachet, 2002) captures the musical sequence played by a musician and responds by playing another musical sequence that imitates the style in the original sequence. Assayag and Dubnov (2004) use variable Markov models and factor oracles to generate improvisation in real time. A more recent extension using variable Markov oracles has been used to discover clustering patterns in audio and to recognize 3D gestures (Wang & Dubnov, 2014). However, these systems focus only on the incoming data stream during a particular time, and the data stream is stored in memory for processing. Therefore, these proposed algorithms and data structures cannot be easily scaled up when the multimedia data or their indexing structure exceeds the memory size. As the volume of information continues to grow at an astonishing rate in the digital era, it becomes imperative to study and improve the scalability of existing algorithms and to propose new approaches to solve old problems.

Several limiting factors should be considered when studying how an algorithm can scale up for large datasets. The most prominent element is efficiency, or the time it takes for the algorithm to search and retrieve the result. Other elements, such as memory limitations, can prevent a linear-time algorithm from being useable if the algorithm requires the entire structure to be stored in memory. The ability to distribute an algorithm to many computation units and storage nodes can also affect scalability.

In this study, we proposed algorithms that extend the models using prefix trees and factor oracles for indexing data sequences in relational databases. Although NoSQL databases may be more suitable for storing data sequences, we focused on relational databases in this study because of their popularity and wide adoption. We improved the prefix tree–based model by reusing existing sub-trees to create compact representations and by creating compound hash digests for fast retrievals. We also proposed an efficient search algorithm to retrieve and validate all matches in factor oracles. We evaluated the search time of our models by comparing them with the file-scan algorithm using textual data from Wikipedia. We also applied the model to music stylistic analysis by identifying continuations and approximating similarity using the LRS for musical data in MIDI and audio recordings of more than a thousand excerpts of Bach’s and Mozart’s compositions.