# Efficient Retrieval of Music Recordings Using Graph-Based Index Structures
## 4 Experiments
### Experimental Setup  
In the following, we analyze the possible decrease in retrieval quality and the improvements of the retrieval runtime introduced by the HNSW graph. To this end, we consider quantitative performance measures, which we list in Table 2. To evaluate the retrieval quality, we use standard precision-based measures (more details in Section 4.2). To analyze the impact of the index structures on the retrieval speed, we consider several steps that are involved in our retrieval scenario. Some steps need to be computed offline when processing the database documents, and other steps need to be computed online when processing a query. In the offline phase, we need to compute features for all audio files of the database, construct an index and save the index file to disk. These steps can be carried out at any time and on any system (offline). When applying our index, we first need to load the index into the computer's main memory (RAM). This loading step can be considered as being in-between the online and offline stages. The index loading needs to be performed on the actual system where the retrieval service is provided. When the index structure can be kept in the main memory, it does not have to be reloaded for each query. Therefore, we still consider it as part of the offline stage. In the actual online phase, we need to compute the query features and perform the nearest neighbor search procedure using our index structure. In the following sections, we analyze these steps in the order given in Table 2.  
If not mentioned otherwise, we always report on average time measurements (\(\mu\pm\sigma\)) for 100 iterations of the experiment. Note that runtime evaluation is a delicate topic on its own [39]. For example, one may argue that it is more meaningful to report minimum instead of average runtime measurements because other processes running in parallel affect the mean more than the minimum. In our case, this is not a major issue because the standard deviation \(\sigma\) is always relatively low. We want to highlight that we take a practical perspective by measuring runtimes using distinct implementations of the respective index structures, implemented in different programming languages. The absolute runtimes obtained may vary when using different implementations or hardware systems. Our \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Step** & **Performance Measure** & **Stage** & **Section** \\ \hline Overall pipeline & Quality (P@1, P@3, P\({}_{R}\)) & Offline \& online & Section 4.2 \\ Feature computation & Time (ms) & Offline \& online & Section 4.3 \\ Constructing the index & Time (s) & Offline & Section 4.4 \\ Saving the index & Disk space (MB) & Offline & Section 4.4 \\ Loading the index & Time (ms) & Offline & Section 4.4 \\ Retrieval & Time (ms) & Online & Section 4.5 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Considered performance measures. study gives practical insights into the runtimes obtained by specific implementations on specific platforms for our specific application. In general, we are interested in the orders of magnitude, the relative differences between the time measurements, and the relationships between index size and runtime. We compare three different search approaches: an exhaustive search approach (full search, exact search solution), an indexing strategy using \(K\)-d trees (KD, exact search solution), and the graph-based index structure (HNSW, approximative search solution). We perform our experiments using Python 3.6.5 on a computer with an Intel Xeon CPU E5-2620 v4 (2.10 GHz) and 31 GiB RAM. We use the efficient pairwise-distance calculation of scipy 1.0.1 [40] for the full search, which is calling a highly optimized implementation in C. For the \(K\)-d trees (using a default leaf size of 30), we use the implementation of scikit-learn 0.20.1 [41], which is written in Cython.