• 主题
高级搜索  >
历史搜索 清空历史
首页> 中文学位 >基于位置敏感哈希的近似kNN查询算法研究
【6h】

基于位置敏感哈希的近似kNN查询算法研究

代理获取
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

近年来，随着互联网技术和网络信息检索技术的不断发展，尤其许多应用面临数据量呈几何级快速增长，并且数据维度也逐渐变高。那么，如何高效地处理海量高维数据的k近邻(k-NearestNeighbors，kNN)查询问题已经成为当前的一个重要研究课题。由于“维度灾难”的出现，基于R-tree及其变种索引结构已经不能够满足用户的需求，算法效率表现出比暴力查询方法更差的性能。
　　位置敏感哈希（LocalitySensitiveHashing，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查询问题。最后在真实以及人工数据集上进行大量实验，实验结果表明我们的算法具有良好的查询性能以及高可扩展性。

著录项

相似文献

  • 中文文献
  • 外文文献
  • 专利
代理获取

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号