软件工程硕士论文-移动对象轨迹的最近邻居查询研究

《软件工程硕士论文-移动对象轨迹的最近邻居查询研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、密级：硕士学位论文论文题目移动对象轨迹的最近邻居查询研究作者姓名×××指导教师×××教授学科(专业)软件工程所在学院软件学院提交日期2007-05-15ADissertationSubmittedtoZhejiangUniversityfortheDegreeofMasterofEngineeringTITLE:NearestNeighborQueryProcessingonMovingObjectTrajectoryAuthor:×××Supervisor:Professor×××Subject:SoftwareEngineeri

2、ngCollege:CollegeofSoftwareTechnologySubmittedDate:May15,2007浙江大学硕士学位论文摘要摘要随着无线通讯和位置定位系统的发展，移动对象数据库（MOD）变得越来越重要，也对数据库研究提出了极大的挑战。基于时间和空间的查询算法成为一些基于位置的服务急需解决的问题。比如：交通控制，近邻信息访问和对野生动物迁徙特性的分析等。而其中一个重要的查询类型就是k最近邻居（kNN）查询。它主要用来查询离某一移动对象最近的k个轨迹。据我们所知，在已有的研究文献中，他们主要处理的是对于一系列连续移

3、动点的将来或者当前位置的查询，这些查询或者基于静态的查询点或者基于连续移动的查询点。但是对于历史移动对象轨迹的最近邻居查询却很少。基于此，在本文中，首先，我们提出了两种基于最佳优先（Best-First）策略的算法：BFPkNN和BFTkNN。分别用来处理静态查询点以及移动轨迹的k最近邻居（kNN）。并且为了减少内存消耗和CPU时间，本文给出了一些有效的剪枝策略。这些剪枝策略能够有效的避免访问那些不可能包含最终结果的节点，也能剔除掉那些不会成为最终结果的迹线段。其次，我们还提出了在历史移动对象轨迹上处理连续k最近邻居查询的两个算法：

4、HCP-kNN和HCT-kNN。同时我们分析并给出了在连续kNN查询中常用的维护和更新k个最近邻居列表（kNearestLists）算法。再次，本文提出了在存储有历史移动对象轨迹的基于R树的索引结构上进行受限k最近邻居（CkNN）查询的概念，以及有效的处理方法。具体来说，为了有效处理CkNN我们提出了区域查询和kNN查询的依次查询方法以及在kNN查询中整合区域查询的方法。另外，我们还给出了两个算法，一个是截取迹线段得到时间域在某一范围内，空间区域包含在受限区域CR内的部分迹线段的算法，另外一个是截取节点获得时间在指定范围内，空间范围

5、在CR内的部分记录的算法。关键词　移动对象轨迹，TB树，k最近邻居查询，受限k最近邻居查询i浙江大学硕士学位论文AbstractAbstractWiththeintegrationofwirelesscommunicationsandpositioningtechnologies,theconceptofMovingObjectDatabases(MOD)hasbecomeincreasinglyimportant,andhasposedagreatchallengetothedatabasecommunity.Emerginglo

6、cation-dependentservicescallfornewqueryprocessingalgorithmsandtechniquestodealwithboththespatialandtemporaldomains.Examplesofthesenewservicesincludetrafficmonitoring,nearbyinformationaccessingandmigrationpatternsanalyzingofwildanimals.Animportantclassofqueriesthatisdef

7、initelyusefulforMODprocessingistheso-calledknearestneighbor(k-NN)queries,whereoneisinterestedinfindingthekclosesttrajectoriestoapredefinedqueryobjectQ.Toourknowledge,intheliteraturesuchqueriesprimarilydealwitheitherstaticorcontinuouslymovingquerypointsoverstationarydat

8、asets,orqueriesaboutthefutureorcurrentpositionsofasetofcontinuouslymovingpoints.Apparently,thesetypesofqueriesdonotco