基于R-树的最近邻查询研究-韩冬柏.doc

理学硕士学位论文基于R-树的最近邻查询研究韩冬柏哈尔滨理工大学2011年3月国内图书分类号:TP391理学硕士学位论文基于R-树的最近邻查询研究硕士研究生:韩冬柏导师:刘润涛申请学位级别:理学硕士学科、专业:应用数学所在单位:应用科学学院答辩日期:2011年3月授予学位单位:哈尔滨理工大学ClassifiedIndex:TP391DissertationfortheMasterDegreeinScienceResearchonNearestNeighborQueryBasedonR-TreeCandidate:HanDongbaiSupervisor:LiuRuntaoAcademicDegreeAppliedfor:MasterofNaturalScienceSpeciality:AppliedMathematicsDateofOralExamination:March,2011University:HarbinUniversityofScienceandTechnology哈尔滨理工大学硕士学位论文原创性声明本人郑重声明:此处所提交的硕士学位论文《基于R-树的最近邻查询研究》,是本人在导师指导下,在哈尔滨理工大学攻读硕士学位期间独立进行研究工作所取得的成果。据本人所知,论文中除已注明部分外不包含他人已发表或撰写过的研究成果。对本文研究工作做出贡献的个人和集体,均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。作者签名:韩冬柏日期:2011年3月23日哈尔滨理工大学硕士学位论文使用授权书《基于R-树的最近邻查询研究》系本人在哈尔滨理工大学攻读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔滨理工大学所有,本论文的研究内容不得以其它单位的名义发表。本人完全了解哈尔滨理工大学关于保存、使用学位论文的规定,同意学校保留并向有关部门提交论文和电子版本,允许论文被查阅和借阅。本人授权哈尔滨理工大学可以采用影印、缩印或其他复制手段保存论文,可以公布论文的全部或部分内容。本学位论文属于保密 ,在年解密后适用授权书。√。不保密。。(请在以上相应方框内打√)作者签名:韩冬柏日期:2011年3月23日导师签名:刘润涛日期:2011年3月23日基于R-树的空间最近邻查询研究摘要最近邻查询是空间数据查询领域中最重要的查询技术之一,在地理信息系统(GIS),计算机辅助设计与制造(CAD/CAM),智能识别系统,多媒体的应用等各个方面都有广泛的应用。同时随着科学技术的快速发展,对最近邻查询的效率的要求也越来越高,本文从研究最常用的空间索引技术R-树出发,对R-树的查找算法、插入算法、删除算法等进行了探讨,给出了相应的伪代码,并运用相关的性质对R-树的各种算法过程进行优化。本文研究的是最近邻查询中两个应用较广泛的方面,K最近邻(KNN)查询和障碍最近邻查询(ONN)。在KNN中我们研究了静态的K最近邻查询和动态的K最近邻查询,并给出了相应的算法、伪代码和算法解释。然后我们把空间数据索引技术R-树应用到KNN的查询算法中,运用最小距离(MINDIST)和最大最小距离(MINMAXDIST)来对R树的结点进行排序和剪枝,建立了用于查询的剪枝规则。并给出了基于R-树的K最近邻查询算法,给出了剪枝过程的策略和算法的伪代码。在对障碍最近邻的研究中,把实际应用中的障碍看作多边形。并给出了求解多边形可视点的算法,然后只需考虑障碍多边形的可视点,过滤掉了大部分障碍点,再运用R-树的查询知识对这些可视点进行分类,并求出其最短路径,所得的最短路径就是所求的点与点之间的障碍距离。关键词空间数据库;R-树;K最近邻;障碍最近邻ResearchonNearestNeighborQueryBasedonR-,suchasthegeographicalinformationsystem(GIS),computeraideddesignandmanufacturing(CAD/CAM),intelligentidentificationsystem,andmultimediaapplications,,withtherapiddevelopmentofscienceandtechnology,-trees,monlyusedi