计算机科学2 0 0 2 V 0 1 2 9 N Q - 8 基于G R I D 文件的移动对象索引方法 G r i dF i l eB a s e dI n d e x i n gM e t h o df o rM o v i n gO b j e c t s 吴岑1 白芸1 丁治明2 孟小峰1 ( 中国人民大学数据与知识工程研究所北京1 0 0 8 7 2 ) 1 ( 中国科学院计算技术研究所北京1 0 0 0 8 0 ) 2 A b s t r a c t I n d e x i n go fm o v i n go b j e c t si sak e yt e c h n o l o g yi ni m p r o v i n gt h ep e r f o r m a n c eo fm o v i n g o b j e c t sd a t a b a s e s I nt h i sp a p e r ，w ep u tf o r w a r dan e wm o v i n go b j e c ti n d e x i n gm e t h o d G r i dF i l e B a s e dI n d e x i n gm e t h o df o rM o v i n g O b j e c t s T h es t r u c t u r eo ft h ep r o p o s e di n d e x i n gm e t h o di sd e s c r i b e di nd e t a i l ，a n dt h er e l a t e da l g o r i t h m sa r ep r e s e n t e d I no r d e rt Oe v a l u a t et h ep e r f o r m a n c eo f t h ep r o p o s e dm e t h o d o l o g y ，w ed e v e l o p eap r o t o t y p es y s t e m T h ee x p e r i m e n tr e s u l t ss h o wt h a t t h ep r o p o s e da l g o r i t h m sh a v ee f f i c i e n t l yi m p r o v e dt h ep e r f o r m a n c eo ft h es y s t e m K e y w o r d sM o v i n go b j e c t sd a t a b a s e s ，S p a t i a l - t e m p o r a li n d e x i n g ，Q u e r yp r o c e s s i n g 1 引言 近年来，随着无线通讯技术及全球定位技术的 发展，移动对象数据库( M o v i n gO b j e c t sD a t a b a s e ， 简称M O D ) 技术已经成为了一个研究热点 1 ，并在 诸多应用领域中展现了广阔的应用前景，如智能交 通控制系统、军事指挥系统等。在所有这些应用中， 数据量的庞大远远超出了人们的想象。 为了追求更快的查询及处理速度，就必须研究 出有效的存取方法。移动对象索引技术对于减少搜 索空间，加快查询响应速度有着至关重要的作用。目 前，移动对象索引技术已经成为了一个非常重要的 研究领域，并引起了人们持久的关注。 在移动对象索引技术方面，人们已经进行了较 为大量的研究，并提出了许多模型与算法，如移动对 象的H A S H 方法 2 、基于Q U A D 树的移动对象索 引方法 3 、以及基于R 树的移动对象索引方法“3 等。 然而，这些方法均没有讨论位置更新对索引性能的 影响。为了克服上述缺陷，本文提出了一种基于 G R I D 文件的移动对象索引算法，重点分析了其中 的位置更新处理策略，并给出了相应的移动对象查 询处理方法。 2 基本概念 移动对象的动态属性【1 可以用时空轨迹进行表 示。时空轨迹是地理空间加上时间轴所形成的多维 空间中的一条曲线。为了方便说明，我们假设移动对 象在X Y 平面上移动，这样时空轨迹可以看成是 x Y T 三维空间中的一条曲线。同时，为了处理 上的方便，我们一律以直线线段来逼近实际的复杂 轨迹曲线。 定义1 ( 时空轨迹) 设M 为系统中的任意一个 移动对象( 其标识为M I D ) ，则其时空轨迹手( 肘，D ) 可以定义为如下的一个有限序列： ( M j D ) 一( ( z i ，Y ，岛) ) 7 - 1 其中，( z i ，Y ，岛) ( 1 i 行) 称为 ( M j D ) 的第i 个关 键点，记为手( M ，D ) c o ( i ) ；而线段E ( x ，M ，) ，( 五十。， y f + 1 ，t J + 1 ) 则称为f ( 加D ) 的第i 个时空片段，记为 f ( M D ) S e g ( i ) 。 定义2设M 为系统中的任意一个移动对象 ( 其标识为M I D ) ，且f ( M J D ) 和 ( M J D ) l D ( i ) 分 别为其时空轨迹及轨迹的第i 个关键点，定义： ；( D ) J D ( i ) P 为筝( M ，D ) p ( i ) 的9 分量，其 中P z ，Y ，t ； 手( M 佃) C u r S e g 为当前时空片段号，即移动对 象M 当前所处的时空轨迹编号； f ( M I D ) S u m S e g 为f ( M J D ) 中包含的时空片 段总数。 T Y 图1 位置更新的处理 一X 2 0 3 在移动对象数据库系统中，时空轨迹不仅可以 表示移动对象过去和当前位置，而且还可以表示其 将来位置。当移动对象刚刚进入系统时，需要预先将 其运行计划提交给系统。在其进行的过程中，当实际 位置与预测位置的偏差超过一定的阚值时，就需要 触发位置更新对索引中的轨迹进行更新，以反映最 新的实际情况，如图1 所示。 5 基于G R I D 文件的移动对象索引 从本质上讲，移动对象的索引即为X Y T 三维空间中的空间索引，因此可以直接利用传统的 空间对象索引方法 5 。目前有三种主流的空间索引 算法：R 树及其变形树、Q U A D 树及其变形树、以及 G R I D 文件及其变形算法。从本质上讲，由于R 树和 Q U A D 树均为多层嵌套结构，因此它们在进行位置 更新时都会涉及到树结构的嵌套调整，不太适合于 频繁位置更新的情况。在进行位置更新时，需要删除 旧的轨迹，插入新的轨迹。但插入和删除操作都会触 发R 树和Q U A D 树的多级分裂合并以及调整，从 而极大地影响了它们的位置更新性能。而G R I D 文 件的情况则不同。G R I D 文件的索引结构属于扁平 结构，而且在进行G R I D 块的分裂和合并时分裂位 置是灵活的，因此比较适合于频繁位置更新的情况。 鉴于上述考虑，我们选择G R I D 文件作为移动 对象索引的数据结构，并对基本的G R I D 文件算 法 5 进行了改造，提出一种新的，基于G R I D 文件的 移动对象索引方法。 我们设要索引的空间为X Y T ，其中X Y 为应用地理空间，而T 为T 轴的一段。由于时间 是无限增长的，我们在建立索引时只是表示当前时 刻前后的一段，随着时间的推移进行周期性的转贮。 在G M O I 中，我们可以对X Y T 。空间进行 一个G R I D 划分：P P x P ，P 。，其中：P 。= ( x o ，x 1 ， ，X I ) ，P y = ( y o ，y 1 ，y m ) ，P t = ( t o ，t 1 ，t n ) ，且X i ( o i 1 ) 、y ，( o j m ) 、t k ( o k n ) 分别为X 、Y 、T 维上的区段。这样，整个三维空间就被划分成了若干 个G R I D 块。这些G R I D 块又进一步被映射到外存 G R I D 桶中( G R I D 桶是I o 的基本单位) 。记录的 插入和删除可能会引起G R I D 划分的动态变化，并 导致划分区域的分裂和合并。X Y T 空间的动 态划分以及G R I D 块与G R I D 桶之间的动态对应关 系通过G R I D 目录进行管理。在G R I D 目录中只存 放指向外存桶的指针，真正的索引记录是放在 G R I D 桶中的，如图2 所示。 在G M O I 中，移动对象的轨迹信息是以轨迹片 段为单位存放的。考虑轨迹片段S E G = ( 嚣，Y i ，t i ) 一 ( z m ，Y m ，t m ) 的情况，所有与S E G 相交的G R I D 块对应的G R I D 桶中均存放有S E G 的完整信息，包 2 0 4 括对应的M I D ，以及S E G 的两个端点坐标。由于 S E G 对应与三维空间中的直线线段，因此可以十分 容易地根据G R I D 目录计算出与之相交的各个 G R I D 块。 图2 三维时空数据空间的G R I D 划分 5 1G M O I 的索引生成算法 G R I D 文件是逐步生成的。在初始状态下，整个 X Y x T 空间中没有数据记录；当新的移动对象 进入系统并提交其运行计划时，相应的轨迹信息需 要插入G R I D 文件中。当插入的数据足够多时，就会 引起G R I D 文件的分裂。由此G R I D 文件是一个动 态增长的数据结构。 当插入某个移动对象M 的离散时空轨迹f ( M ，D ) 时，系统将逐个处理其各个轨迹片段。设要 处理的轨迹片段为 ( M ，D ) S e g ( i ) ，首先需要查找 到f ( M m ) S e g ( i ) 的插入位置，即插入f ( M I D ) S e g ( i ) 的G R I D 桶( 可能会有多个) ，其查找过程与 G R I D 文件的查询处理相似；然后将善( M I D ) S e g ( i ) 的信息( 包括M I D 及 ( M J D ) S e g ( i ) 的端点坐 标) 插入相应的G R I D 桶中；在插入的过程中需要判 断是否需要进行G R I D 的分裂：设G R I D 桶的容量 为C ，如果R 要插入的G R I D 桶中记录个数小于C ， 则可直接将f ( D ) S e g ( i ) 的信息插入桶中，反之 就需要进行G R I D 划分的分裂。在G R I D 文件中，分 裂位置可以是随意的，因此可以通过选择合适的分 裂维和分裂位置将分裂过程中的工作量控制在很小 的范围，具体处理可见文 5 3 。 算法1 给出了G M O I 索引生成算法。 算法1 ：F T M O D 索引生成算法 i n p u t ：r ( M r D ) ； 处理第i 个轨迹片段 f o r ( f = 1 ；i = i C M I D ) S u m S e g ；i + + ) G r i d 。为所有与第i 轨迹片段相交的G r i d 块 G r i d 。= G r i d I G r i d N f ( 枷) S e g ( i ) ； F o rVG r i d G r i d 逐个处理G r i d 。中的所有G r i d 块 I F ( I G r i d I c ) 将f ( D ) S e g ( i ) 的信息插入G r i d 中； E L S E 分裂G r i d ； 将芋( M m ) S e g ( i ) 的信息