# Efficient Retrieval of Music Recordings Using Graph-Based Index Structures
## 3 Graph-Based Nearest Neighbor Search
### HNSW Graphs  
To date, we have described a search procedure using a data structure with a single graph. Building upon such a structure, [PERSON] and [PERSON] [25] introduced an improved data structure with multiple levels, called Hierarchical Navigable Small World (HNSW) graph, for approximate nearest neighbor search. Compared to search procedures for single-layer structures (as described in the previous section), the multi-layer search procedure has various benefits, such as improved search quality, higher efficiency (with a runtime that increases logarithmically with the dataset size), and greater stability with respect to the dimensionality \(K\). Figure 4 illustrates an HNSW graph with three layers. The bottom level (first layer) is a graph containing the full database, similar to the graph structure described in the previous section. In the figure, this layer contains 16 database items. The middle level (second layer) contains a subset of these items (eight items). The top level (third layer) contains a subset of the second layer's items (four items). For illustration purposes, the dashed red lines in the figure indicate the items that are available at all layers. Items that are available only at the first two layers are indicated with dashed gray lines. We now want to outline the search procedure for HNSW graphs. Given a query point \(\mathbf{x}_{\text{q}}\), searching in an HNSW graph starts at the top layer with a suitably selected entry point \(\mathbf{x}_{\text{e}}\) (e.g., random selection, see [25] for details). A search procedure is then applied, similar to the approach described in the previous Section 3.1, to find a candidate for the nearest neighbor to \(\mathbf{x}_{\text{q}}\) in the top layer. Then, the search continues at the next layer, where the entry point is the item corresponding to the nearest neighbor candidate from the upper layer. This way, the search continues until we arrive at the bottom layer, where all database items are available. The aim is to find the \(\
u\) nearest neighbors in this layer as the search procedure's result. To stabilize the approximate search results, we may first search for more than \(\
u\) approximate nearest neighbors (using a graph-based search procedure as before). We denote the number of \"intermediate\" candidates by \(\
u^{\prime}\in\mathbb{N}\), where \(\
u\leq\
u^{\prime}\leq|\mathbb{D}|\). Among the candidates, we then select the \(\
u\) nearest neighbors (by exhaustive search) as the  
Figure 3: Illustration of graph-based approximate nearest neighbor search. final result. The number \(v^{\prime}\) is a free parameter that can be increased to improve the search results (at the cost of an increased runtime). [PERSON] and [PERSON] [25] also proposed an algorithm for constructing HNSW graphs, which we summarize briefly. During the construction process, the database items are consecutively inserted into the graph. For each new item \(\mathbf{x}\in\mathbb{D}\), we randomly decide on its upper-most layer \(\ell(\mathbf{x})\in\mathbb{N}\) according to an exponentially decaying probability distribution. If the random process selects a higher layer \(\ell(\mathbf{x})\) than the highest existing layer in the graph, the number of layers in the graph increases dynamically. The item \(\mathbf{x}\) is then inserted in all layers \([1:\ell(\mathbf{x})]:=\{1,\ldots,\ell(\mathbf{x})\}\). Next, we want to connect the new node \(\mathbf{x}\) to \(M\) database items in each layer \([1:\ell(\mathbf{x})]\) by edges. The parameter \(M\in\mathbb{N}\) controls the minimum number of edges for each node of the data structure. We apply a top-down search procedure, similar to the approach described above, to search for suitable items in each layer \([1:\ell(\mathbf{x})]\). To stabilize the search results, we may first search for more than \(M\) candidates for inserting edges (using a graph-based search procedure as before).