基于k-means特征的适应性近似最近邻搜索算法

摘要：

在基于倒排索引和HNSW索引结构的最近邻搜索算法中,由于所有查询点使用固定的终止条件进行近似最近邻搜索,从而导致某些查询点在搜索路径上访问了不必要的数据点.因此,本文针对十亿规模数据集,在IVF-HNSW算法的基础上,根据数据点的k-means特征和真实最小访问点,建立神经网络回归模型.通过模型,动态预测每个查询点在HNSW索引中找到最近邻所需要搜索的质心个数,以及在IVF中需要搜索的倒排列表的个数,最终每个查询点能够通过适应性搜索,减少需要访问的数据库向量的个数,进而降低总体搜索所需要的查询时间.实验结果表明,优化后的自适应搜索算法与原始IVF-HNSW算法相比,在最高召回率下,平均查询时间最多可降低 27%.

关键词：最近邻搜索、倒排索引、HNSW索引、适应性搜索

所属期刊栏目：13

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

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

页数：共5页

页码：80-84