# Efficient Retrieval of Music Recordings Using Graph-Based Index Structures
## 2 Music Retrieval Application
### Cross-Version Retrieval System  
We now describe our retrieval approach, closely following [9]. Given a database of music recordings and a short query audio fragment, the aim is to identify all recordings (versions) in the dataset based on the same musical piece as the query. To this end, we compare the database and query recordings using chroma-based audio features, which measure local energy distributions in the 12 chromatic pitch class bands [31; 32]. Our chroma features are computed by suitably pooling the frequency bins of a time-frequency representation with a logarithmic frequency axis, where a frequency bin corresponds to a semitone [33]. Following [9; 17], we use a chroma variant called CENS (chroma energy distribution normalized statistics) [34], which is adapted for the retrieval task using a post-processing strategy involving logarithmic quantization, temporal smoothing, and frame-wise normalization.  
All database recordings are transformed into chroma sequences. We use a shingling approach [1; 9; 17; 35], where the database's chroma sequences are subdivided into subsequences (also referred to as \"shingles\") of \(L=20\) chroma vectors, using a hop size of \(H=1\) frame. The length of a shingle corresponds to 20 s of audio (using a feature rate of 1 Hz). As for the retrieval, the query (in the form of a single shingle) is compared with all database shingles. Figure 2 illustrates such a query (left) for our Mendelssohn example and the set of overlapping shingles (right) for a database document (a track of a CD from the Carus collection). As the first option to compare two shingles, we reshape each shingle of dimension \(12\times 20\) to a vector of dimensionality \(K=240\) and apply a distance function  
\[d:\mathbb{R}^{K}\times\mathbb{R}^{K}\rightarrow\mathbb{R}_{\geq 0}\,. \tag{1}\]  
Throughout this paper, we use the squared Euclidean distance  
\[d(\mathbf{x}_{1},\mathbf{x}_{2})=\sum_{k=1}^{K}(x_{1}(k)-x_{2}(k))^{2} \tag{2}\]  
between two vectors \(\mathbf{x}_{1},\mathbf{x}_{2}\in\mathbb{R}^{K}\) as the distance function.  
Alternatively, we reduce the dimensionality (\(K<240\)) of the shingles before computing the distance. In particular, following [PERSON] and [PERSON] [9], we use classical PCA [24], or deep neural networks (DNNs) trained with the triplet loss function [36] for dimensionality reduction. The DNN is a convolutional neural network, having a relatively small amount of parameters (e.g., about 6000 parameters for \(K=10\)). The last network layer performs an \(\ell^{2}\)-normalization of the embedding. For more details, we refer to [9]. The authors showed that the shingle dimension can be reduced from 240 to 15 without substantial loss in retrieval quality for the given application (while PCA- and DNN-based embeddings yield similar results). The DNN-based approach is beneficial for even smaller dimensionalities (below \(K=12\)), where we only have a moderate loss in retrieval quality.  
The retrieval task is then solved by finding the database's shingles with the smallest distance to the query shingle, which is a nearest neighbor search problem. [PERSON] and [PERSON] [9] compared the runtimes for this retrieval task using an exhaustive search and a search approach using \(K\)-d trees [12; 13]. Using a small dataset of 16 h of music, they found that \(K\)-d trees are only beneficial for smaller dimensionalities (below \(K=15\)). This finding  
Figure 2: Illustration of shingle-based query and database document.  
agrees with the fact that \(K\)-d trees are inappropriate for high-dimensional data [21, 37]. In our paper, building upon these findings, we want to explore the potential of a graph-based index structure for this music retrieval problem.