基于时空标签轨迹的范围模式匹配查询

梁珺秀,许建秋

(南京航空航天大学计算机科学与技术学院,江苏 南京 210016)

0 引 言

随着无线通信技术和智能终端的迅速发展，每天产生大量移动对象数据，并同时与空间环境和运动模式等相关联。移动对象查询不再仅限于时空属性，更扩展至与时空属性相关的语义属性上。有效地组织管理移动对象，分析移动对象的运动，可用于大量位置服务应用(Location Based Service，LBS)[1]。

现有的语义相关查询或是仅要求覆盖给定查询语义[2]，或是语义属性满足简单顺序即可[3]，或是不考虑轨迹间的距离进行计算，这种对轨迹的分析模式很大程度地忽略了轨迹中的有效信息。因此需要提出一种同时包含复杂语义属性和时空属性的查询，来解决日益复杂的用户查询要求。

在某些情况下，用户可能只对某一特定区域轨迹的语义感兴趣，如分析用户在超市中包含语义的时空轨迹，返回在早上8:00至10:00时间区间内经过水果区或蔬菜区及日用品区的轨迹。通常在该时间段内经过这些地方购买的多为家庭主妇，因此可为返回轨迹结果对应的移动对象推送商品优惠、限时蔬菜打折之类的消息。考虑在特定范围内的模式匹配查询可以更有针对性地制定合适的方案。本文主要工作如下：

1)结合传统移动对象查询及模式匹配查询，提出范围模式匹配查询。

2)给出基于标签R树的范围模式匹配查询算法。

3)通过合成数据及真实数据，与已有索引对比，验证查询算法的有效性。

1 相关工作

常见移动对象查询包括范围查询[4]、K近邻查询[5]及相似轨迹查询[6]等。范围查询返回在给定时空范围内的所有移动对象，K近邻查询返回距离给定查询对象最近的前K条轨迹，相似轨迹查询给定相似性度量的距离函数判断轨迹间的相似性。而轨迹中语义属性的出现，使得用户查询在传统查询基础上添加语义查询请求。

文献[7]提出活动轨迹由一组同时包含位置和用户活动的点所组成，描述用户的活动信息；文献[8]提出语义轨迹，在时空轨迹的基础上描述移动对象在时刻点处的语义；文献[9]提出轨迹表示为随时间变化标签的符号轨迹，标签为字符串形式，不包含经纬度信息。

Chen等[10]提出了基于活动轨迹的面向出行的活动轨迹搜索(Trip Oriented Search on Activity Trajectory，TOSAT)，给定起点和终点，返回在给定距离阈值内，完全覆盖给定活动且有最高轨迹匹配距离的前K条轨迹；Zheng等[11]提出语义轨迹的模糊关键字查询，用户给出查询关键字，综合考虑语义轨迹与查询关键字的编辑距离和经过给定关键字的轨迹长度，返回代价最小的前K条轨迹；Damiani等[12]提出了从符号的维度提取满足给定模式的符号轨迹子轨迹，由子轨迹的时间范围来限制空间维度在符号属性和空间轨迹上的混合查询。

2 问题描述

2.1 相关定义

定义1时空标签轨迹：可表示为traj=<[I1,l1, loc11, loc21],…, [In,ln, loc1n, loc2n]>，其中任意[Ij,lj, loc1j, loc2j]表示第j个时空标签轨迹单元，其中Ij表示第j个单元对应的时间区间，lj表示单元j对应的标签，loc1j表示开始时刻的地理位置，loc2j表示结束时刻的地理位置。

定义2模式：P=〈p1, …, pn〉，其中pi为以下2种形式之一：

1)pi为标签，表示不同的语义标签，称为单元模式。

2)pi为*、+、[p]、[pi|pj]、[p]+、[p]*或[p]?，称为简单模式，简单模式中的p为单元模式或简单模式，简单模式中*表示存在0或0个以上的简单模式，+表示存在至少一个简单模式，|表示2个简单模式中仅存在其中一个，?表示前面修饰的简单模式最多只出现一次。

定义3模式匹配(Pattern Match，Pmatch(traj,P))：对于给定模式P，当且仅当时空标签轨迹traj中存在轨迹段的标签信息，与P中标签的内容相同且顺序一致时，即traj轨迹段中的标签顺序匹配P所表示的正则表达式，则称轨迹与P模式匹配。

定义4轨迹插值(Interpolate(R,I,traj))：给定区域R，时间区间I，Interpolate(R,I,traj)返回轨迹traj在时间区间I及范围R内的子轨迹段。

定义5范围模式匹配查询(Range Pattern Match Query,RPMQ)：给定空间区域R，时间区间I以及模式P=，返回轨迹集合D′∈D：

1)∀ traj∈ D′，Interpolate(R,I,traj)≠Ø且

如图1所示，给定查询模式P=，该查询模式表示查询从p1出发，中间经过一个或一个以上的地点，然后返回p1并经过p2的轨迹。图1中虚线框表示时空范围的限制，因此对于4条轨迹，先得到满足时空限制条件的子轨迹段traj′，在图1中用实线表示traj′，虚线表示查询时空范围外的部分。对于traj1，轨迹语义p1段部分在框内，因此满足P中的由p1出发的请求，后经过，满足查询模式的中间部分，因此traj1可以作为查询结果返回；对于traj2，虽然满足P，但轨迹最后一段完全不在虚线框内，因此子轨迹中只包含部分，不匹配模式P，而traj3和traj4不匹配给定模式，因此最后将traj1作为范围模式匹配查询结果返回。

图1 范围模式匹配查询

2.2 标签R树

标签R树索引(Label R-Tree，LR-Tree)，形式上由一个3DR-Tree[13]和一个标签表组成，标签表中不重复地保存时空标签轨迹数据集中出现的所有标签，而空间位图层与3DR-Tree不同的是：

1)每个节点的项(entry)中增加一个预设定长度的位图，树中所有节点项中位图长度相同，位图由一串”0/1”组成，“0/1”代表了当前项指向的子节点的标签存在性，当位为1时，表示位对应到标签表中的标签存在，为0则不存在。

2)位图的每位通过哈希函数对应到标签表中的一个或多个位置，其中标签表的每行保存不同标签。

叶节点项位图中的每一位表示所指向移动对象标签的存在性，非叶节点项中的位图通过所有子节点的位图执行按位或操作得出。

LR-Tree内部节点项表示为(rid,MBR,bitset)，其中rid指向当前节点的下层子节点，MBR是将rid指向的子节点中所有项的MBR包围的最小矩形框，bitset由rid所指向的子节点中所有子节点项位图执行按位或操作得到。叶节点项存储形式为(tid,MBR,bitset)，其中tid指向存储在磁盘空间上的时空标签轨迹，MBR为将该轨迹包围的最小边框矩形，bitset为所指向的时空标签轨迹包含的所有标签到标签表的映射计算所得的位图。

定义6位图匹配(Bitmap Match,BMatch(P,E))：对于给定模式P的位图Tbit和LR-Tree项中位图Ebit，∀bit∈Tbit，当Tbit(bit)=1时，若Ebit中对应的位Ebit(bit)=1，则表示当前位图Ebit与查询模式P位图匹配，反之若存在一个或一个以上位不为1，则不匹配，其中模式P的位图Tbit由模式P中所有出现的标签与LR-Tree中标签表对应所得。

3 范围模式匹配查询

范围模式匹配查询返回在给定的时间空间范围内，子轨迹段匹配给定模式的所有轨迹。利用LR-Tree处理范围模式匹配查询，分为筛选和精细计算2步，首先遍历LR-Tree，找到树中与给定查询模式P位图匹配且与查询时空范围对应矩形框相交的所有叶节点项，然后对得到的叶节点项所指向的时空标签轨迹进行精细计算，判断时空范围内的子轨迹段是否匹配给定模式，将模式匹配的所有轨迹作为查询结果返回。基于LR-Tree的范围模式匹配查询如算法1及算法2(见3.2节)所示。算法1主要步骤如下：

算法1 筛选过程

输入：查询模式P；查询时间区间I；查询空间范围R；时空标签轨迹集合D；LR-Tree

输出：中间结果集合Q

1：Q←Ø;S←Ø;

2:S.push(LR-Tree.RootNode);

3:WHILE(S不为空)

4:Node←S.top(); S.pop();

5:FOR EACH entry∈Node

6:EMBR←entry.MBR();

7:IF(BMatch(P.Tbit, E.Ebit))

8:IF(EMBR空间投影与R相交)

9:IF(QBMR.timeInterval与EMBR.timeInterval相交)

10:IF(entry为叶节点项)

11:Q.push(entry);

12:ELSE

13:S.push(entry.node);

14:END IF

15:END IF

16:END IF

17:END IF

18:END FOR

19:END WHILE

20:RETURN Q

采用深度优先方法遍历LR-Tree，设置栈S、保存LR-Tree筛选结果的队列Q及最终查询结果的队列Res，首先将LR-Tree根节点入栈：

1)对于每个出栈节点，依次判断节点中项是否与给定模式P位图匹配，对于匹配的位图，进一步判断节点项对应的最小边框矩形MBR是否与给定查询范围R的边框矩形相交，对于不相交的矩形框，将以该节点项指向的节点为根节点的子树从树中裁剪，对满足前2个条件的项判断是否与给定查询时间区间相交，将满足3个条件的节点项进行下一步。

2)对于满足前2个条件的节点项，若当前节点为非叶节点，则将节点项所指向的子节点入栈S；若当前节点为叶节点，则将叶节点项保存入队列Q中。

3)在遍历LR-Tree后，对于Q中所有叶节点项，将其所指向的时空标签轨迹取出，判断轨迹是否存在与给定时空范围相交的子轨迹段，对于非空子轨迹段再进一步判断是否匹配给定查询模式，将子轨迹段匹配模式的轨迹加入返回结果集合Res中。

最终集合Res中保存的所有轨迹，即为范围模式匹配查询的查询结果。

3.1 范围模式匹配查询筛选

算法1所示为范围模式匹配查询中的筛选过程算法，筛选过程由3个部分组成：1)节点项是否与给定模式P位图匹配；2)项中MBR在空间上的投影是否与给定查询范围R的矩形框相交；3)项中MBR在时间区间上的投影是否与给定查询时间区间I相交。

对于第1个部分，项中位图由项所指向的子节点中所有节点项位图按位或操作所得，若当前节点项位图某位为0，则表示以其子节点为根节点的所有节点项中位图对应的位均为0；若节点项与查询模式位图Tbit不与位图匹配，即在Tbit为1的所有位上，节点项位图中存在一个或一个以上的位不为1，则当前节点的所有子孙节点均不可能存在对应位为1的项。因此不匹配的节点项所指向的时空标签轨迹不包含查询模式中的所有标签，不可能完全匹配给定查询模式，则可以将这部分节点剪枝而不需要进一步的计算。

对于第2个和第3个部分，根据范围模式匹配查询定义，返回在给定时空范围内匹配模式的轨迹，因此返回结果中的轨迹必然与给定查询时空范围相交。对于空间范围R，LR-Tree中非叶节点项的MBR是将所有子节点项包围的最小边框矩形，因此若MBR与给定R不存在相交部分，则该子节点与R也不可能存在相交部分，因此可以作为筛选条件；而对于时间范围I，根据定义，若节点项的定义时间区间与I不存在交集，也必然不会出现在返回结果中。

根据上述3个部分筛选条件，可以在访问LR-Tree的节点时，筛选出所有不可能作为结果返回的轨迹，大量减少进一步的计算，从而降低磁盘I/O和CPU计算时间。

3.2 范围模式匹配查询精细计算

对于经过筛选过程后保留在队列Q中的所有项，需要进行进一步的精细计算来判断项所指向的时空标签轨迹是否满足给定查询条件。算法2为范围模式匹配查询精细计算过程，精细计算过程主要分2步：1)判断当前项所指向的轨迹与给定时空查询范围的交集是否为空；2)判断查询范围内的子轨迹段与给定模式是否匹配。对于满足上述2个条件的轨迹则作为结果加入Res中，最终保存在Res中的所有轨迹即为范围模式匹配查询结果。

范围模式匹配查询返回与给定时空范围相交的轨迹，因此对于Q中叶节点项指向的每条轨迹，首先考虑与查询时空范围是否相交。在筛选过程后得到的所有轨迹与查询时间区间必然存在交集，而对于空间属性来说，筛去的是轨迹的MBR在空间上的投影与查询范围不相交的轨迹，轨迹本身与查询范围是否相交需要进行进一步的计算。

算法2 精细计算

输入：查询模式P；查询时间区间I；查询空间范围R；中间结构集合Q

输出：查询结果Res

1：Res←Ø;

2:FOR EACH entry∈Q;

3:sub Traj←Interpolate(entry.traj,I,R);

4:IF(sub traj不为空∧Pmatch(subTraj,P))

5:Res.push(entry.tid);

6:END IF

7:END FOR

8:RETURN Res;

在图2所示的轨迹投影中，traj为时空标签轨迹，用来判断traj是否经过查询空间范围R，将轨迹投影至XY平面，得到轨迹在二维空间上的投影，实线部分为范围R内的子轨迹段subtraj，即为traj与查询空间R的交集。对于subtraj，再与查询时间区间计算，得到查询时间区间内的子轨迹段subtraj′，即为给定时空范围内的子轨迹段。根据范围模式匹配定义，在得到子轨迹段subtraj′后，只需要考虑子轨迹段的模式匹配，判断subtraj′是否与给定查询模式P模式匹配，将匹配的子轨迹对应的时空标签轨迹加入到返回结果集合Res中，最终Res中得到的所有轨迹即为范围模式匹配查询的结果。

图2 轨迹投影

4 实验性能与测试

表1 数据集的数据统计

实验使用真实数据集和合成数据集，如表1所示。真实数据集是微软亚洲研究院GeoLife[14]的项目组收集182个用户3年内的GPS数据，其中部分用户用交通方式标记了他们的运动数据(如步行、火车等)，合成数据集是SECONDO系统中人工合成地铁轨迹数据的Trains。

表2记录了GeoLife中出现的所有标签及不同标签出现的次数。

表2 标签频数

4.1 对比索引介绍

RR-Tree采用文献[15]中的思想，将HAG索引的网格结构替换为R树索引结构，实现在R树节点项中插入最大最小值的结构，并命名为RR-Tree。RR-Tree节点结构如图3所示，N为RR-Tree的节点，N中包含若干节点项E，E中包含MBR和pointer/tid，与R-Tree定义相同，其中Min(Max)表示以该节点项为根节点的子树中包含的最小(大)语义数值。在查询过程中，首先判断查询模式P中所有的语义标签是否都出现在[Min,Max]范围内，对于满足条件的节点项进一步根据节点项中的MBR与给定查询时空条件计算来进行剪枝，3DR-Tree[13]在时空上的计算与RR-Tree相同。

图3 RR-Tree节点结构

TB-Tree[4]以轨迹段MBR作为叶节点项的MBR构造TB-Tree，每个叶节点中只包含同一轨迹中的轨迹段，并有指针指向下一个包含同一轨迹的叶节点。对于TB-Tree节点项中MBR，若节点项与查询时间区间不相交或节点项的MBR计算后与空间查询条件不满足，则将节点裁剪。当遍历至叶节点处读取完整轨迹，判断是否模式匹配并进行进一步的轨迹时空距离计算。

对于SETI[16]网格索引，将给定空间等分为大小相同的网格，在每个网格中建一维R树索引轨迹段的时间属性。在查询过程中，首先判断每个网格与查询空间范围关系是否满足空间属性要求，满足则根据网格中的一维R-Tree判断是否存在与查询时间区间相交的项。将满足时空属性的项对应轨迹进行进一步的精细计算，判断是否满足查询条件。

4.2 范围模式匹配查询性能测试

为了验证本文提出的基于LR-Tree范围模式匹配查询算法的有效性，采用C++语言在Linux环境下扩展可扩充移动对象数据库SECONDO，对LR-Tree、RR-Tree、3DR-Tree、SETI及TB-Tree索引结构进行实现，实验环境为：Intel(R) Core(TM) I3-2120 CPU@3.30 GHz，4 GB内存，Ubuntu14.04 64 bit操作系统，本部分实验参数设置如表3所示。

表3 范围模式匹配查询实验参数

4.2.1 数据集对算法性能影响

本节实验以不同数据集为实验数据，比较5种索引在相同的查询条件下，在不同数量级的数据集上的性能，得到的结果如图4所示。可以看出随着数据量增长，5种索引的I/O次数及CPU时间均呈增长趋势，由低到高依次为LR-Tree、RR-Tree、3DR-Tree、TB-Tree及SETI，相较于另外4种索引，LR-Tree增长更为缓慢，体现了LR-Tree高效的剪枝性能。

(a) CPU时间比较

(b) I/O次数比较图4 数据集对算法性能影响

4.2.2 查询模式对算法性能影响

本部分实验以GeoLife真实数据作为实验数据，对GeoLife中出现的8种标签，在相同的查询条件下设置仅含一个标签的不同查询模式，实验得到的结果如图5所示。对比表3中标签出现次数，可以看出相较于另外4种索引，对于出现频率较低的标签，如airplane和train，由于在LR-Tree节点项位图中对应位为1的节点少，因此能更好地利用节点中的位图有效地使用关键字剪枝，从而减少I/O代价和CPU时间，提高查询效率。

(a) CPU时间比较

(b) I/O次数比较图5 查询模式对算法性能影响

4.2.3 查询标签数量对算法性能影响

本节实验采用合成数据Train，对比查询模式中包含不同的标签数量对查询效率的影响，得到实验结果如图6所示。随着查询模式中标签数量增加，I/O代价及CPU时间逐渐降低并趋于稳定，由于在固定范围内匹配给定模式的轨迹数量减少，因此I/O代价降低，且由图6可以看出LR-Tree的I/O代价及CPU时间明显低于另外4种索引。

(a) CPU时间比较

(b) I/O次数比较图6 查询标签数量对算法性能影响

4.2.4 查询时间区间长度对算法性能影响

由图7可以看出随着查询时间长度增加，I/O次数及CPU时间均呈增长趋势。

(a) CPU时间比较

(b) I/O次数比较图7 查询时间区间长度对算法性能影响

在查询过程中，给定查询时间区间长度的不同，导致与给定时间区间相交的节点增加或减少，影响查询返回结果，因此本节实验考虑查询时间区间长度的影响。由于查询时间长度增加，与查询时间区间相交的节点增加，通过索引过滤的轨迹数量减少，因此产生更多的I/O，导致CPU时间的增加。在5种索引中，随着查询时间增加，LR-Tree增长缓慢，可以看出基于LR-Tree的范围模式查询算法表现出良好的剪枝性能。

4.2.5 查询范围边长对算法性能影响

在本节实验比较查询空间范围的大小对查询效率的影响。本节实验设置(8500，9000)为查询矩形框左下方坐标，设置查询边长为矩形框边长，并以500为单位逐渐增大，实验结果如图8所示。可以看出随着矩形框范围逐渐增大，查询的I/O次数及CPU时间逐渐增加。由于查询空间范围增加，返回结果数增加，导致I/O次数及CPU时间增加。另外4种索引I/O次数增长较明显的同时，LR-Tree增长缓慢，可以看出LR-Tree查询算法相较于另外4种索引表现出更高效的剪枝能力。

(a) CPU时间比较

(b) I/O次数比较图8 查询范围边长对算法性能影响

5 结束语

本文提出范围模式匹配查询，并设计了一种基于标签R树的查询算法，考虑在给定时间区间范围内的语义查询问题。从不同参数的角度与基于已有索引的查询算法在真实数据和合成数据上进行对比，实验结果表明相较于包含语义信息的RR-Tree，基于标签R树的范围模式匹配查询算法查询效率提高40%～70%，验证了基于标签R树的范围模式匹配查询算法的有效性。未来将基于本文算法，提出在时间区间内包含多标签的范围模式匹配查询。