基于近邻图的高维空间近似最近邻查询研究

摘要

随着大数据时代的来临，大规模搜索的搜索效率问题成为一个研究重点。最近，研究人员开始关注一种基于近邻图（Nearest Neighbor Graph）的近似最近邻查询方法（Approximate Nearest Neighbor），其优势在于面对海量高维数据时查询效率高，查询结果准确，近邻召回率高。本文系统研究了基于近邻图的近似最近邻查询算法，如GNNS、kGraph算法等。该类算法在预处理阶段构建一个近邻图，在查询阶段，应用贪心算法的思想以近邻图为索引结构进行查询。贪心算法从一个随机的数据对象开始，不断地载入当前最优近邻在近邻图上的邻居，若该邻居比当前最优近邻更接近查询对象，则令该邻居为新的最优近邻，本质是一个通过不断获得局部最优，逼近全局最优的过程。但由于贪心算法的固有缺陷，随着迭代次数增加，算法陷入局部最优的概率也大幅上升，会降低ANN查询的精度和效率。 针对贪心算法在近邻图上易陷入局部最优的缺陷，本文使用一种解决思路：在查询阶段，为贪心算法提供一个更优的起始点。优质的起始点可以将贪心选择定位在近邻图中靠近查询对象的区域，此时仅需要很少的迭代次数就可以访问到真实近邻，降低了发生局部最优的概率，提升了最近邻查询的精度和效率。 本文提出一种新的基于近邻图的近似最近邻查询方法NSH-NNG，将邻域敏感哈希（Neighbor-Sensitive Hashing）技术和基于近邻图的ANN查询结合到一起。邻域敏感哈希是一种哈希学习的方法，其生成的哈希函数考虑了数据集分布特性，且对距离查询对象近的数据对象更有区分度，故能在快速ANN查询的同时保持高精度。在预处理阶段，该方法同时构建一个NSH哈希索引和一个近邻图；在查询阶段，该方法将查询对象映射为NSH哈希编码，先通过多索引哈希快速确定一个与查询对象相似的候选集，再以该候选集为起始点集在近邻图上进行ANN查询。本方法减少了基于近邻图的ANN查询算法陷入局部最优的概率，能以较高的精度实现快速近似最近邻查询。 此外，本方法在提高查询性能的同时，还提出了一种基于数据敏感哈希（Data-Sensitive Hashing）的快速近邻图构建方法。数据敏感哈希通过机器学习，能将数据库中相似的数据对象均匀地分散到哈希桶中。根据该特性，采用分而治之法，先通过DSH算法将整个数据集均匀地分成多个较小的子集，在每个子集中使用线性查询法生成子近邻图，再将子图合并成近邻图，最后使用近邻下降算法对该近邻图进行优化。 本文在两个真实高维数据集下，实验验证了NSH-NNG方法相对于几种流行算法在查询效率上有二至三倍的提升。同时，证明了基于数据敏感哈希的快速近邻图构建方法的效率不亚于几种流行的近邻图构建算法。

目录

第一个书签之前