Efficient Retrieval of Music Recordings Using Graph-Based Index Structures
Efficient Retrieval of Music Recordings Using Graph-Based Index Structures
复制标题
DOI：
10.3390/signals2020021
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
Frank Zalkow;Julian Brandner;Meinard Müller
中科院分区：
文献类型：
--
作者：
Frank Zalkow;Julian Brandner;Meinard Müller
灵活的检索系统需要方便地浏览通过大型音乐收藏。在特定的基于内容的音乐检索场景中，用户提供查询音频片段，并且检索系统从集合返回与查询相似的音乐记录。在这种情况下，系统的快速响应对于积极的用户体验至关重要。为了实现低响应时间，需要索引结构，以促进有效的搜索操作。一种这样的索引结构是K-d树，它已经被用于音乐检索系统。作为替代方案，我们建议使用现代的基于图的索引，表示为分层可导航小世界（HNSW）图。作为我们的主要贡献，我们探索其潜力的背景下，跨版本的音乐检索应用程序。特别是，我们报告系统的实验比较图和树为基础的索引结构的检索质量，磁盘空间的要求，和运行时间。尽管事实上，HNSW索引只提供了一个近似的解决方案，最近邻搜索问题，我们证明，它几乎没有负面影响的检索质量在我们的应用程序。作为我们的主要结果，我们表明，基于HNSW的检索速度快了几个数量级。此外，与基于树的结构不同，图结构还可以很好地处理高维索引项。鉴于这些优点，我们强调音乐信息检索（MIR）应用程序的HNSW图的实际意义。
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.