高维数据最近邻查询算法研究

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

1、高维数据最近邻查询算法研究作者姓名原玥导师姓名、职称崔江涛教授一级学科计算机科学与技术二级学科计算机系统结构申请学位类别工学硕士提交学位论文日期2014年11月学校代码10701学号1203121564分类TN82号TN82密级公开西安电子科技大学硕士学位论文高维数据最近邻查询算法研究作者姓名：原玥一级学科：计算机科学与技术二级学科：计算机系统结构学位类别：工学硕士指导教师姓名、职称：崔江涛教授提交日期：2014年11月4AStudyofNearestNeighborSearchinHigh-dimenti

2、onalSpaceAthesissubmittedtoXIDIANUNIVERSITYinpartialfulfillmentoftherequirementsforthedegreeofMasterinElectronicScienceandTechnologyByYuanyueSupervisor:Prof.CuijiangtaoNov.20146西安电子科技大学学位论文独创性（或创新性）声明秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我

3、所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。学位论文若有不实之处，本人承担一切法律责任。本人签名：日期：西安电子科技大学关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属于西安电子科技大学。学校有权保留送交论文的复印件，允许查

4、阅、借阅论文；学校可以公布论文的全部或部分内容，允许采用影印、缩印或其它复制手段保存论文。同时本人保证，获得学位后结合学位论文研究成果撰写的文章，署名单位为西安电子科技大学。保密的学位论文在年解密后适用本授权书。本人签名：导师签名：日期：日期：摘要摘要高维数据空间中的最近邻查询问题被广泛应用于数据库，图像检索和许多其它相关领域。受“维数灾难”的影响，这一问题变得越来越重要。本文研究且实现了DCR（DataCo-Reduction）算法。使用近年研究所得的联合聚类方法，DCR通过压缩原始数据集合的规模和维数，

5、将高维数据集合压缩至更加紧密的子空间中。索引结构同K最近邻查询过程本文使用了过滤和精炼策略。本文通过使用联合聚类算法建立了更加紧确的距离下界。因此DCR算法能够有效提升k最近邻查询算法的效率。特别的，DCR算法通过同时考虑到数据集合规模和维数的二元性，实现了相似性查询的最优化。实验结果表明在大规模数据集合上DCR算法在过滤能力和查询响应时间两方面都有着优秀的性能表现。近年来，DCR算法被认为是K最近邻查询领域非常优秀的解决方法。然而，由于该算法在访问候选点时需要进行大量的随机I/O，效率上受到影响。为了保证

6、返回结果的质量，需要访问足够多的查询对象，由此会带来大量的I/O开销。为了解决这一问题，本文提出了一个新的索引方法，ZOrder索引，该索引结构通过最大化单次I/O中访问候选点的数目，使得查询中磁盘页面I/O次数最小。本文的主要贡献可以总结为：首先，本文根据数据点的访问顺序定义了能够评估数据集合中两个数据点ZOrder编码之间距离的方式。由此能够得到数据集合对应的ZOrder编码集合的编码线序关系，并且根据该线序关系实现对数据点的排序。其次，本文证明了ZOrder索引算法能够将具有相似ZOrder编码的数据

7、点存储在连续的磁盘页面。在最近邻搜索过程中，ZOrder索引算法在较少次数的硬盘内存间的I/O就能完成。在几次硬盘内存间I/O之后，便能得到足够多的候选点，从而不仅大幅度减少查询响应时间，也提高了返回结果的准确度。通过对真实数据集合上的实验，并同经典的最近邻查询算法的实验结果的比对分析，能够证明ZOrder索引算法良好的空间和时间效率。关键词：量化编码，数据联合聚类，过滤和精炼，高维索引，检索论文类型：基础研究类I西安电子科技大学硕士学位论文IIABSTRACTABSTRACTTheNearestNeigh

8、borSearch(NNSearch)inhigher-dimensiondataspaceiswidelyappliedindatabase,imageprocessingandmanyotherrelevantareas.FacedwiththeCurseofDimensionalityproblemwhichbecomesmoreandmoreseriousweinvestigateandimplement