基于var_树的反向最近邻查询技术的研究

《基于var_树的反向最近邻查询技术的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士研究生：修建新导师：郝忠孝申请学位级别：工学硕士学科，专业：计算机系统结构所在单位：计算机科学与技术学院答辩日期：2010年3月授予学位单位：哈尔滨理工大学卜■Cl弱sifiedIndex：TP3llDissertationfortheMasterDegreeinEngineeringResearchofReversenearestNeighborQueryBasedonVAR*-TreeCandidate：Supervisor：XiuJianxinHaoZhongxiaoAcademicDegree

2、Appliedfor：MasterofEngineeringSpecialty：ComputerSystemsOrganizationDateofOralExamination：March，2010University：HarbinUniversityofScienceandTechnology哈尔滨理工大学硕士学位论文原创性声明本人郑重声明：此处所提交的硕士学位论文I：基于VAR*树的反向最近邻查询技术的研究》，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期间独立进行研究工作所取得的成果。据本人所知

3、，论文中除已注明部分外不包含他人已发表或撰写过的研究成果。对本文研究工作做出贡献的个人和集体，均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。’作者签名：弱旋韵日期：孙年卑月石日哈尔滨理工大学硕士学位论文使用授权书《基于VAR*树的反向最近邻查询技术的研究》系本人在哈尔滨理工大学攻读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔滨理工大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全了解哈尔滨理工大学关于保存、使用学位论文的规定，同意学校保留并向有关部门提交论文和

4、电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内容。本学位论文属于保密口，．在年解密后适用授权书。不保密囱。(请在以上相应方框内打4)作者签名：耥导师签名：删日期：卯／o年牛月6日日期：乒町。年够月／日哈尔滨理土大学工学硕士学位论文基于Ⅵ蛾木树的反向最近邻查询技术的研究摘要在空间数据库中，反向最近邻查询技术是最重要的查询技术之一，它是在最近邻查询技术的基础上提出的，反向最近邻查询技术是空间数据库技术研究的重点和难点，如何有效地实现反

5、向最近邻查询一直是人们研究的热点问题。目前对反向最近邻查询的研究还不是很多，它们都存在着一定的缺陷，比如查询效率不高，不适合高维空间的查询等等。本文对目前国内外反向最近邻查询的研究成果进行分析，在原有研究的基础上提出了本文的观点，主要内容包括以下几个方面。首先，为了有效地实现反向最近邻查询，本文提出了一种新的索引结构VAR*．Tree。VAR*树是在原有的VAR树的基础上做了改进，引入了性能优良的SR树。VAR*树的构造过程主要包括对原始数据的量化压缩和把量化压缩后的近似数据用SR树来进行管理(用近似数据

6、构造一棵SR树)两个步骤。这种索引结构的优点是对原始数据的量化压缩能够大大减少存储空间，引入的SR树的索引结构也更加适合反向最近邻查询的要求。经实验验证，VAR*树的索引结构较SR树索引结构占用空间更小、更适合查询的需要。其次，在VAR*树的基础上给出了基于VAR*树的最近邻查询算法VAR*NN算法，还给出了基于VAR*树的KNN算法。算法经实验验证查询效率优于以往的最近邻查询算法。再次，在VAR*树的基础上给出了基于VAR*树的反向最近邻查询算法VAR*RNN算法，还给出了VAR*RNN算法相关的插入和

7、删除算法。经实验验证算法在2维和11维的空间下，查询效率优于以往的反向最近邻查询算法。总之，本文提出的新的索引结构VAR*．Tree，它的性能优越，更适合最近邻查询和反向最近邻查询，提高了它们的查询效率。与其他算法的查询效率相比有了一定的提高，特别是在高维空间查询时，体现了良好的性能。关键词空间索引；SR树；VAR*树；最近邻查询；反向最近邻查询哈尔滨理工大学工学硕士学位论文ResearchofReversenearestNeighborQueryBasedonVAR*-TreeAbstractInthe

8、spatialdatabase,thereversenearestneighborqueryisoneofthemostimportantqueries,whichisbasedonthenearestneighborquery．Itisthefocusanddifficultofspatialdatabasetechnology,howtotheeffectivehnplementationoftherI*傩ene硼燃tne