基于距离的相似最近邻搜索算法研究

摘要

为了提高相似最近邻搜索(ANN)算法的精度,提出了一种在度量空间下基于距离的相似最近邻搜索算法—优化的VP森林(OVF)算法。在传统VP树(VT)算法的基础上,首先采用改进的选择优势点的方法,通过从数据集采样优势点候选集,对其进行评估,选取其中区分度大的点作为优势点;然后提出构建多棵VP树的新方法,改进距离优势点远的子树中最近邻不紧凑问题;接着提出使用优先队列与剪枝搜索方法结合的新搜索方法查找最近邻,减少了很多不必要的距离计算。最后通过实验结果表明,本文方法在数据维度、数据集大小、返回不同邻居个数、不同的距离函数及建树个数方面精度有了很大的提高。