论文部分内容阅读
随着WIFI、3G、GPS等无线通信技术的快速发展,各种具有定位功能的车载设备、无线移动终端的普及,使得越来越多的基于移动对象位置的服务被人们广泛使用。移动对象的位置时刻在随时间变化,存储移动对象位置信息的数据库需要处理移动对象时间和空间频繁变化的时空数据。在移动对象数据库中,移动对象索引技术是支撑移动对象数据库进行数据管理的基础,是移动对象数据库管理的核心。本文通过对现有的移动对象数据库技术与索引技术的研究,在深入分析了交通路网结构的基础上,提出一种基于交通路网的有效移动对象轨迹索引结构ETI(Efficient moving objects Trajectories Indexing)。ETI移动对象组合索引主要由上下两层结构组成,上层为路网索引结构由存储道路信息的道路哈希表和2DR_Tree (?)组成,实现对路网空间的索引。其中2DR-Tree存储每条路段的空间范围信息;道路哈希表存储每条道路的标识及其所有组成路段信息,同一路段的路段指针和2DR-Tree叶结点指针指向同一个下层的1DR-Tree。由于路网的结构相对固定,道路更新周期长,频繁改动的几率较小,所以可以将道路哈希表和2DR-Tree视为静态结构来存储。下层的索引结构由移动对象哈希表、动态链表和1DR-Tree共同构成。其中,1DR-Tree存储与之对应路段的移动对象时间信息和轨迹信息;移动对象哈希中存储移动对象的标识和实时信息,并通过链表指针与单向链表相连:单向链表按照更新时间顺序存储移动对象的运动轨迹信息。在分析了交通路网中移动对象的运动规律基础上,结合交通道路的流量大小、繁忙程度的不同,在道路哈希结构和移动对象哈希结构中引入基于缓存的LRU内存置换算法,提高道路和移动对象在内存中的命中率,减少外存访问次数,从而提高了索引结构的更新效率,使得ETI索引结构相比传统的FNR-Tree移动对象索引算法具有更高的索引性能。最后本文还用T. Brinkhoff基于路网的移动对象数据产生器和真实的Oldenburg交通路网数据,模拟产生了移动对象实验测试数据。通过对ETI移动对象组合索引和FNR-Tree索引结构在索引操作中的结点存取次数为性能参考,进行性能比较。结果显示,本文提出的ETI移动对象组合索引结构在移动对象轨迹更新、道路查询、历史轨迹查询等方面性能均有所提高。