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

摘要：

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

关键词：近似最近邻搜索、k最近邻图、贪婪搜索算法

所属期刊栏目：10

分类号：TP399(计算技术、计算机技术)

在线出版日期：2021-03-23（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：70-72,78