论文部分内容阅读
最近邻检索是计算机视觉、数据挖掘、机器学习等领域的一个基本问题。随着互联网数据的爆炸性增长,海量高维数据的最近邻检索问题已成为挑战。传统的基于树形结构的最近邻检索方法在面对海量高维数据时表现乏力,而基于哈希表示的最近邻检索方法凭借其高效的压缩存储和快速的检索速度,已经成为解决海量高维数据相似性搜索问题最有效的方法之一。但是,哈希表示的最近邻检索方法存在两个问题:第一是数据通常会被多个哈希函数映射为比特码,所以不同的哈希函数会生成质量不等的比特位,而在大多数场景下,这些比特位是被同等对待的;第二是在数据规模特别大时,原本采用线性扫描的汉明距离计算也不再高效,此时通常会构建哈希表来提高搜索的效率,但是由于长比特码的局限性,传统的单哈希表索引方式已经很难满足对于检索的高效性要求。基于上述哈希表示的最近邻检索方法存在的问题,本文提出HMTable算法和MQRank算法。HMTable是一种性能更好的多哈希表索引结构,用于解决哈希表索引低效的问题,而MQRank是一种结合多表特性的更加细粒度的比特码排序算法。具体地说,由于单哈希表难以满足长比特码的索引要求,因此通常会通过划分比特码来构建多哈希表。因为一些简单朴素的划分方法不能捕获到比特位之间的关系信息,所以构建的多哈希表性能不是很好。本文的HMTable采用分层迭代的方式划分比特码,使得划分的比特码分组更加均匀,从而构建出质量更高的多哈希表;由于汉明距离只是一些离散的整数值,难以准确衡量相同距离下的不同数据点的差别,主要原因在于不同比特位在距离的计算上具有同等的作用。因此,针对比特位一致性问题,本文提出MQRank用于更加细粒度的加权汉明距离计算。MQRank的比特位权重计算综合了近邻点和远邻点对于哈希函数划分能力的影响,同时在各个子表下独立校准权重,使得生成的比特位权重在基于多表的最近邻计算上更加精确。本文在4个公开数据集MNIST、CIFAR1O、SIFT1M和GIST1M上进行实验设计与验证,并在基于多种哈希算法生成的比特码上分别进行多哈希表索引查询与权重优化的实验评价。大量的实验结果表明,本文所提出的方法在近似最近邻检索上具有有效性和通用性。