论文标题
手指：基于图基的近似邻居搜索的快速推断
FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search
论文作者
论文摘要
例如，近似K-Near的邻居搜索（AKNNS）现在已经在现代应用程序中变得无处不在，例如，作为一个快速搜索程序，具有两个塔式深度学习模型。特别是基于图的AKNN方法，由于其出色的性能，因此受到了极大的关注。这些方法依靠贪婪的图形搜索来遍历数据库中的载体。在这种贪婪的搜索方案下，我们进行了一个关键的观察：许多距离计算不会影响搜索更新，因此可以在不损害性能的情况下近似这些计算。结果，我们提出了手指，这是一种快速的推理方法，以实现有效的图形搜索。手指通过估计较低碱基和分布匹配的相邻残留向量之间的角度来近似距离函数。近似距离可用于绕过不必要的计算，从而导致更快的搜索。从经验上讲，在不同的基准数据集中加速了一种基于图形的流行方法，其名为HNSW的HNSW被指定为HNSW的方法可超过现有的基于图的方法20％-60％。
Approximate K-Nearest Neighbor Search (AKNNS) has now become ubiquitous in modern applications, for example, as a fast search procedure with two tower deep learning models. Graph-based methods for AKNNS in particular have received great attention due to their superior performance. These methods rely on greedy graph search to traverse the data points as embedding vectors in a database. Under this greedy search scheme, we make a key observation: many distance computations do not influence search updates so these computations can be approximated without hurting performance. As a result, we propose FINGER, a fast inference method to achieve efficient graph search. FINGER approximates the distance function by estimating angles between neighboring residual vectors with low-rank bases and distribution matching. The approximated distance can be used to bypass unnecessary computations, which leads to faster searches. Empirically, accelerating a popular graph-based method named HNSW by FINGER is shown to outperform existing graph-based methods by 20%-60% across different benchmark datasets.
