论文部分内容阅读
随着移动设备、无线通信和GPS的大量应用,催生了一类基于位置的服务(Location based service)。位置服务提供给查询者关于移动对象随时间变化的位置信息,数据库需要处理不断频繁更新的时空数据,而传统数据库一般只能处理更新周期比较长的数据,无法响应数据的频繁更新,因此时空数据库应运而生。在现实环境中,大多数的移动对象在二维空间中做受限运动(公交车在交通道路上按公交路线行驶),而不是自由运动(轮船在大海中自由航行),因此研究受限环境中的移动对象数据库的相关技术更具现实意义,而建立高效的索引机制是移动对象数据库的研究重点。目前,成熟的索引结构只能实现移动对象的历史轨迹和实时位置查询,不能预测移动对象在将来时刻的位置信息,更不能实现移动对象的最近邻查询。本文在介绍移动对象数据库和数据模型的基础上,着重分析了交通路网模型和移动对象索引技术,首先考虑交通路网拓扑结构,采用路径为基本单位,离散的表示路网信息；然后借鉴两种常用索引结构FNR-Tree和MON-Tree的优点,提出一种能够索引移动对象全时态位置信息并支持最近邻查询的索引结构CRS (A Comprehensive indexing on road sectors)。 CRS为两层索引结构,上层主要对交通路网建立索引,下层主要针对路网上的移动对象建立索引。上层路网以路径为基本划分单位,建立路径2DR树,为提高查询效率,引入路径哈希表,通过路径哈希表可直接定位R树的叶子结点,而无需搜索整个上层R树才能找到相应路径；为了提高将来时刻位置预测精度和有效的支持最近邻查询,在上层索引结构中引入了交叉口转向表,记录路径上所有交叉点的信息。下层结构主要由移动对象2DR树、静态对象1DR树、移动对象哈希表和动态链表组成,上层R树的每个叶子结点都指向一棵移动对象R树和静态对象R树,移动对象R树记录了该条路径上所有的移动对象位置信息,静态对象R树记录了该条路径上所有的静态对象,且每个静态对象都指向一条最近邻链表(NNL),用于实现移动对象相对静态对象的最近邻查询。为了提高索引移动对象轨迹信息的效率,引入了动态链表和移动对象哈希表,通过访问哈希表和动态链表可直接得出移动对象的轨迹信息,而无需搜索整个下层移动对象R树森林。在移动对象轨迹查询方面,以访问结点的次数为性能指标,CRS索引结构和MON-Tree及FNR-Tree进行比较,结果表明,CRS索引结构有较高的查询效率。在移动对象轨迹预测和最近邻查询方面,CRS索引结构有较高的精确度。