Unleashing Graph Partitioning for Large-Scale Nearest Neighbor Search

本文考虑将大规模的近似最近邻搜索（ANNS）问题分解为较小的子问题的基本问题。目标是将输入点划分为保留邻域的碎片，以便任何点的最近邻只包含在少数碎片中。当查询到达时，使用路由算法来识别应搜索其最近邻的碎片。这种方法构成了分布式ANNS的支柱，其中数据集非常大，必须分割到多个机器上。 在本文中，我们设计了简单而高效的路由方法，并证明了它们性能的强大理论保证。我们的路由算法的一个关键特点是它们本质上是模块化的，并且可以与任何分区方法一起使用。这解决了以前方法的一个关键缺点，即路由算法与其相关的分区方法不可分割。特别地，我们的新路由方法使得可以使用平衡图分区，这是一种高质量的分区方法，但没有自然相关的路由算法。因此，我们提供了第一种使用平衡图分区的路由方法，这些方法训练非常快，延迟低，并实现高召回率。我们对十亿级数据集上的完整分区和路由流水线进行了全面评估，结果表明，我们的方法在性能上明显优于现有的可扩展分区方法，在90%召回率下，QPS比最佳竞争对手高出2.14倍。

解决大规模近似最近邻搜索（ANNS）问题的分布式计算问题。

本论文提出了一种基于模块化的路由算法，可以与任何分区方法一起使用，并可以使用平衡图分区，实现了高质量的分区和低延迟的路由。

本论文的路由算法非常高效，可以处理十亿级别的数据集，比现有的可扩展分区方法表现更好。实验结果表明，我们的方法可以在90%召回率下实现高达2.14倍的QPS。

与本论文相关的研究包括：《Scalable Locality-Sensitive Hashing for Millions of High-Dimensional Vectors》、《Distributed Similarity Search in High-Dimensional Spaces》等。