移动对象轨迹的最近邻居查询研究

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

1、浙江大学硕士学位论文移动对象轨迹的最近邻居查询研究姓名：李春申请学位级别：硕士专业：计算机科学指导教师：陈根才20070515浙江大学顽}学位论文AbstractWiththeintegrationofwirelesscommunicationsandpositioningtechnologies，theconceptofMovingObjectDatabases(MOD)hasbecomeincreasinglyimportant，andhasposedagreatchallengetothedatabasecommunity．Emerginglocation-dependentservi

2、eescallfornewqueryprocessingalgorithmsandtechniquestodealwithboththespatialandtemporaldomains．Examplesofthesenewservicesincludetrafficmonitoring，nearbyinformationaccessingandmigrationpatternsanalyzingofwildanimals．AnimportantclassofquefiesthatisdefinitelyusefulforMODprocessingistheso．calledknearest

3、neighbor(k-NN)queries，whereoneisinterestedinfindingthekclosesttrajectoriestoapredefinedqueryobjectQ．Toourknowledge，intheliteraturesuchqueriesprimarilydealwitheitherstaticorcontinuouslymovingquerypointsoverstationarydatasets，orqueriesaboutthefutureorcurrentpositionsofasetofcontinuouslymovingpoints．A

4、pparently,thesetypesofqueriesdonotcoverNNsearchonhistoricaltrajectories．Motivatedbythisproblem，i耳thispaper,WedeveloptwoalgorithmsbasedonBest．Firsttraversalparadigm，calledBFPkNNandBFTkNN，whichhandlethekNNretrievalwitIlrespecttothestaticquerypointandthemovingquerytrajectory,respectively．Inaddition，we

5、alsoenableseveraleffectivepruningheuristicstopruneawayallunnecessarynodessuchthatthememoryspaceconsumptionandtheCPUtimecanbedecreased．Thepruningheuristicsavoidsaccessingnodesthatcannotconminquailfyingentriesanddiscardanyunnecessaryentries．Wealsopresenttwoalgorithms，calledHCp—kNNandHCT—kNN，whichdeal

6、withtheproblemofefficientlyprocessingllistoricalcontinuousk-NearestNeighbor．AneffectiveupdatestrategytomaintainthenearestlistsisproposedforcontinuouskNNsearch．Furthermore，Weintroduceandsolvetheconstrainedk-nearestneighbor(CkNN)queryonR—tree—likestructuresstoringhistoricalinformationaboutmovingobjec

7、ttrajectofies．WepresentseveralalgorithmstohandletheCkNNqueryproblemefficiently．Inparticular,ourtechniquesprocessCkNNqueriesbyeithercombiningconditionsofrangeandkNNi；浙江人学帧I学位论文Abstractqueries，orbymodifyingth