基于邻域碰撞计数的局部敏感哈希索引

《基于邻域碰撞计数的局部敏感哈希索引》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学校代码10701学号1403121522分类号TP39密级公开西安电子科技大学硕士学位论文基于邻域碰撞计数的局部哈希索引作者姓名：王磊一级学科：计算机科学与技术二级学科：计算机系统结构学位类别：工学硕士指导教师姓名、职称：崔江涛教授学院：计算机学院提交日期：2018年6月LocalitysensitivehashingindexbasedonneighborhoodcollisioncountingAthesissubmittedtoXIDIANUNIVERSITYinpartialfulfillmentofther

2、equirementsforthedegreeofMasterinComputerSystemsOrganizationByWangLeiSupervisor:CuiJiangtaoTitle:ProfessorJune2018摘要摘要数据不仅仅是信息的一种表达方式，更是潜在信息的载体。低维度的数据集通过传统数据库的方法很容易查询。近年来，数字化和网络化带来了数据的繁荣，图像和视频数据在整个大数据的比例已经要接近90%，非结构化的数据集导致了特征向量维度和特征向量集规模巨大，海量高维数据对数据库管理带来了诸多挑战和机遇

3、。其中，海量高维数据的索引和查询作为一个十分重要的问题亟待解决。因此基于高维最近邻查询（NN:NearestNeighbor）得到了广泛的关注和不断的优化。其优势一方面在于高效率的存储方式和高速率的索引结构，同时另一方面保证在很多情况下有这良好的准确率。在实际应用中已成为解决海量高维数据检索研究的基础技术之一。解决海量高维数据近邻查询问题的方法可分为两大类：其一，局部敏感哈希（LSH:Locality-SensitiveHashing）及其变种，通过随机映射或投影将高维特征映射成哈希编码，生成哈希函数。这样原始数据相邻

4、的两个点在新的空间中相邻的概率依然很大而不相邻的点映射进同一空间的概率很低。其二，近邻图（NNG:NearestNeighborGraph），随机选取一点，充分利用数据点间邻域关系，通过构造图结构将候选点与其邻居进行比较从而提供近邻收敛路径，迭代更新候选点。本文首先对局部敏感哈希计数、近邻图进行了重点的关注和研究分析。在基于?稳定分布的局部敏感哈希中，不同的哈希方法使用不同的策略重新组织哈希编码，但这些哈希编码重组策略使得哈希函数顺序静态化，可能会导致算法拒绝某些近邻被选作候选点。碰撞计数哈希(C2LSH：Collis

5、ionCountingLocality-SensitiveHashing)采用十分灵活的动态计数策略选择候选点，使得近邻更容易被选作候选点。值得注意的是，在C2LSH中，哈希函数的选取个数不受数据对象的维度影响，这使得C2LSH特别适合高维NN搜索。通过少量精度以求的近似最近邻而获取效率上的提升。为了对碰撞计数局部敏感哈希的效率和精准性进行进一步优化，本文提出将通过碰撞计数和近邻图两种不同的方式更新候选点集，通过近邻的邻居可能也是一个好的近邻这个原则进行邻域投票，重新计数后优化候选点集。通过较少较优的候选集点来实现高精

6、度的近似最近邻查询，使得哈希编码对距离查询较近的数据对象具有更好的区分度。将邻域碰撞哈希与近邻图结合起来，以较高的召回率和精准率实现高维数据的快速近似最近邻查询。本文通过在不同的高维数据集上的大量实验，其实验结果表明了基于邻域碰撞计数的局部敏感哈希索引与当前流行的LSH方法在性能上是有一定的优势，也证明了局部敏感哈希所产生的编码能够在精准率、平均响应时间等方面有进一步的提升空间。I西安电子科技大学硕士学位论文关键词：局部敏感哈希，近似最近邻查询，高维索引结构，邻域投票，近邻图IIABSTRACTABSTRACTData

7、isnotonlyanexpressionofinformation,butalsoacarrierofpotentialinformation.Low-dimensionaldatasetsareeasilyqueriedbytraditionaldatabasemethods.Inrecentyears,digitalizationandnetworkinghavebroughtaboutaboomindata,andtheproportionofimageandvideodataintheentirebigdat

8、ahasapproached90%.Unstructureddatasetshaveresultedinahugescaleofeigenvectorsandfeaturevectorsets.Dimensionaldatabringsmanychallengesandopportunitiestodatabasemanageme