# Efficient Retrieval of Music Recordings Using Graph-Based Index Structures
## 3 Graph-Based Nearest Neighbor Search
### Graph-Based Data Structures  
In our search problem, we have a database \(\mathbb{D}\) of items \(\mathbf{x}\in\mathbb{D}\). The items are \(K\)-dimensional vectors, thus \(\mathbb{D}\subset\mathbb{R}^{K}\). Figure 3 (initial situation) illustrates a dataset, where the items are gray points. Given a query \(\mathbf{x}_{\text{q}}\in\mathbb{R}^{K}\) (colored in orange in Figure 3) and some distance measure \(d\) (see Equation (1)), the aim is to find the \(\
u\in\mathbb{N}\) database items that are nearest to this query. As an example, let us now assume \(\
u=1\). Then the aim is to find the closest database item  
\[\mathbf{x}^{*}=\operatorname*{arg\,min}_{\mathbf{x}\in\mathbb{D}}d(\mathbf{x},\mathbf{x}_{ \text{q}}). \tag{3}\]  
A naive solution to this problem is to compute the distances between all database items and the query for selecting the item with the smallest distance (exhaustive search). With graph-based nearest neighbor search, we aim to find \(\mathbf{x}^{*}\) without evaluating all these distances, but only a subset of them. In general, we have no guarantee of finding \(\mathbf{x}^{*}\) with a graph-based search. Because of this reason, this strategy belongs to the category of approximate nearest neighbor search methods.  
\begin{table}
\begin{tabular}{c c c c c c} \hline  & **\# Audio Files** & \(\mathbf{\Sigma}\)**Duration** & \(\mathbf{\diameter}\)**Duration** & **Annotations** & **\# Shingles** \\ \hline \(\mathbb{D}_{\text{sm}}\) & 330 & 16:13:37 & 0:02:57 & ✓ & 52,332 \\ \(\mathbb{D}_{\text{lg}}\) & 7115 & 389:58:03 & 0:03:17 & ✗ & 1,272,386 \\ \hline \end{tabular}
\end{table}
Table 1: Statistics for the used datasets. Duration format hh:mm:ss. Annotations refer to the availability of complete annotations for the musical pieces underlying the recordings (required to evaluate retrieval quality). \(\mathbf{\Sigma}\) refers to the total, and \(\diameter\) refers to the average.  
In our graph-based approach, the database is organized as an undirected graph structure, where the database items are nodes. Nearby nodes are connected by edges, which are represented by connecting lines in Figure 3. In essence, the search in the database consists in traversing along the edges of the graph. In the first step of the search procedure, we select an entry point \(\mathbf{x}_{\text{e}}\in\mathbb{D}\) of the database (colored in dark blue in Figure 3, first step), e.g., by random choice. This entry point is our first active search node in the procedure. We then compute the distance of the query to this node. Next, we compute the distance between the query and all items that are connected to the active search node (colored in light blue in Figure 3). If any of these distances are smaller than the distance between the query and the active search node, we continue with the next step, where the node with the shortest distance is the next active search node in the procedure. Otherwise, we terminate, and our active search node is the final candidate for the nearest neighbor to the query. In Figure 3, we perform four steps until the algorithm terminates. In our example, the final candidate corresponds to the exact solution \(\mathbf{x}^{*}\).