International Audio Laboratories Erlangen

Efficient Retrieval of Music Recordings Using Graph-Based Index Structures

This is the accompanying website for the following paper:

1. Frank Zalkow, Julian Brandner, and Meinard Müller
   Efficient Retrieval of Music Recordings Using Graph-Based Index Structures
   Signals, 2(2): 336–352, 2021. Bibtex PDF Details DOI

   @article{ZalkowBM21_Indexing_Signals,
   author      = {Frank Zalkow and Julian Brandner and Meinard M{\"u}ller},
   title       = {Efficient Retrieval of Music Recordings Using Graph-Based Index Structures},
   journal     = {Signals},
   volume      = {2},
   number      = {2},
   year        = {2021},
   doi         = {10.3390/signals2020021},
   url-details = {https://www.audiolabs-erlangen.de/resources/MIR/2020_signals-indexing},
   url-pdf     = {https://www.mdpi.com/2624-6120/2/2/21},
   pages       = {336--352}
   }

Abstract

Flexible retrieval systems are required for conveniently browsing through large music collections. In a particular content-based music retrieval scenario, the user provides a query audio snippet, and the retrieval system returns music recordings from the collection that are similar to the query. In this scenario, a fast response from the system is essential for a positive user experience. For realizing low response times, one requires index structures that facilitate efficient search operations. One such index structure is the K-d tree, which has already been used in music retrieval systems. As an alternative, we propose to use a modern graph-based index, denoted as Hierarchical Navigable Small World (HNSW) graph. As our main contribution, we explore its potential in the context of a cross-version music retrieval application. In particular, we report on systematic experiments comparing graph- and tree-based index structures in terms of the retrieval quality, disk space requirements, and runtimes. Despite the fact that the HNSW index provides only an approximate solution to the nearest neighbor search problem, we demonstrate that it has almost no negative impact on the retrieval quality in our application. As our main result, we show that the HNSW-based retrieval is several orders of magnitude faster. Furthermore, the graph structure also works well with high-dimensional index items, unlike the tree-based structure. Given these merits, we highlight the practical relevance of the HNSW graph for music information retrieval (MIR) applications.

Material

To make the results of our paper transparent and accessible, we provide a repository containing code that shows how to use the index structures discussed in the article, along with pre-computed features for an example dataset. We also provide an HTML export of the Jupyter notebook from the repository, such that one may study how the index structures are applied without running any code.

Acknowledgements

Frank Zalkow and Meinard Müller are supported by the German Research Foundation (DFG-MU 2686/11-1, MU 2686/12-1). The International Audio Laboratories Erlangen are a joint institution of the Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU) and Fraunhofer Institute for Integrated Circuits IIS.

References

1. Julian Brandner
   Efficient Cross-Version Music Retrieval Using Dimensionality Reduction and Indexing Techniques
   Friedrich-Alexander-Universität Erlangen-Nürnberg, 2019. Bibtex

   @mastersthesis{Brandner19_Indexing_MasterThesis,
   title   = {Efficient Cross-Version Music Retrieval Using Dimensionality Reduction and Indexing Techniques},
   author  = {Julian Brandner},
   school  = {Friedrich-Alexander-Universit{\"a}t Erlangen-N{\"u}rnberg},
   type    = {{M}aster {T}hesis},
   year    = {2019}
   }

2. Yury A. Malkov and Dmitry A. Yashunin
   Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
   IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4): 824–836, 2020. Bibtex DOI

   @article{MalkovYashunin18_HNSWG_IEEE-PAMI,
   author    = {Yury A. Malkov and Dmitry A. Yashunin},
   title     = {Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs},
   journal   = {{IEEE} Transactions on Pattern Analysis and Machine Intelligence},
   volume    = {42},
   number    = {4},
   pages     = {824--836},
   year      = {2020},
   doi       = {10.1109/TPAMI.2018.2889473}
   }

3. Frank Zalkow and Meinard Müller
   Learning Low-Dimensional Embeddings of Audio Shingles for Cross-Version Retrieval of Classical Music
   Applied Sciences, 10(1), 2020. Bibtex Details DOI

   @article{ZalkowMueller20_Shingles_AppliedSciences,
   author      = {Frank Zalkow and Meinard M{\"u}ller},
   title       = {Learning Low-Dimensional Embeddings of Audio Shingles for Cross-Version Retrieval of Classical Music},
   journal     = {Applied Sciences},
   volume      = {10},
   number      = {1},
   year        = {2020},
   doi         = {10.3390/app10010019},
   url-details = {https://www.mdpi.com/2076-3417/10/1/19}
   }