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

摘要

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