移动对象索引ST-tree

叶小平， 陈瑞鑫， 周旋珍， 陈 鹏

(华南师范大学计算机学院，广州 510631)

随着计算机网络技术和无线定位通信设备迅速发展，移动对象数据管理已成为时空数据库的研究热点并形成移动对象数据库(MOD)的专门领域.在MOD中，移动点对象数据具有时空变化双重属性, 数据结构复杂, 具有海量存储数据规模,数据索引成为MOD基本技术手段之一.移动对象索引需要同时索引时空信息并管理不同的时态状况, 如索引历史轨迹、当前及未来位置数据.移动对象数据海量规模需基于外存存储，现有历史信息索引多是基于B树及其扩展系列以充分利用B树高效更新特征，如Jensen等[1]提出BX树采用空间划分和数据转换来索引移动对象位置并得到较好的更新性能；Chen等[2]提出ST2B-tree基于B+树，能够有效自动调优结构索引.由于移动对象数据应用十分广泛，Pfoser[3]将其分为3类应用场景：①非限制性移动；②限制性移动；③交通网络移动.现实中大多数移动对象往往被限制在路网(road network)当中，此时使用路网中线性参考位置表示移动对象相应位置可达到良好的降维效果.FNR树[4]是一种典型的路网移动对象索引，它使用一棵2DR树索引路网中线路，并对每条线路使用一棵1DR树索引其上移动对象轨迹.MON树[5]是FNR树的改进，索引的基本元素由同名道路构成的路径.叶小平等[6]提出一种基于空间相点分析的“先时间后空间”的协同索引MOindex，具有良好的查询效率.

本文研究基于区间关系(interval relation)的路网移动对象数据索引. 首先将区间转换为由其两端点确定的平面点，在区间点集合上讨论了“下右优先遍历”(down-right first traversing，DRFT)算法[7]，通过DRFT序列建立一般区间集合上数据结构；其次是将路网移动对象数据单元“时空矩形”(temporal-spatial rectangle，TSR)映射为时间期间(periods)和空间间隔(spatial segments)的二元组，由于时间期间和空间间隔都是一般区间的特例，可应用DRFT算法分别建立两者集合上的数据结构.以此为基础，从协同配置观点出发，建立一种新的移动对象数据索引模式ST-tree，该索引能够实现“一次一集合”的查询模式.另外，论文设计相应仿真，采用通用数据与现有基本工作进行比较评估，结果表明ST-tree的可行性和有效性.论文内容安排如下：第1节讨论一般区间集合结构，建立基于DRFT序列结构的索引模式ST-tree；第2节研究ST-tree的数据查询算法；第3节是相关实验仿真.

1 数据结构与索引模式

一个路网中线路r实例如图1所示.线路r上任意一点p的相对位置度量D(r,p)定义为始点p0到p的距离，当p=p0时，D(r,p)=0；当p≠p0时，D(r,p)=D(r,pi)+D(pi,p)，即首先计算p所在线段Si始点pi的位置度量，再加上p和pi之间的欧氏距离.

图1 路网线路r

1.1 移动对象数据结构

设区间集合Γ={(ai，bj)}，u=(ai，bj)看作平面上点，Γ看作平面点集H(Γ)，Γ和H(Γ)可建立1-1对应.不引起混淆时，不区分Γ和H(Γ).H(Γ)中具相同始点ai0的点组成1列，记为COL(ai0)，COL(ai0)右边相邻列称为COL(ai0)右相邻列，记为COLr(ai0).

算法1H(Γ)“下(右)优先”遍历算法

由H(Γ)“最左上方”点P开始，P(i,j)=u(0,0)，将P加入输出列表L1.

Step 1 由P开始沿该列一直向下遍历至属于H(Γ)的“最后”一个点K(i,m)(m

Step2.1 若存在，将N加入输出列表，P=N(i+1,m)，返回执行Step1.

Step 3 输出列表L1.

Step 4H(Γ)=H(Γ)L1，转向Step1.

1.2 路网移动对象索引ST-tree

定义1(移动对象索引模式ST-tree) 基于路网移动对象数据索引为四元组MO-tree=(R*-tree, HR; ST-tree, HM)，其基本结构见图2，(R*-tree, HR)为路网索引模块，(ST-tree, HM)为移动对象索引模块.

图2 MO-tree模式结构

(1)路网数据处理模块.通过R*-tree管理路网线路数据.R*-tree中每个叶结点对应一条线路，并建立移动对象索引ST-tree.

R*-tree叶结点表示为(mbr, plpt, mpt)，mbr为对应线路最小限定矩形，指针plpt指向实际线路的相应存储，指针mpt指向相应Mo-tree.R*-tree非叶结点元素表示为(mbr, childpt)，mbr表示其所有子结点mbr构成的最小限定矩形，childpt为子结点指针.

哈希表HR中元素表示为(pl, mpt)，pl为线路标识，指针mpt指向相应Mo-tree.HR用于查找和更新移动对象历史轨迹索引ST-tree.

(2)移动对象数据处理模块. ST-tree是Mo-tree的集合，Mo-tree由S-level、T-level和O-level等3个层面组成.

①S-level：对于所有空间间隔建立空间DRFT序列Ls，各个max(Ls)作为元素构成Mo-tree的根结点，所有Ls为对应max(Ls)子结点.

②T-level：对每个Ls结点对应的时间期间集合建立时间DRFT序列Lt，各个max(Lt)作为元素构成Ls结点的子结点.所有Lt为对应max(Lt)子结点.

以上2个层面的结点，即Mo-tree的非叶子结点元素表示为(VT/VS,childpt)，其中VT/VS表示时间期间/空间间隔，指针chlidpt指向子结点.

③O-level，Mo-tree的每个叶结点为Lt中每个时间期间对应的移动对象集合，每个移动对象(结点元素)可表示为(Oid, plid, ptr1, ptr2, vt, vs)，Oid是移动对象标识，plid为对象所在线路标识，指针ptr1/ptr2指向同一对象的前/后一线段，vt/vs是时间期间/空间间隔.哈希表HM中每个元素为{Oid, ptr}，Oid是移动对象标识，指针ptr指向对象最新线段所在ST-tree树叶结点元素.移动对象数据模块Mo-tree结构如图3所示.

图3 Mo-tree模式结构

2 数据查询

给定查询时空矩形Q=(d1,d2;t1,t2)，对于数据时空矩形D=(di1,di2;ti1,ti2)，如果Q∩D≠，则称D为关于Q的查询结果.

Q∩D≠等价于[d1,d2]∩[di1,di2]≠∧[t1,t2]∩[ti1,ti2]≠，因此，时空矩形相交转化为相应空间区间(interval)以及时间期间(period)相交.在算法2中，给定一个区间Q，考察Γ中所有和Q相交的集合.如果DRT序列L中所有元素都与Q相交(不相交)，则称L与Q相交(不相交)

算法2 DRT序列相交算法

Step 1 如果Q∩max(L)=，则L不与Q相交.

Step 2 如果Q∩min(L)≠，则L与Q相交.

Step 4 输出L处理结果，L=Li+1.

ST-tree支持时空范围查询和轨迹线查询.

时空范围查询也称为窗口查询.在路网环境中，给定查询窗口Q=(d1,d2;t1,t2)，其查询语义为“在时间期间T=(t1,t2)内，查找在空间间隔S=(d1,d2)内的所有移动对象.”在上述查询中，如果t1=t2，窗口查询就称为时间片查询.

算法3时空范围查询算法

设有时空范围查询Q=(d1,d2;t1,t2).

Step 1 通过路网索引模块中的2DR*树搜索与Q相交的线路MBR；对于得到的每条线路MBR通过plpt找到线路真实表示，获得相应的线路序列.对每一个线路r，执行Step2.

Step 2 通过Mo-tree中的S-level和T-level顺次按照算法2进行空间和时间过滤.

Step 3 通过Mo-tree中O-level输出查询结果.

移动对象轨迹线查询分为下述2种基本情形：

(1)Q=(O,t1,t2)，查询“在t1至t2时间内，移动对象O运动轨迹是怎样的？”

(2)Q=(Q,p,t1,t2)，查询“移动对象O离开某地p后在(t1,t2)内运动轨迹是怎样的？”

在情形(1)中，查询分为2个步骤完成：第1步，在哈希表HM中直接找到对象o并利用表中的指针定位移动对象的历史轨迹；第2步，在指针指向的ST-tree叶节点元素的ptr1指针和VT信息，通过比较查询时间(t1,t2)得到最终轨迹.

3 仿真与评估

为测试ST-tree的性能，比较对象为MON-tree[5]和PPFN*-tree[8]，实验使用Intel Pentium 4，2.8 Ghz，512 MB主存，软件环境为Microsoft Windows XP SP3， C++， Visual Studio 2008.实验数据由基于路网的移动对象产生器[9]得到，路网数据采用Geo Community提供的德国部分交通网络数据[10].对于上述路网数据，通过基于路网的移动对象产生器以5万的跨度分别生成5、10、15、20、25万个移动对象轨迹数据.

窗口查询是给定一个时间间隔和一个矩形区域，查找在这个窗口范围内的移动对象.

如图4所示，随移动对象数量增长，ST-tree窗口查询性能优于MON-tree和PPFN*-tree，同时ST-tree还呈现线性增长态势.

如上文提到的，时间片查询是窗口查询的一种特例，它在索引的查询类型中占据重要的地位，由图5可知，随着移动对象数量的增加，ST-tree、MON-tree和PPFN*-tree查询所消耗的时间都呈近似线性增长.且ST-tree优于MON-tree和PPFN*-tree.

图4 移动对象数量增加时查询性能比较

图5 时间片查询

由于MON-tree未实现轨迹查询，轨迹查询仿真时只考虑ST-tree与PPFN*-tree比较，PPFN*-tree采用TB*-tree索引历史轨迹，在轨迹查询方面效率较好.实验中给定对象标识和查询时间间隔，查出该对象的轨迹信息.移动对象数为25万，对于每个查询时间间隔，随机产生500个查询对象，最后求其时间开销平均值，如图6所示，对于较小查询时间间隔，ST-tree优于PPFN*-tree，而随间隔变大，ST-tree渐渐弱于PPFN*-tree.

图6 轨迹线查询

4 结语

本文研究基于DRFT序列的区间结构关系及其路网场景下移动对象数据索引技术.主要研究了一般区间集合的基本结构以及相应性质和构建算法，为构建索引提供相应数学基础；同时将时空矩形集合映射为空间间隔集合和时间期间集合，通过这2个时空元素集合构建路网场景中移动对象数据结构；在此基础上，提出了一种关于历史信息的路网移动对象索引技术ST-tree，通过与现有基本工作仿真比较表明了ST-tree的可行性与有效性.动态管理是索引的一项基本功能，相关工作将另文讨论.

参考文献：

[1] Jensen C S, Lin D, Ooi B C. Query and update efficient B+-tree based indexing of moving objects[C]∥Proceedings of the thirtieth international conference on very large data bases (VLDB). Toronto, Canada, 2004:768-779.

[2] Chen S, Ooi B C, Tan K L, et al. ST2B-tree: A self-tunable spatio-temporal B+-tree index for moving objects[C]∥Proceedings of the 2008 ACM SIGMOD international conference on management of data. Vancouver, Canada, 2008:29-42.

[3] Pfoser D. Indexing the trajectories of moving objects[C]∥Bulletin of the IEEE computer society technical committee on data engineering. Washingtom:IEEE Computer Society, 2002:2.

[4] Frentzos E. Indexing objects moving on fixed networks[C]∥Proceedings of the 8th international symposium on advances in spatial and temporal databases. Berlin:Springer-Verlag, 2003: 289-305.

[5] Victor T D A, Ralf H G. Indexing the trajectories of moving objects in networks[J]. GeoInformatica, 2005, 9(1): 33-60.

[6] 叶小平,郭欢,汤庸，等.基于相点分析的移动数据索引技术[J].计算机学报，2011,34(2):256-274.

Ye X P, Guo H, Tang Y,et al. Index of mobile data based on phase points analysis[J].Chinese Journal of Computer, 2011, 34(2):256-274.

[7] 叶小平，周畅，廖青云，等.DTindex：分布式时态索引技术[J].华南师范大学学报:自然科学版,2013,45(3):40-44.

Ye X P, Zhou C, Liao Q Y, et al. DTindex: Distributed temporal data index[J].Journal of South China Normal University:Natural Science Edition, 2013,45(3):40-44.

[8] Fang Y, Cao J, Peng Y, et al. Efficient indexing of the past, present and future positions of moving objects on road network[C]∥Proceedings of the WAIM 2013 international workshops. Beidaihe, China, 2013, 7901: 223-235.

[9] Brinkoff. A framework for generating network-based moving objects[C]∥Proceedings of the 12th international conference on scientific and statistical database management (SSDBM). Berlin, Germany,2000:253-255.

[10] Geo Community. Transportation-Germany[CP/OL].(2012-08)[2013-02-12].http:∥data.geocomm.com/catalog/GM/group103.html.