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

摘要

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