# Efficient Retrieval of Music Recordings Using Graph-Based Index Structures
## 5 Conclusions  
In our study, we compared various search techniques for a cross-version music retrieval task, where we aim to find the closest shingles in a database to a given query shingle. In particular, using datasets of different sizes, we applied indexing approaches with exact (exhaustive search, \(K\)-d tree) and approximate (HNSW graph) solutions. Our results showed that the approximate solution of the graph-based index has almost no negative impact on the retrieval quality in our music scenario. As our main finding, we obtained dramatic speed-ups by several orders of magnitude for the search operations involved in our retrieval system. We verified that HNSW graphs are robust with respect to the dimensionality of the items to be indexed, unlike \(K\)-d trees. As another contribution, we explored the impact of the HNSW index on several further steps in our pipeline, such as constructing, saving, and loading the index structure. We based our work on a previous study [9] that used shingles with highly specialized features for a cross-version music retrieval task. The authors aimed to reduce the shingle dimensionality with different embedding strategies to make the retrieval application more efficient. They found that it is possible to substantially reduce the shingle dimensionality with only a moderate loss in retrieval quality, where a DNN-based embedding is beneficial over a PCA-based reduction for small dimensionalities below \(K=12\). This reduction in dimensionality was essential for using \(K\)-d trees. Our experiments with HNSW graphs demonstrated that the shingle dimensionality is not as relevant to efficiency as good indexing approaches since the runtimes obtained with the HNSW approach are generally lower than those obtained with other search approaches, even with a strong dimensionality reduction. Still, dimensionality reduction may be important, e.g., to reduce disk space and memory requirements. Given our results, the remaining bottleneck of the retrieval pipeline is the feature computation for the query. In future research, one may employ feature representations that are less expensive to compute, e.g., using the STFT. Here, the embedding techniques may be useful to adapt and further enhance these \"raw\" representations for the retrieval task. As for future work, one may also explore alternative approaches to accelerate the nearest neighbor search in our cross-version retrieval scenario. One possibility is to apply an appropriate prototype selection method [46; 47], where the dataset is reduced by selecting representative prototypes. Another option is the use of pivot-based methods [48; 49], where pre-computed distances between the database items to some selected items (the pivots) are exploited for excluding some database items during the search. As basis for further research in this direction, we make our work reproducible by using open source implementations in all steps and by providing example code that shows how to apply these implementations, along with feature representations for an example dataset. Given our strong improvements in retrieval runtime without quality loss, we consider the HNSW graph a powerful tool that deserves more attention in the MIR community. All authors substantially contributed to this work by developing the main ideas and concepts. [PERSON] and [PERSON] wrote the paper. [PERSON] and [PERSON] implemented the approaches and conducted the experiments. Some results of this paper emerged from work for [PERSON]'s Master thesis [50], supervised by [PERSON] and [PERSON]. All authors have read and agreed to the published version of the manuscript. This work was supported by the German Research Foundation (DFG-MU 2686/11-1, DFG-MU 2686/12-1).