海量数据的高效近似近邻查询研究

《海量数据的高效近似近邻查询研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号；密级１０１５１ＵＤＣ：竿位代码馨乂是洛事乂掌全日制应用型硕±研究生学位论文海量数据的高效近似近邻查询研究周見指导教师曲雲蔬教授企业导师旨宏伟高级工程师申请学位类别工程硕±工程领域计算化技术学位授予单位大连海事大学２０１６年６月分类号密级ＵＤＣ单位代码１０１５１大连海事大学工程硕±学位论文海量数据的髙效近似近邻查询研巧（学位论文形式：应用研究）周亮指导教师曲委歸职称教授企业导师吕宏伟

2、职称高级工程师学位授予单位大连海事大学申请学位级别工程硕±王程领域计算机技术论文完成日期２０１６年６月答辩日期２０１６年６月答辩委员会主席ＳｔｕｄｏｎｔｈｅＥｆｆｉｃｉｅｎｔＡｒｏｘｉｍａｔｅＮｅａｒｅｓｔＮｅｉｈｂｏｒＳｅａｒｃｈｙｐｐｇ化ｒＭａｓｓｉｖｅＤａｔａＡｆｈｅｓｓ：ｉＳｕｂｍｉｔｔｅｄ化ＤａｌｉａｎＭａｒｉｔｉｍｅＵｎｉｖｅｒｓｉｔｙＩｎａｒｔｉａｌｆｕｌ打Ｕｍｅｎｔｏｆｔｈｅｒｅｕｉｒｅｍｅｎｔｓｆｏｒｔｈｅｄｅｒｅｅ

3、ｏｆｐｑｇＭａｓｔｅｒｏｆＥｎｉｎｅｅｒｉｎｇｇｂｙＺｈｏｕＬｉａｎｇＣｏｍｕｔｅｒｔｅｃｈｎｏｌｏ（ｐｇｙ）ＴｈｅｓｉｓＳｕｐｅｒｖｉｓｏｒ：ＰｒｏｆｅｓｓｏｒＱｕＷｅｎｙｕ？Ｊｕｎｅ２０１６大连海事大学学位论文原创性声明和使用授权说明原创性声明本人郑重声明；本论文是在导师的指导下，独立进行研究工作所取得的成果，＂海量数据的高效近似近邻查询研究＂撰写成硕±学位论文。除论文中己经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均己在文中明确方式标明。

4、本论文中不包含任何未加明确注明的其他个人或集体己经公开发表或未公开发表的成果。本声明的法律责任由本人承担。学位论文作者签名：学位论文版权使用授权书本学位论文作者及指导教师完全了解大连海事大学有关保留、使用研究生学，目位论文的规定Ｐ：大连海事大学有权保留并向国家有关部口或机构送交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可Ｗ将本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论文。同意将本学位论文收录到《中国优秀博硕±学位论

5、文全文数据库》（中国学术期刊（光盘版）电子杂志社）、《中国学位论文全文数据库》（中国科学技术信息研究所）等数据库中，并Ｗ电子出版物形式出版发行和提供信息服务。保密的论文在解密后遵守此规定。本学位论文属于：保密□在年解密后适用本授权书。＂＂不保密｛／（请在Ｗ上方框内打Ｖ）论文作者签名：导师签名一曰期：ｙ年月曰（（中文摘要摘要随着大数据时代的到来，人们往往很难在规定时间内，利用常规方法对海量数据的内容进行管理，其潜在、分析和处理。但是数据规模越大的价值也就越大。因此，如何在

6、大数据中快速、有效地检索到相似的目标数据成为目前计算机界研究的一个热点问题。近年来，学者们提出近似最近邻检索方法，通过数据索引来加快目标数据的在线检索速度。局部敏感哈希ＬｏｃａｌｉｔｙＳｅｎｓｉｔｉｖｅＨａｓｈｉｎｇ与随机网格（ＲａｎｄｏｍＧｒｉｄｓ（））一，这两种方法都存在是目前研究此问题的两种有效方法，但研究中发现定的问题。局部敏感哈希算法为了保证准确度，需要建立多张索引表，所Ｗ空间复杂度较高；随机网格方法则需要创建很多的副本，从而耗费更多的外存空间。为了解决近似近邻算法中精确度不高和占用

7、空间过多的问题，本文结合局部一一敏感哈希与随机网格算法的优点，提出种新的方法基于网格的局部敏感哈希算法，对数据进行网格划分，这样会尽。本文算法吸取随机网格中划分网格的思想可能保留原始数据的空间近邻结构。同时，利用局部敏感哈希技术处理高维数据的，进而通过索引检索近邻数据。这种方法可Ｗ利用网格索引优势，对网格进巧检索优势提高检索精度，同时也能有效地减少网络传输量。我们在ＭａｐＲｅｄｕｃｅ并行编程框架下，对本文算法进行了实现，实验中算法具有良好的可扩展性。实验结果表。明，本文提出的算法在处理高维空间的

8、海量数据时会表现出较好的性能关键词！大数据；ＭａｐＲｅｄｕｃｅ；近似最近邻捜索；局部巧感哈希；网格索引英文摘要ＡＢＳＴＲＡＣＴＷｉｔｈｔｈｅａｒｒｉｖａｌｏｆｔｈｅｅｒａｏｆｂｉｄａｔａｍａｎｍａｓｓｉｖｅｄａｔａｈａｖｅｂｅｅｎｕｎａｂ