# Efficient Retrieval of Music Recordings Using Graph-Based Index Structures
## 4 Experiments
### Constructing, Saving, and Loading the Index  
We now address various performance measures for the offline stage, i.e., for constructing, saving, and loading the index structures. For these steps, we restrict our analysis to one embedding technique (PCA) because the specific embedding strategy used has only a minor influence on these measures. The first step is to construct the index structure (either a \(K\)-d tree or an HNSW graph). We report on the times required to construct the index, given that the data to be indexed is already in the computer's main memory (i.e., pre-computed shingle embeddings, without having any distances pre-computed). When this data needs to be read from disk, it will cause some additional overhead. For example, loading all pre-computed shingle embeddings (\(K=12\)) of \(\mathbb{D}_{\text{sm}}\) takes 0.9 ms on average. Loading the full shingles (\(K=240\)) of \(\mathbb{D}_{\text{lg}}\) requires one second on average. Columns 4 and 5 of Table 5 show the time needed to construct the index structures for various dimensionalities. We include time measurements for the smaller dataset \(\mathbb{D}_{\text{sm}}\) and the larger dataset \(\mathbb{D}_{\text{lg}}\). The first row in the table refers to the \(K\)-d tree index for shingles without dimensionality reduction (\(K=240\)). This setting leads to construction times of 0.54 s for \(\mathbb{D}_{\text{sm}}\) and 43.03 s for \(\mathbb{D}_{\text{lg}}\). For lower dimensions, this time decreases. For example, constructing the \(K\)-d tree index for \(\mathbb{D}_{\text{lg}}\) takes 3.89 s, 1.66 s, and 0.99 s for the dimensionalities of 30, 12, and 6, respectively. Constructing an HNSW graph for \(K=240\) requires 0.65 s for the smaller dataset \(\mathbb{D}_{\text{sm}}\) and 26.66 s for the larger dataset \(\mathbb{D}_{\text{lg}}\). For this large dataset and a high dimensionality of \(K=240\), constructing an HNSW graph is faster (26.66 s) than constructing a \(K\)-d tree (43.03 s) in the implementations used. However, this is not the case for lower dimensions. For example, constructing the index structures for the larger dataset \(\mathbb{D}_{\text{lg}}\) using \(K=30\) requires 3.89 s for the KD and 16.38 s for the HNSW approach. In general, the construction time grows approximately in a linear fashion with the dimensionality \(K\) for lower dimensions. Only for large dimensionalities, the time for constructing a \(K\)-d tree explodes, which agrees with the fact that \(K\)-d trees are not suited for high-dimensional data [21, 37]. In contrast, the HNSW approach behaves stable for all considered dimensionalities. In all our settings, constructing an index takes less than a \begin{table}
\begin{tabular}{c c} \hline \hline
**Step** & **Time (ms)** \\ \hline Audio Loading & \(44.8\pm 1.4\) \\ Spectral Feature Computation & \(1171.5\pm 34.3\) \\ CENS Feature Computation & 0.9 \(\pm\) 0.5 \\ \hline Embedding PCA (\(K=30\)) & 0.05 \(\pm\) 0.0 \\ Embedding PCA (\(K=12\)) & 0.05 \(\pm\) 0.0 \\ Embedding PCA (\(K=6\)) & 0.05 \(\pm\) 0.0 \\ \hline Embedding DNN (\(K=30\)) & 1.6 \(\pm\) 0.1 \\ Embedding DNN (\(K=12\)) & 1.5 \(\pm\) 0.1 \\ Embedding DNN (\(K=6\)) & 1.4 \(\pm\) 0.1 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Time measurements (in ms) for various steps involved in the feature computation of 20 s of audio. minute. We do not consider this duration critical in our application because the step is performed offline. The next step is to save the index structure to the hard disk, where it requires disk space. In the case of the \(K\)-d tree, we use scikit-learn's [41] recommended default persistence format based on the Python package joblib without compression. In the case of the HNSW graph, we use the default storage format of hnswlib, which is a custom binary format (also without compression). Columns 6 and 7 of Table 5 show the required disk space used for storing the index structures.