路网中移动对象的索引与查询研究

《路网中移动对象的索引与查询研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、西南大学硕士学位论文路网中移动对象的索引与查询研究姓名：谭晓天申请学位级别：硕士专业：计算机软件与理论指导教师：余建桥20120527摘要路网中移动对象的索引与查询研究计算机软件与理论专业硕士研究生谭晓天指导老师余建桥教授摘要随着GPS定位、无线传感等技术的发展与运用，以及具有定位功能的无线手持、车载设备的普及，使得基于移动对象的位置服务被广泛使用。移动对象的位置等信息随时间发生变化，数据库需要处理时间和空间频繁变化的数据，即时空数据。传统数据库旨在管理更新周期较长的数据，无法适应数据的频繁更新，因此移动对象数据库应运而生。面向路网的移动对象

2、数据库主要是对移动对象的位置等信息进行管理与查询，数据库中通常包含海量的时空数据，建立高效的索引机制是移动对象数据库研究的主要内容。在介绍移动对象数据库技术、分析面向路网的索引结构基础上，本文采用离散模型的表示方法。首先建立基于路段的路网模型，其次充分考虑路网拓扑的结构，引入临近路段信息，提出一种对历史轨迹和实时信息进行管理的IQN-Tr∞(hlde虹ngandQue巧ingt喇ectoriesofmovingobiectSforroadNet、Ⅳork)索引结构。路网模型包含交叉口集合和路段集合两部分，交叉口由二维空间上的点构成，路段由若干

3、条折线构成。IQN．Tree包含上下两层结构。上层结构由路段哈希表和路段2DR-T'ree构成，路段2DR-Tree将路网二维空间划分为若干子索引空间，实现基于路段的空间索引，路段2DR—n∞每个叶结点分别指向下层结构的2DR-Tree森林：路段哈希表主要存储了路段标识号、路段的临近路段信息，路段哈希表中的数据项通过双向指针与路段2DR-1．ree中对应的叶结点想连；路段哈希表进行动态更新，当移动对象首次进入该路段时，增加路段哈希表的相应数据项。下层结构包含了移动对象哈希表、动态链表和移动对象2DR-T．ree森林，2DR—Trec森林索引空

4、间由路段中的相对位置和时间间隔构成，实现对移动对象位置等信息的时空索引；改进下层R．Tr∞的空间划分方法，引入时间维单调递增的原则；按照移动对象的三种进入方式，将每个路段的下层R-1'ree细分为三个R．Tree，上层每个路段的叶子结点指针分别指向下层三个R-1．ree；移动对象哈希表存储了移动对象标识号和实时信息，并通过指针与动态链表相连，动态链表中每个数据项存储了基于时间戳更新的移动对象运动信息。根据路网拓扑结构，查找临近路段信息，设计新型窗口查询的算法并阐述其执行过程。与MoN．Trec索引结构进行性能比较，表明IQN．1he在插入操作

5、、窗口查询、轨迹查询和道路查询等方面具有良好的性能。关键词：临近路段窗口查询索引结构路网AbstractIndexingandQueryingtrajectoriesofm0VlngobjectsforroadNe伽orkMajor：Computerso腑areandTheoryDirection：DatabaseandInformationsystemSupeIVisor：Pro￡YUJian—qiaoAuthor：1hnXiao．tianAbstraCtWlththedeVelopmentand印plicationofGPSpositio

6、nin舀wirelesssensortechnology，笛weU勰tllepopul撕tyofloc撕on-er】旧bledI瑚Adhel也automotiVeequipment，location-b雒edsenriceofmovingoqectiswidelyuSed．LocationofmovingobjectchangesavertilIle，tlledatabaSeneedt0process廿ledatawMChischanged舶quently．Ⅱlespa：ti伊teInporalda：ta．T硼itionalda：协雒eisd

7、esi即edt0m锄agenles枷cda饥soitc锄’tadapttDupdatef}明uemlydata锄dmovingobjectda：t昌lbaSecomesifItobein吕hlroadne觚。比movingobjectda：协舔eiIltendt0que巧andm锄agetllelocationofmoVingobject，d撕baLseusuallycomains锄ountofspatioItempofaldata，esta_blishing锄e街cientinde姬ngmechanismforthemoVingobject

8、isoneofthemostimportantcontent0ndatabase．Ontlleb笛isofin仃oductionf-ormoVingobjectda