图像检索中基于近似k-近邻图的近似最近邻搜索算法研究

发布时间：2021-01-10 08:51

　　最近邻搜索作为一个基础性问题,广泛出现在数据库、机器学习、计算机视觉和信息检索等领域。最近邻搜索问题可以被简单定义为,给定查询向量和n个同维的候选向量,要求返回某种距离度量方式下距离查询向量最近的一个或多个候选向量。在许多现实应用中,精确算法往往需要高昂的时间和空间代价,而近似最近邻搜索则以牺牲一定的准确率为代价,显著地降低了对存储空间和查询时间的要求。近似最近邻搜索因其实用性,受到了广泛关注,许多算法相继被提出,包括基于空间分割、基于哈希、基于向量量化和基于近邻图四类算法。然而目前还没有通用的亚线性时间复杂度的近似最近邻搜索算法。在大数据时代,设计高质、高效的近似最近邻搜索算法具有重要的理论意义和实用价值。基于（近似）k-近邻图（k-NX图）的近似最近邻搜索算法是当前的主流算法,一般包括两个步骤:一是对候选向量离线构造k-NN图,二是基于k-NN图采用某种搜索策略返回查询结果。k-NN图的质量和搜索策略极大地影响了算法的效果和效率。本文对k-NN图的构造,以及爬山搜索（GNNS）算法做了改进。主要结果有:（1）发现爬山搜索算法存在冗余计算、收敛速度慢,提出一种改进的爬山搜索（E-GN... 

【文章来源】：厦门大学福建省 211工程院校 985工程院校 教育部直属院校

【文章页数】：75 页

【学位级别】：硕士

【部分图文】：

图２．１随机Ｋ－Ｄ树

图２．２?ｋ－ｍｅａｎｓ树

⑷??Ｇ在二维情况下的一个例子，距离最近的两个邻居是〃３和弃ｆｌ４，而将点６加入到ｐ的近邻列表。（参考文献Ｉ５１］）??个子集里，点对之间的平均角度是最大的。然而，这是一ＤＰＧ中提出了一个更简单的贪心启发式方法。开始的时候中选择的最近的ｆ个点。在接下来的次迭代中，当中，能够使得Ｓ中的点的平均角度相似性更小时，就移动的每一个点《，在差异化相似图中加入边（ＰＡ）和（《，ｐ）。差＇


本文编号：2968432