1815一种基于城市交通网络及移动对象全时态索引.docVIP

一种基于城市交通网络的移动对象全时态索引 Indexing the Past, Present and Future Positions of Moving Objects in Urban Traffic Networks 陈继东 孟小峰 胡志智 李本钊 肖珍 （中国人民大学信息学院 北京 100872） （{chenjd,huzhizhi,libz,xiaozh,xfmeng}@ruc.edu.cn） Abstract: Advance in wireless Internet and position technologies such as GPS enable new data management applications that monitor continuous streaming data. In these applications, efficient management of such streams is a challenging goal due to the highly dynamic nature of the data and the need for fast, on-line computations. In this paper, we present a novel index technique for querying the past, present or future positions of moving objects in urban traffic networks. In particular, we first invoke a simulation based predict model for the vehicles future trajectory which is more precise than the traditional predict model in TPR-tree. Moreover, exploiting the feature of traffic network, we present a dynamic structure termed AU (Adaptive Unit) and develop it to an R-tree based index named current-AU. Finally, by naturally extending the AU we propose past-AU, which is capable of indexing historical trajectory and at the same time avoid the dead space which is inevitable in TB-tree. Empirical studies indicate that the AU-tree outperforms the traditional TPR-tree and TB-tree in several aspects. Key Words: Moving Object database, Moving Object indexing, Location Model 1. 介绍 随着3G时代的到来，众多具有定位功能的无线手持设备的大量普及，促使一类基于位置的服务，称为位置相关服务（Location Based Service）成为可能。位置相关服务包括交通管理，军事指挥，基于位置的信息服务等众多领域[1]。提供位置相关服务需要用到移动对象位置的实时数据，这些数据一般可以通过GPS（Global Positioning System）或基站定位获得。由于这些数据自身的动态特性（连续的变化）和查询的实时要求，因此如何高效的管理移动对象的位置数据成为一个具有挑战性的目标。 而移动对象数据库MOD（Moving Object Database）就是对移动对象的位置及其相关信息进行管理的数据库。它也是位置相关服务最重要的技术基础。MOD是数据库研究近年来发展起来的一个分支。移动对象数据库遇到的核心科学问题有以下几点： 移动对象位置获取。即怎样在有限的无线带宽限制下获得大量的并随时间频繁更新的移动对象位置信息。 移动对象位置建模。即当服务器收到移动对象位置信息后，用什么样的模型来表示这些原始的位置数据，以方便下一步更有效的应用这些数据。 移动对象索引。即如何设计一种新的索引技术来索引频繁更新的移动对象位置信息，并且能够进一步适应其对历史轨迹信息的查询。 在实际移动对象索引中，通常第二和第三个问题是紧密联系在一起的，移动对象索