论文部分内容阅读
近年来,随着互联网技术和网络信息检索技术的不断发展,尤其许多应用面临数据量呈几何级快速增长,并且数据维度也逐渐变高。那么,如何高效地处理海量高维数据的k近邻(k-Nearest Neighbors, kNN)查询问题已经成为当前的一个重要研究课题。由于“维度灾难”的出现,基于R-tree及其变种索引结构已经不能够满足用户的需求,算法效率表现出比暴力查询方法更差的性能。位置敏感哈希(Locality Sensitive Hashing, LSH)是最受欢迎且适合于解决处理高维数据空间下的近似kNN查询问题。然而,该方法的缺点在于为了保证较高的查询质量需要构建许多哈希表,导致存储代价较高以及查询效率低下；此外,随着处理数据量规模的不断增大以及MapReduce编程模型的广泛使用,传统单机上的查询算法已经不具备处理海量数据的能力,查询效率、索引代价等各方面都存在很大的提升空间。为了解决上述存在的问题,本文针对现有基于LSH的近似kNN查询算法进行了深入的研究,主要做了以下相关工作：(1)针对现有LSH相关算法索引存储代价高以及查询效率低下等问题,本文提出了一种新的二级混合索引结构LSRP-tree,它先利用RP-tree将整个数据集划分成多个子聚类,然后再对每一个子聚类构建基于LSH的哈希表。基于该索引结构,充分利用LSH哈希函数碰撞的特点,还分别设计了两种不同的CCP和CCF近似查询算法,有效地完成了高维数据空间下的近似查询操作。与LSB-tree/LSB-forest方法相比,本文算法在查询效率、查询质量以及空间代价方面均有很明显的提高。(2)为了解决大规模数据处理能力不足的问题,文中在分析位置敏感哈希算法以及MapReduce编程机制的基础上,利用当前非常流行的MapReduce编程模型,结合MapReduce机制本身的特点,研究了基于LSH的近似kNN查询算法,设计了一种新的分布式索引结构,并且提出了相应的查询方法。该方法可以有效地解决海量数据环境下的近似kNN查询问题。最后在真实以及人工数据集上进行大量实验,实验结果表明我们的算法具有良好的查询性能以及高可扩展性。