基于动态矩形遍历搜索的k-nn查询算法

《基于动态矩形遍历搜索的k-nn查询算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文基于动态矩形遍历搜索的K-NN查询算法申请人姓名：指导教师：专业名称：研究方向：汤金娥李国斌计算机应用技术计算机网络河南理工大学计算机科学与技术学院二○一○年十二月万方数据万方数据中图分类号：P628密级：公开UDC：620单位代码：10460基于动态矩形遍历搜索的K-NN查询算法ANewK-NNQueryAlgorithmBasedontheTraversalandSearchoftheDynamicRectangle申请人姓汤金娥申请学位硕士名学科专业计算机应用技研究方向术计算机网络导师

2、李国斌职称副教授提交日期2010.10答辩日期2010.12河南理工大学万方数据万方数据河南理工大学学位论文原创性声明本人郑重声明：所呈交的学位论文，是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除了特别加以标注和致谢的地方外，不包含任何其他个人或集体已经公开发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明并表示了谢意。本人愿意承担因本学位论文引发的一切相关责任。学位论文作者签名:年月日河南理工大学学位论文使用授权声明本学位论文作者及导师完全了解河南理工大

3、学有关保留、使用学位论文的规定，即：学校有权保留和向有关部门、机构或单位送交论文的复印件和电子版，允许论文被查阅和借阅，允许将本学位论文的全部或部分内容编入有关数据库进行检索和传播，允许采用任何方式公布论文内容，并可以采用影印、缩印、扫描或其他手段保存、汇编、出版本学位论文。保密的学位论文在解密后适用本授权。学位论文作者签名：导师签名：年月日年月日万方数据万方数据致谢在河南理工大学两年半的硕士研究生生活即将结束。回想这两年半的学习时光，我学到了很多东西，生活过得既充实又有意义。在这儿我首先要向河南理工大学致以

4、我最衷心最真诚的谢意，我在这儿度过了两年半的时间，给我留下了美好的回忆。非常感谢我的导师李国斌老师从我研究生入学以来一直以来谆谆教导我,给了我很多鼓励，李老师一直以来在空间数据库领域给我莫大的帮助，对我悉心指导，严格要求、热情鼓励，为我创造了很多锻炼提高的机会，从最初的定题，到资料收集，到写作、修改，到论文定稿，他给了我耐心的指导和无私的帮助。在我们反复地探讨和交流下，我选择了目前国内研究最少、也最热门，而且也是最有难度的空间数据库索引中的K-NN查询算法作为我的毕业设计，从开题一直到最后论文初稿，李老师倾注了大量的心血

5、和精力，我们对最后的研究成果感到很满意。感谢计算机科学与技术学院的领导和老师们在我读研期间所给予的关心和支持。感谢各位评审论文的专家能在百忙之中抽出时间对我的硕士论文进行评审，并提出宝贵的意见，在此表示最衷心的感谢！在此我向我的导师以及在毕业设计过程中给予我很大帮助的老师、同学们致以最诚挚的谢意！万方数据万方数据摘要随着移动计算、无线通信以及定位技术的快速发展，大量的应用领域，如交通、商贸、物流、气象、军事等，积累了巨大的空间数据。人们迫切需要对这些数据进行各种查询分析以便发现其隐藏的知识或做出正确的决策。本文首先分析了

6、利用传统的树索引和网格索引进行K-NN查询的优缺点，基于树索引的K-NN算法，采用测量距离和剪枝策略提高查询效率，在继续查找下一近邻时，往往需要大量的距离计算以便排除不必要的查找区域，在数据量庞大的情况下，频繁的计算距离所花费的时间代价很大，算法查询效率急剧下降，基于网格索引的K-NN查询算法，通过计算被查询对象与其周围八个网格中的对象距离，获取近邻对象，并一层层向外扩大查询范围，查询范围不灵活，会出现空网格单元使得近邻对象的查询次序与实际排序顺序不一致，致使搜索缓慢，存储利用率低。本文提出了基于动态矩形遍历搜索的K-N

7、N查询算法，采用聚类方法将空间数据对象聚类到被查询对象所在的水平和竖直方向，选择大小合适的矩形动态进行移动以获取下次进行查询的范围，采用动态矩形进行遍历搜索K-NN对象，由于将数据对象进行聚类，使得每类中数据对象间距变小，动态矩形在每个方向的查询区域不为空，节省了存储空间，采用要查找的K-NN对象数目来选取动态矩形的大小，排除了人为性，查找范围具有很大随机性，由实际数据对象的空间分布决定，动态矩形大小更为合理，同时有效排除了当前不必要查询的区域，在四个方向上是循环进行查找，每次遍历过程中，动态矩形只在一个方向进行一次数据

8、对象范围划分，查找完后，便转向下一个方向进行避免了某方向长期被占用，由于下一个查找方向是上次遍历过程中下一个具有最小近邻距离的方向，所查找的近邻对象之间的顺序趋于最终结果排序顺序，只需进行少量对象间的调整即可，提高了查询效率。论文在采用Java开发技术实现了对基于动态矩形遍历搜索的K-NN查询算法方法的仿真测试。然后