最近邻搜索作为一个基础性问题,广泛出现在数据库、机器学习、计算机视觉和信息检索等领域。最近邻搜索问题可以被简单定义为,给定查询向量和n个同维的候选向量,要求返回某种距离度量方式下距离查询向量最近的一个或多个候选向量。在许多现实应用中,精确算法往往需要高昂的时间和空间代价,而近似最近邻搜索则以牺牲一定的准确率为代价,显著地降低了对存储空间和查询时间的要求。近似最近邻搜索因其实用性,受到了广泛关注,许多算法相继被提出,包括基于空间分割、基于哈希、基于向量量化和基于近邻图四类算法。然而目前还没有通用的亚线性时间复杂度的近似最近邻搜索算法。在大数据时代,设计高质、高效的近似最近邻搜索算法具有重要的理论意义和实用价值。基于(近似)k-近邻图(k-NX图)的近似最近邻搜索算法是当前的主流算法,一般包括两个步骤:一是对候选向量离线构造k-NN图,二是基于k-NN图采用某种搜索策略返回查询结果。k-NN图的质量和搜索策略极大地影响了算法的效果和效率。本文对k-NN图的构造,以及爬山搜索(GNNS)算法做了改进。主要结果有:(1)发现爬山搜索算法存在冗余计算、收敛速度慢,提出一种改进的爬山搜索(E-GNNS)算法:即在每一轮迭代中,不只对第一个样本,而是对前k个样本都在k-NN图上进行扩展。实验表明,E-GNNS算法在搜索效率和平均召回率上获得了显著提升。(2)在爬山搜索种子点的选择上,采用基于RVQ编码的倒排索引来生成候选种子点,替代原方法的随机种子点。实验表明,在这一策略的支持下,E-GNNS算法能够在相似的搜索时间下,获得超10%的平均召回率的提升。(3)为克服k-NN图构造时效率低下、内存消耗严重的缺点,提出一个基于2-M树的轻量级的构造方法。实验表明,该方法能够在不牺牲后期搜索效果和效率的前提下,显著降低k-NN图构造的时间和内存消耗。