# Efficient Retrieval of Music Recordings Using Graph-Based Index Structures
## 4 Experiments
### Retrieval Time  
In this section, we report on our runtime experiments for searching the nearest neighbors in our datasets. Regarding efficiency, these experiments refer to the most critical part of the retrieval pipeline because this step is part of the online stage (where the runtime affects the user experience). An efficient search is of major importance for scalability because, in general, the search runtime scales with the dataset size. The aim of our index structures is to improve the efficiency of this step. We can also consider the complexity of the search approaches from a theoretical perspective (which is not the focus of this paper, being a practice report). The runtime of the full search increases linearly with the dataset size. In other words, its search complexity is in the order of \(O(|\mathbb{D}|)\). The expected search complexity for \(K\)-d trees is in the order of \(O(\log|\mathbb{D}|)\)[13]. However, it is well known [45] that the actual performance may be \begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline \multirow{2}{*}{**Search**} & \multirow{2}{*}{**Reduction**} & \multirow{2}{*}{\(\mathbf{K}\)} & \multicolumn{2}{c}{**Construction Time (s)**} & \multicolumn{2}{c}{**Save Size (MB)**} & \multicolumn{2}{c}{**Load Time (ms)**} \\  & & & \(\mathbb{D}_{\text{sm}}\) & \(\mathbb{D}_{\text{lg}}\) & \(\mathbb{D}_{\text{sm}}\) & \(\mathbb{D}_{\text{lg}}\) & \(\mathbb{D}_{\text{sm}}\) & \(\mathbb{D}_{\text{lg}}\) \\ \hline KD & — & 240 & 0.54 \(\pm\) 0.0 & 43.03 \(\pm\) 0.1 & 209.7 & 5161.2 & 131.5 \(\pm\) 0.4 & 3209.1 \(\pm\) 25.4 \\ KD & PCA & 30 & 0.06 \(\pm\) 0.0 & 3.89 \(\pm\) 0.2 & 27.0 & 664.8 & 17.5 \(\pm\) 0.3 & 405.1 \(\pm\) 8.8 \\ KD & PCA & 12 & 0.03 \(\pm\) 0.0 & 1.66 \(\pm\) 0.1 & 11.3 & 279.4 & 3.5 \(\pm\) 0.1 & 167.0 \(\pm\) 6.9 \\ KD & PCA & 6 & 0.02 \(\pm\) 0.0 & 0.99 \(\pm\) 0.1 & 6.1 & 150.9 & 2.1 \(\pm\) 0.3 & 86.3 \(\pm\) 2.2 \\ \hline HNSW & — & 240 & 0.65 \(\pm\) 0.0 & 26.66 \(\pm\) 0.0 & 53.9 & 1310.9 & 108.1 \(\pm\) 0.4 & 2680.0 \(\pm\) 42.8 \\ HNSW & PCA & 30 & 0.51 \(\pm\) 0.0 & 16.38 \(\pm\) 0.0 & 9.9 & 241.8 & 85.1 \(\pm\) 2.1 & 2095.3 \(\pm\) 6.6 \\ HNSW & PCA & 12 & 0.43 \(\pm\) 0.0 & 11.58 \(\pm\) 0.0 & 6.2 & 150.2 & 82.9 \(\pm\) 0.4 & 2071.5 \(\pm\) 43.8 \\ HNSW & PCA & 6 & 0.42 \(\pm\) 0.0 & 10.20 \(\pm\) 0.0 & 4.9 & 119.6 & 82.6 \(\pm\) 0.6 & 2049.1 \(\pm\) 22.8 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Performance measures for constructing, saving, and loading the index structure. equivalent or worse than an exhaustive search, depending on the data distribution (which influences the tree structure). Especially for high-dimensional data, the search performance degenerates. According to [25], the overall complexity scaling of the search for the HNSW graph is \(O(\log|\mathbb{D}|)\), which does not degenerate for high-dimensional data. For the experiments of this section, we search for the \(\
u\) nearest items in our dataset (either \(\mathbb{D}_{\text{sm}}\) or \(\mathbb{D}_{\text{lg}}\)) to a given query, where we consider \(\
u\in\{1,10,100,1000\}\). We again use 3300 queries (as in Section 4.2) and perform several repetitions of this experiment. Then, we normalize the measured runtimes with respect to the number of queries and repetitions, such that the reported measures refer to the time needed for a single query. Table 6 shows the results of our experiments. Let us first consider the PCA-based dimensionality reduction using \(K=30\) for the smaller dataset \(\mathbb{D}_{\text{sm}}\). The exhaustive search requires 4.803 ms. The indexing approaches are much faster, taking 0.009 ms using a \(K\)-d tree and 0.007 ms using an HNSW graph. In this setting, there is no large difference between the indexing approaches. When we search for more neighbors (increasing \(\
u\)), the KD approach slows down substantially (0.621 ms, 1.001 ms, and 2.025 ms for \(\
u\) values of 10, 100, and 1000, respectively). The runtime does not increase to the same extent for the HNSW approach (0.007 ms, 0.007 ms, and 0.056 ms).