# Efficient Retrieval of Music Recordings Using Graph-Based Index Structures
## 4 Experiments
### Retrieval Time
Searching in the larger dataset \(\mathbb{D}_{\text{lg}}\) shows the potential of the HNSW index even more clearly. For example, using the PCA-based embedding (\(K=30\)), for \(\
u=100\), the \(K\)-d tree requires 66.499 ms and the HNSW graph needs only 0.019 ms. While the increased dataset size only has a minor effect on the runtime for the HNSW approach, it dramatically increases the KD strategy's runtime. For lower dimensionalities, the runtime differences between the \(K\)-d tree and the HNSW graph are less extreme. For example, the KD approach requires 0.201 ms for \(K=6\) (\(\mathbb{D}_{\text{lg}}\), \(\
u=100\)). Still, the HNSW graph is much faster (0.011 ms). Without dimensionality reduction, the KD approach breaks down (more than 700 ms for \(\mathbb{D}_{\text{lg}}\)), which is a known fact [21, 37]. However, the HNSW graph still facilitates fast retrieval (e.g., 0.021 ms for \(\
u=100\)). This substantial decrease in retrieval time shows the power of the graph-based search approach. In general, the tendencies discussed for the PCA reduction are similar when using the DNN-based embedding. \begin{table}
\begin{tabular}{c c c c c c c c c c c} \hline \hline \multirow{2}{*}{**Reduction**} & \multirow{2}{*}{**K**} & \multirow{2}{*}{**Search**} & \multicolumn{5}{c}{\(\mathbb{D}_{\text{sm}}\)} & \multicolumn{5}{c}{\(\mathbb{D}_{\text{lg}}\)} \\  & & & \(\boldsymbol{\
u=10}\) & \(\boldsymbol{\
u=100}\) & \(\boldsymbol{\
u=1000}\) & \(\boldsymbol{\
u=1}\) & \(\boldsymbol{\
u=100}\) & \(\boldsymbol{\
u=1}\) & \(\boldsymbol{\
u=100}\) & \(\boldsymbol{\
u=1000}\) \\ \hline \multirow{3}{*}{—} & \multirow{3}{*}{240} & Full Search & 13.912 & 13.912 & 13.824 & 13.875 & — & — & — & — \\  & & KD & 0.072 & 23.136 & 24.463 & 25.269 & 771.623 & 775.116 & 770.461 & 772.946 \\  & & HNSW & 0.008 & 0.008 & 0.009 & 0.072 & 0.020 & 0.020 & 0.021 & 0.205 \\ \hline \multirow{3}{*}{PCA} & \multirow{3}{*}{30} & Full Search & 4.803 & 4.757 & 4.768 & 4.812 & — & — & — \\  & & KD & 0.009 & 0.621 & 1.001 & 2.025 & 36.825 & 48.145 & 66.499 & 88.849 \\  & & HNSW & 0.007 & 0.007 & 0.007 & 0.056 & 0.010 & 0.009 & 0.019 & 0.123 \\ \hline \multirow{3}{*}{PCA} & \multirow{3}{*}{12} & Full Search & 4.354 & 4.418 & 4.322 & 4.360 & — & — & — & — \\  & & KD & 0.004 & 0.087 & 0.233 & 0.713 & 0.907 & 1.698 & 4.414 & 10.280 \\  & & HNSW & 0.007 & 0.007 & 0.007 & 0.056 & 0.009 & 0.009 & 0.009 & 0.067 \\ \hline \multirow{3}{*}{PCA} & \multirow{3}{*}{6} & Full Search & 4.123 & 4.115 & 4.124 & 4.159 & — & — & — \\  & & KD & 0.003 & 0.019 & 0.074 & 0.346 & 0.031 & 0.065 & 0.201 & 0.852 \\  & & & HNSW & 0.007 & 0.007 & 0.006 & 0.048 & 0.007 & 0.007 & 0.011 & 0.072 \\ \hline \multirow{3}{*}{DNN} & \multirow{3}{*}{30} & Full Search & 4.899 & 4.897 & 4.883 & 4.930 & — & — & — & — \\  & & KD & 0.009 & 0.459 & 1.019 & 2.498 & 30.021 & 46.611 & 75.748 & 117.543 \\  & & HNSW & 0.007 & 0.007 & 0.007 & 0.057 & 0.011 & 0.011 & 0.011 & 0.077 \\ \hline \multirow{3}{*}{DNN} & \multirow{3}{*}{12} & Full Search & 4.439 & 4.434 & 4.433 & 4.480 & — & — & — \\  & & KD & 0.004 & 0.064 & 0.177 & 0.709 & 0.377 & 0.829 & 2.498 & 7.240 \\  & & HNSW & 0.008 & 0.008 & 0.009 & 0.068 & 0.006 & 0.007 & 0.007 & 0.056 \\ \hline \multirow{3}{*}{DNN} & \multirow{3}{*}{6} & Full Search & 4.165 & 4.162 & 4.171 & 4.220 & — & — & — \\  & & KD & 0.002 & 0.014 & 0.062 & 0.310 & 0.019 & 0.039 & 0.141 & 0.663 \\ \cline{1-1}  & & HNSW & 0.006 & 0.007 & 0.007 & 0.054 & 0.007 & 0.007 & 0.007 & 0.057 \\ \hline \hline \end{tabular}
\end{table} 
Table 6: Search runtimes (in ms) using a single query for various dimensions \(K\) and search strategies. Note that the exhaustive search involves computing all pairwise distances between the query and the database items. As a consequence, the parameter \(\
u\) does not influence the search time. Furthermore, we did not perform the full search for \(\mathbb{D}_{\text{lg}}\) because of excessive memory requirements. Figure 5 shows the search runtimes for various dimensionalities \(K\).