基于近邻图的局部敏感哈希索引技术研究

代理获取

页面导航

目录
摘要
著录项
相似文献
相关主题

摘要

随着社会的发展和时代的进步，数据维数越来越高，数据库规模越来越大，复杂性越来越高，那么怎么从海量高维数据中快速找到目标数据成了一个难题。对于低维的小数据集，我们可以通过线性计算很容易解决，但是对于海量高维数据集，线性查找往往需要很庞大的运算量，非常耗时。为了解决这一难题，一方面需要设计更加高效的索引结构对数据进行有效组织，另一方面需要为索引结构配以高效的查询机制实现更加准确快速的搜索。这种技术我们称之为高维最近邻查询(Nearest Neighbor, NN)技术，现已成为海量多媒体数据检索研究中的一个基础问题。
　　由于高维空间中存在“维数灾难”现象，使得高效查找精确最近邻变得十分困难。而通过牺牲少量精度以求解近似最近邻(Approximate Nearest Neighbor, ANN)代替精确解却能够获得巨大的效率提升，因此研究者们重点关注近似最近邻查询技术。目前，局部敏感哈希技术(LSH)及其变种被公认为是近似最近邻查询最有效的解决方案。LSH的基本思想就是：原始数据空间相邻的两个点通过相同的映射或投影后，这两个点在新的数据空间中相邻的概率同样很大，而不相邻的两个点被映射进同一个桶里的概率很小。
　　本文对局部敏感哈希技术、空间曲线和近邻图进行了重点研究和分析。在局部敏感哈希技术方面，对目前的多种哈希算法进行了学习和研究，对其技术优劣性进行了分析。局部敏感哈希的优势是能实现候选点的快速筛选，通过构建复合哈希函数能有效过滤不相关点得到高质量的候选集，但缺点是访问候选点依赖大量的随机I/O，而且存在大量漏报，为了获取高质量的返回结果，需要构建多个哈希表，访问足够多的候选点，从而导致了庞大的时间和空间开销。空间曲线可以建立复合哈希值的线序关系，从而能实现邻域的快速定位。近邻图技术借助数据点间的邻接关系能快速地收敛到更好的候选点，但受初始搜索点质量的影响容易陷入局部最优。
　　为了克服当前 LSH方法的缺陷，本文提出了一种新的算法——NNG-LSH，该方法通过空间曲线和近邻图来实现邻域快速定位和近邻搜索的局部收敛。作者首先通过空间曲线在复合哈希值上建立一种线序（即字典序）关系，然后对应的原始数据集也是升序排列，这样哈希值相似的点可以被存储在连续的磁盘页上，从而为在查询过程中减少随机I/O访问，实现邻域的快速定位奠定了基础。在近似最近邻查询过程中，引入近邻图，通过查询点所在页面的近邻点进行收敛，从而达到局部近邻优化，提高返回值的准确度。
　　本文通过在四个真实的高维数据集上大量的实验以及对比表明，与当前最新的LSH方法对比，证实NNG-LSH在近似最近邻查询中的准确性和空间需求方面是有优势的。

著录项

作者
王凌霄;
展开▼
作者单位

西安电子科技大学;

展开▼
授予单位西安电子科技大学;
学科计算机科学与技术
授予学位硕士
导师姓名崔江涛;
年度 2017
页码
总页数
原文格式 PDF
正文语种中文
中图分类 TP311.131;
关键词
高维数据; 局部敏感; 空间曲线; 近邻图; 哈希索引; 线性查找; 最近邻查询;

相似文献

中文文献
外文文献
专利

1. 基于数据降维与精确欧氏局部敏感哈希的k近邻推荐方法 [J] . 郭喻栋 ,郭志刚 ,陈刚 . 计算机应用 . 2017,第009期
2. 基于局部敏感哈希的近邻传播聚类 [J] . 刘淑鑫 ,乐嘉锦 . 计算机光盘软件与应用 . 2014,第006期
3. 基于Voronoi图的最近邻查询的索引结构的研究 [J] . 王淼 . 齐齐哈尔大学学报（自然科学版） . 2006,第006期
4. 基于最优排序的局部敏感哈希索引 [J] . 冯小康 ,彭延国 ,崔江涛 . 计算机学报 . 2020,第005期
5. 图上基于局部敏感哈希的多关键字索引 [J] . 韩京宇 ,杨健 . 计算机应用 . 2014,第012期
6. 基于数据降维与精确欧氏局部敏感哈希的k近邻推荐方法 [C] . GUO Yudong ,郭喻栋 ,GUO Zhigang . 第十七届中国Rough集与软计算学术会议、第十一届中国Web智能学术研讨会、第十一届中国粒计算研讨会及第五届三支决策学术会议联合会议（CRSSC-CWI-CGrC-3WD 2017） . 2017
7. 基于局部敏感哈希的近似近邻查询算法研究 [A] . 张梁 . 2015

基于近邻图的局部敏感哈希索引技术研究

目录

摘要

著录项

相似文献

相关主题

期刊订阅