基于邻居聚类的近似最近邻搜索

Approximate nearest neighbor search based on neighbor clustering

本文提出了一种新的基于图的方法,用于对高维特征向量的数据集进行近似最近邻搜索(ANNS)。大多数基于图的方法着重于提高图的构造质量,而本文的工作着重于图搜索的性能。基于近似k近邻(k NN)图来展示实验结果,并且存在许多用于构建近似k NN图的现有方法,例如NN下降、KGraph或Faiss。本文在图的构建阶段,首先初始化一个近似的k NN图,然后利用K-means聚类算法将邻居聚类;在查询阶段,使用贪婪搜索算法,遍历图并尝试贪婪地到达查询。为了提高查询性能,仅通过聚类信息比较其中一部分邻居,在实验中展示了如何降低查询成本和提高查询精度。

This article presents a new graph-based method for approximate nearest neighbor search(ANNS) on datasets of high dimensional feature vectors.Most graph-based methods focus on improving the quality of graph construction,but our work focuses on the performance of graph search.We report the results using approximate k-nearest neighbor(kNN) graph,and there are many existing methods for constructing approximate kNN graphs,such as NN-descent,KGraph or Faiss.In the construction stage of the graph,we first initialize an approximate kNN graph,and then filter the neighbors by the angle among the neighbors of each point on the graph.During the query stage,we use the greed-search algorithm,which walks over the graph and tries to reach the query greedily.To improve the query performance,we only compare a part of its neighbors by angle information.We show in the experiment how to achieve lower query time and query cost with high precision.