[论文翻译]基于非度量相似图的极大内积搜索

Non-metric Similarity Graphs for Maximum Inner Product Search 基于非度量相似图的极大内积搜索 Stanislav Morozov Yandex, Lomonosov Moscow State University stanis-morozov@yandex.ru Stanislav Morozov Yandex, 莫斯科国立大学 stanis-morozov@yandex.ru Abstract 摘要 In this paper we addre... 本文研究了最大内积搜索(MIPS)问题，该问题目前是众多机器学习应用中的计算瓶颈。虽然与最近邻搜索(NNS)类似，但MIPS问题被证明更具挑战性，因为内积并非严格意义上的度量函数。我们提出利用相似图(similarity graphs)来解决MIPS问题，这种图的每个顶点都与在某种相似度函数下最相似的顶点相连。相似图框架最初是为度量空间设计的，本文将其自然扩展到非度量的MIPS场景。我们证明，与现有方法不同，相似图不需要任何数据转换来将MIPS降维为NNS问题，而应直接用于原始数据。此外，我们解释了这种降维为何会对相似图产生不利影响。通过与现有方法的广泛对比，我们表明所提方法在MIPS问题的运行时间/精度权衡方面具有颠覆性优势。