基于区域覆盖连续移动查询算法的研究和实现

《基于区域覆盖连续移动查询算法的研究和实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据AThesisinComputerApplicationTechnologylMIIHIlllJIIIIJJillJlJIfIlJllIlfllllllilllJ019567ResearchandImplementationofContinuousMovingQueryAlgorithmsBasedonCoveredAreaByWangXiaosongSupervisor：ProfessorWangBomoNortheasternUniversityJune2012万方数据独创性声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加

2、以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢=蕾恧。学位论文作者签名：王小序幺日期：z口肛．多．2牛学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：半年历一年口一年半口两年口学位论文作者签

3、名：王小未：2：签字日期：知／2、多、2y导师签名：王：／I乏衙签字Et期：2O／2．∥．2牛万方数据东北大学硕士学位论文摘要基于区域覆盖的连续移动查询算法的研究与实现摘要基于位置服务的空间查询在交通导航、救援服务以及数字战场等诸多领域有着广泛的应用前景。近年来，随着无线通信和全球定位系统(GlobalPositioningSystem，GPS)定位技术的发展，移动环境下的查询技术的研究已经成为移动数据库领域的热点。由于移动环境下的查询对象和被查询对象均是不断变化的，因此移动环境下的查询比较复杂，并且研究成果较少。连续查询不同于只需计算一次的传统查询，它需要在一段

4、时间内持续维护查询结果，因此在移动环境下实现起来更加具有挑战性。本文主要针对移动环境下的两类空间查询技术展开研究，分别是连续范围查询和连续K近邻查询。首先，Del．VGQ索引是一个层次索引，由Dela蚰ay三角网和虚拟网格四分树(VirtualGridQuadtree，VGQ)构成。它具备YVGQ索引的快速定位特点和Delaunay=．一角网能表达对象的邻近性质，该索引适合做移动查询，但是该索引不能直接完成连续移动查询，因此本文扩展了Del．VGQ索引。通过分析移动环境下对象的特性，本文在扩展后的Del．VGQ索引的基础上提出了连续范围查询算法DelVGQRang

5、eQuery并且证明了该算法的准确性。接着本文为了验证算法的性能进行了仿真实验。实验结果表明基于区域覆盖的连续范围查询比用TPR-树索引下的连续范围查询的cpu时间快了一个数量级。其次，本文分别在VGQ索引和扩展后的Del．VGQ索引的基础上提出了两种连续K近邻查询算法VGQKnnQuery和DelVGQKnnQuery，并且分别给出了两种算法的正确性证明。接着本文为了验证算法的性能进行了仿真实验。实验结果表明，VGQKrmQuery的查询响应时间慢于DelVGQKnnQuery的查询响应时间，而更新时间前者较快。这是由两个索引的结构和查询算法执行的过程决定的。另

6、外，DelVGQKrmQuery对大数据量具有很好的适应性。最后，本文对路网环境下的连续K近邻查询进行了研究。上述的连续K近邻查询是用欧式距离作为移动对象问的距离，而路网环境下的连续K近邻查询的距离是移动对象问的最短路径距离。因此本文先对路网进行建模，接着利用建好的路网模型实现连续K近邻查询并对查询算法完成正确性证明，最后为了验证算法的性能做了仿真实验。实验结果表明本文的连续K近邻算法CMKNN的cpu时间比传统的IMA算法快了一个数量级。关键词：移动对象索引；移动查询；连续范围查询；连续K近邻查询万方数据ResearchandImplementationofCo

7、ntinuousMovingQueryAlgorithmsBasedonCoveredAreaAbstractSpatialqueriesbasedonlocationserviceshaveextensiveapplicationprospectsinmanyareas，suchaStrafficnavigation，therescueservice，digitalbattlefieldandSOon．Inrecentyears，alongwiththedevelopmentofwirelesscommunicationandglobalpositionings

8、ystem