空间网络环境下基于Voronoi图的时空轨迹查询研究.pdf

《空间网络环境下基于Voronoi图的时空轨迹查询研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、ADissertationSubmittedtoZhejiangUniVersityfortheDegreeofMasterofEngineeringVv⑧TITLE：№!Q望Qi鱼箜呈鱼墨旦型!垒!Q旦皇翌鱼!Trajecto巧DatainSpatialNe锕orks——Author：ShenLiuSuperVisor：‘￡!Q鱼墨墨Q!Q曼塾曼堑g鱼星坠subject：College：ComputerScienceCollegeofConlputerScienceSubmittedDate：2011一01一05浙江大学硕士学位论文———————]嬲嬲幽j摘要移动数据的管理在时空数据库领

2、域占有十分重要的地位，移动数据的运动在数据结构上往往以轨迹的形式体现，之前的针对轨迹数据管理的大多数研究工作主要集中在欧几里得空间下展开，然而，在绝大多数实际场景中，移动对象的运动是在受限的空间网络环境中进行的，如道路网络，水运网络等。在这种情况下，现有的基于欧几里得度量环境的空间数据管理模型就显得过于冗余和低效。本文提出了一种基于网络V0ronoi图(NVD)的空间数据管理模型，通过对网络空间的分区，将广大的空间范围划分为许多小的空间单元，实现了对海量移动对象轨迹的索引。这样，对于每一次空间查询，通过对算法的高效设计，程序只需要访问少量空间单元，便可以得到准确的查询结果，大大减少了查询操

3、作开销，从而实现了针对分布在空间网络环境下的海量时空轨迹数据的高效管理，并通过针对空间网络环境下典型的数据查询——七最近邻查询(七NearestNeighbor舢ery)和范围查询(R觚ge咖)的完整实验验证了模型的准确性和可靠性。关键词：时空数据库，网络‰oi图，轨迹数据，范围查询，七最近邻查询浙江大学硕士学位论文AbstractQlleryprocessingf．or臼向ecto哆dataisve哆impon锄tt0spati0．t即1poraldata_b弱es．Mostofmeresearchworkin也isfieldisbased∞吐leEhclide砚space．HowevI

4、％inmanyapplicatio璐，thespatio—temporal订ajectoriesofmoVingobjectsaredistributedinspatialnetwork∞vironIIlent硫％sivelM锄dthemovemelltsofmovingobjectsarccons仃ainedby西v∞n咖orksegm锄ts．UIldersuchcircllrIlstances，cxistil培Euclide锄-b筋edmethodsarcine仃色ctive．Illtllispaper，wepresentaNetwork、，0】ronoiDiag咖《NVl))b弱ed

5、memod，t0solveknearestquery趾dmgequeryprobl锄伽ahuge锄ountofspatio．tempoml仇0ectori骼inspatialne锕orks．Theb舔icideaisspacepartition．AlaIIgen咖od【spaceispanitionedint0m锄ysmallcells．So，foreachqueⅨ0nlyasmall眦mbcrofcellsotllefm锄mewholene铆orkspacew舔processed．Andthedata_bsesystembecomesmo聆efficiclltbythisway．Thee

6、xperimentsdemonsn-ated血atollrmeⅡ10disverye伍cienteveIlⅥm饥thetr勾ectoD，datasetsarehuge．。Keywords：Spatio-t锄poralda_讪髑e，V0ronoidiagram，媳jectoⅨr锄gequeⅨ，knearestneighborquery浙江大学硕士学位论文目录摘要⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．iAbs臼?act⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．ii第1章绪论⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

7、⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。l1．1研究背景及意义⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．11．2相关研究及存在问题⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯51．2．1最近邻查询相关研究及存在问题⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。51．2．2区域查询相关研究及存在问题⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。61．3研究目标及内容⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．81．4本文结构组织⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯