王执政，杨凯祥，谭宗元

（东华大学 计算机科学与技术学院，上海 201620）

0 引 言

随着计算机技术的飞速发展，当今社会已经进入互联网大数据时代。当前的数据量巨大、数据维度之高，给信息检索带来极大挑战。最近邻搜索是信息检索的重要技术，已经在数据库、人工智能、图像搜索等领域广泛应用，其最原始的方法是对数据库中的所有点进行一一比对，找到最近的邻居，然而这种方法只适应于数据量非常小的情况，对于大数据集查询时间较长，无法满足应用需求。近似最近邻搜索成为主流，其主要思想在牺牲较小的查询精度情况下，减少查询时间、提高查询效率。基于图的搜索算法是当前近邻搜索算法中最受关注的，已经被很多大型商业公司广泛应用。

基于图的近似最近邻搜索算法使用的是近似k近邻图，其主要思想是将数据集的每个向量通过计算欧氏距离得到k个邻居，通过邻居关系建立图索引结构，并在建立的索引的基础上进行查询［1］。该算法一方面使每个点只连接几个邻居，极大的减少了索引的内存；另一方面，通过此图索引可以很快定位到查询点的邻居附近，实现快速查询。近年来，基于图的算法取得了很大的进步，该算法是目前查询速度最快，查询精度最高的近似最近邻搜索算法。

本文通过对基于图的搜索算法查询阶段的分析，将自适应的提前终止算法与Link and Code（L＆C）算法进行结合，对L＆C 算法的查询阶段进行改进。实验结果表明，与原始L＆C 结果相比，在GIST 数据集上平均查询时间最大减少76%。……