A Learning-to-Rank Formulation of Clustering-Based Approximate Nearest Neighbor Search

现代信息检索难题中的关键部分是近似最近邻搜索。其目标是返回一组 $k$ 个数据点，这些点最接近查询点，其准确性由返回集合中捕获的精确最近邻的比例来衡量。解决这个问题的一种流行方法是聚类：索引算法将数据点划分为不重叠的子集，并用如其质心的点表示每个子集。查询处理算法首先识别最近的簇——这个过程被称为路由——然后仅对这些簇执行最近邻搜索。在这项工作中，我们做出了一个简单的观察：路由函数解决了一个排名问题。因此，可以使用排名指标评估其质量，使该函数适合于学习排名。有趣的是，通常可以免费获得基本事实：给定一个处于前 $k$ 个配置的查询分布，基本事实是包含精确前 $k$ 个向量的簇集。我们利用这个洞察力并将其应用于最大内积搜索（MIPS）。正如我们在各种数据集上实证的那样，学习一个简单的线性函数可以始终提高基于聚类的 MIPS 的准确性。

解决问题：论文旨在解决近似最近邻搜索中的路由问题，提出了一种基于学习排序的方法。

关键思路：论文提出路由函数解决了一个排序问题，可以用排序度量来评估其质量，并且可以通过学习排序来改善路由函数的准确性。

亮点：论文针对Maximum Inner Product Search (MIPS)问题，提出了一种基于学习排序的路由函数，实验表明该方法可以显著提高MIPS的准确性。

相关研究：近似最近邻搜索是一个热门的研究方向，已经有很多相关的研究，如《Product Quantization for Nearest Neighbor Search》、《ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms》等。