原文传递
路网中移动对象的索引与查询研究
| 论文题名： | 路网中移动对象的索引与查询研究 |
| 关键词： | 窗口查询;索引结构;路网拓扑;移动对象;离散模型 |
| 摘要： | 随着GPS定位、无线传感等技术的发展与运用,以及具有定位功能的无线手持、车载设备的普及,使得基于移动对象的位置服务被广泛使用。移动对象的位置等信息随时间发生变化,数据库需要处理时间和空间频繁变化的数据,即时空数据。传统数据库旨在管理更新周期较长的数据,无法适应数据的频繁更新,因此移动对象数据库应运而生。面向路网的移动对象数据库主要是对移动对象的位置等信息进行管理与查询,数据库中通常包含海量的时空数据,建立高效的索引机制是移动对象数据库研究的主要内容。 在介绍移动对象数据库技术、分析面向路网的索引结构基础上,本文采用离散模型的表示方法。首先建立基于路段的路网模型,其次充分考虑路网拓扑的结构,引入临近路段信息,提出一种对历史轨迹和实时信息进行管理的IQN-Tree(IndexingandQueryingtrajectoriesofmovingobjectsforroadNetwork)索引结构。 路网模型包含交叉口集合和路段集合两部分,交叉口由二维空间上的点构成,路段由若干条折线构成。IQN-Tree包含上下两层结构。上层结构由路段哈希表和路段2DR-Tree构成,路段2DR-Tree将路网二维空间划分为若干子索引空间,实现基于路段的空间索引,路段2DR-Tree每个叶结点分别指向下层结构的2DR-Free森林:路段哈希表主要存储了路段标识号、路段的临近路段信息,路段哈希表中的数据项通过双向指针与路段2DR-Tree中对应的叶结点想连;路段哈希表进行动态更新,当移动对象首次进入该路段时,增加路段哈希表的相应数据项。下层结构包含了移动对象哈希表、动态链表和移动对象2DR-Tree森林,2DR-Tree森林索引空间由路段中的相对位置和时间间隔构成,实现对移动对象位置等信息的时空索引;改进下层R-Tree的空间划分方法,引入时间维单调递增的原则;按照移动对象的三种进入方式,将每个路段的下层R-Tree细分为三个R-Tree,上层每个路段的叶子结点指针分别指向下层三个R-Tree;移动对象哈希表存储了移动对象标识号和实时信息,并通过指针与动态链表相连,动态链表中每个数据项存储了基于时间戳更新的移动对象运动信息。根据路网拓扑结构,查找临近路段信息,设计新型窗口查询的算法并阐述其执行过程。与MON-Tree索引结构进行性能比较,表明IQN-Tree在插入操作、窗口查询、轨迹查询和道路查询等方面具有良好的性能。 |
| 作者： | 谭晓天 |
| 专业： | 计算机软件与理论 |
| 导师： | 余建桥 |
| 授予学位： | 硕士 |
| 授予学位单位： | 西南大学 |
| 学位年度： | 2012 |
| 正文语种： | 中文 |
检索历史
应用推荐
