论文部分内容阅读
相似性搜索是计算机科学中的一个基础问题,被广泛应用在多个计算机领域,包括数据挖掘、机器学习、信号处理以及信息检索等等。最初人们通过查找查询对象的最近邻(Nearest Neighbor, NN)来解决相似性搜索问题,提出了系列在低维数据空间表现良好的分支界限算法。但是当数据的维度增加时,这类算法的时间效率会下降到接近线性查找的程度,也就是所谓的“维度灾害”。部分研究人员提出可以使用近似最近邻查询来解决相似性搜索问题,因为在大部分的应用场景下,使用近似结果一样可以很好地满足应用需求。位置敏感哈希(Locality Sensitive Hashing, LSH)是近似最近邻搜索算法中最流行的一种,它有坚实的理论依据并且在高维数据空间中表现优异。但是LSH也存在一些缺点：为了拥有较好的搜索效率,LSH算法所建立的索引需要大量的内存；此外,LSH算法的查询时间也存在进一步优化的空间。尽管一些科研工作者针对LSH的缺点提出了一些改进算法,但是这些改进算法也大多基于通用的LSH算法框架,而这个框架本身就存在一定局限性,而且这些算法在处理大规模数据时的性能依然有待提高。为了提出性能及适应性更好的相似性搜索算法,本文在LSH的基础上做了以下工作：1.分析了LSH解决相似性搜索问题的思路,指出了通用的LSH算法框架存在的缺陷：需要使用大量的哈希表来保证查询效率；对于距离查询点较远的点的过滤效果比较差；没有充分利用哈希函数的性质。2.提出了一种新的相似性搜索算法—基于冲突计数的位置敏感哈希(FBLSH)。 FBLSH充分利用了基于P稳定分布的LSH函数的特性,通过冲突次数统计的方法,减少了哈希表的数量,增强了算法过滤不满足查询条件的点的能力,从而降低了查询时间。本文从理论上证明了该算法能有效地解决相似性搜索问题并分析了算法的复杂度。论文的实验表明：与基于P稳定分布的LSH相比,FBLSH能同时提高时间和空间效率。3.为了弥补现有相似性搜索算法处理大规模数据能力的不足,本文提出了一种混合型索引结构—HKF树,它不仅继承了FBLSH低空间消耗的优点而且在大规模数据集上表现优异。HKF树使用层次化的k-means树作为上层结构,在每个叶子节点上建立FBLSH索引。本文从理论上证明了HKF树算法的有效性并分析了算法的复杂度。论文的实验表明HKF树在大规模数据集上的性能优于层次化的k-means树、FBLSH以及后验多探测LSH。