K近邻近似模式匹配查询

2019-01-24梁珺秀许建秋秦小麟

小型微型计算机系统 2018年12期

梁珺秀，许建秋，秦小麟

(南京航空航天大学计算机科学与技术学院，南京 211106)

1 引言

随着智能终端的广泛应用，包含语义的时空轨迹在用户查询中越来越常见，用户查询内容不再局限于时空属性，更包括轨迹上相应的语义属性.对包含语义属性的移动对象进行管理在众多领域中都具有广阔的应用前景[1-3].

常见的语义查询给出空间限制及查询语义，大多是在查询语义完全满足的情况下再进一步考虑在时空属性上是否满足，当查询用户并不要求语义属性完全满足且期望在时空距离上更接近时，现有包含语义属性的时空轨迹查询并不能全面地描述这类问题.为此，需要提出一种适用于此类近似匹配查询语义的技术，以支持更多查询请求.

给定语义模式：在迪斯尼乐园中，从小小世界出发，经过迪斯尼画廊和加勒比海盗，一段时间后经过巴斯光年的星际历险，游玩了若干景点最后到达歌舞基地.查询在2017年7月期间，满足部分给定语义模式，且距离用户上传轨迹较近的前K条轨迹，作为好友推荐目标.

如图1所示，[t1，t2]表示查询时间区间范围，Qtraj表示查询轨迹，traj1和traj2为轨迹集合中的两条轨迹，虚线部分表示与查询模式近似匹配的轨迹段.当查询条件中K为1，即返回与查询模式近似匹配且与查询轨迹较近的唯一一条轨迹，从语义属性角度来说，traj1与给定查询模式完全匹配，而traj2只匹配查询模式中部分模式，而从时空距离观察可得，traj2与查询轨迹距离比traj1更近.由于traj2模式匹配程度高，且从与查询轨迹的距离角度来说，与traj1相比，traj2距离Qtraj更近，当同时考虑模式匹配程度及时空距离时可以将traj2作为K近邻近似模式匹配查询结果返回.

目前还未有针对上述查询的研究成果发表，本文将这类查询定义为K近邻近似模式匹配查询，查询返回在给定时间区间内，模式匹配时空距离值最大的前K条轨迹，即返回结果匹配给定查询模式的同时能更接近查询轨迹.

图1 K近邻近似模式匹配查询Fig.1 K nearest neighbor approximate pattern match query

为解决K近邻近似模式匹配查询，本文主要贡献如下：

1)给出近似模式匹配及相关定义；

2)提出基于标签R树的K近邻近似模式匹配查询算法；

3)实现基于RR-Tree、3DR-Tree、TB-Tree和SETI的K近邻近似模式匹配查询算法，通过真实数据和合成数据，与基于标签R树的算法进行比较.

2 相关工作

目前针对具有语义的时空轨迹已有大量研究，主要包含活动轨迹[4]、语义轨迹[5]及符号轨迹[6].

活动轨迹[4]是由Zheng K等人提出的表示包含关于特定地点处的用户活动信息的新类型的轨迹数据，活动轨迹由点序列构成，每个点处包含时空属性和活动属性，时空属性即为时间点及对应的空间位置，活动属性由零个或多个活动所组成.在[4]中提出了ATSQ(Activity Trajectory Similarity Query)查询，查询结果返回覆盖查询活动且产生最短最小匹配距离的前K条轨迹，而查询OATSQ(Order-Sensitive Activity Trajectory Similarity Query)中考虑提出的活动是有顺序的，即返回的轨迹需匹配给定活动顺序.在[7]中提出了基于等级的活动轨迹搜索RTS(Ranking Based Activity Trajectory Search)，查询输入为一组活动和距离阈值，查询返回在距离阈值内包含所有查询活动，且排名最高前K条轨迹，基于顺序的活动轨迹搜索ORTS (Order-Sensitive Ranking Based Activity Trajectory Search)查询将活动顺序考虑在内.

语义轨迹是由 Alvares LO等人在[5]中提出用注释标记整个轨迹或其部分轨迹段，每个注释表示在其对应点处用户的状态或行为，用这些状态或行为来丰富几何轨迹.在文献[8]中，提出语义轨迹的模糊关键字查询，用户给出查询关键字，综合考虑语义轨迹与查询关键字的编辑距离和经过给定关键字的轨迹长度，返回代价最小的前K条轨迹.

符号轨迹[6]是由 Güting RH等人提出的不包含空间位置属性，轨迹表现为随时间变化的标签，即为时间区间到标签值上映射的轨迹.文献[6]提出了一种模式匹配语言，模式通过符号来描述具有期望结构的列表，当给出的模式中内容与符号轨迹单元内容相同，则称这两个匹配.当指定的模式与轨迹匹配时，可用于从数据库关系中过滤得到满足特定模式的轨迹.在[9]中提出了一种在符号属性和空间轨迹上的混合查询，从符号的维度提取满足给定模式的符号子轨迹，由子轨迹的时间范围来限制空间维度，当子轨迹空间维度与几何条件匹配时，则将其作为结果返回，最终得到同时满足符号和时空条件的轨迹集合.

3 问题描述

3.1 问题定义

定义1.时空标签轨迹：时空标签轨迹可表示为

traj=<[I1，l1，loc11，loc21]，…，[In，ln，loc1n，loc2n]>

其中任意[Ij，lj，loc1j，loc2j]表示第j个时空标签轨迹单元；其中Ij表示第j个单元对应的时间区间，lj表示单元j对应的标签；loc11表示时间区间Ij开始时刻Inss对应的地理位置，loc2j表示时间区间Ij结束时刻Inse对应的地理位置.

定义2.模式：P=，其中pi为以下两种形式之一：

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

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

由定义可知当traj中存在轨迹段的标签信息，与P中标签的内容相同且顺序一致时，称轨迹与P模式匹配.模式匹配查询存在以下特点：

1) 模式匹配能处理较复杂的语义属性查询请求；

2)将模式匹配与时空属性查询相结合，能解决不同维度的查询.

定义4.近似模式匹配(Approximate Pattern Match，APmatch(traj，P))：对于模式P=及轨迹traj，若存在P中子模式P′=，其中1≤i≤j≤n，P′中包含单元模式或所有的简单模式p不全为*，+等通配符，使得traj匹配模式<*，P′，*>，则称traj近似模式匹配P.

由定义可知，traj近似模式匹配P表示P中存在子模式P′，使得traj模式匹配<*，P′，*>，且子模式P′中包含单元模式或所有的简单模式不全为模式定义中给出的通配符，即子模式P′中存在一个或一个以上的语义标签.

定义5.模式长度(Pattern length，PLen(P))：对模式P=，模式中所有单元模式和非通配符简单模式的个数即为当前模式P的模式长度.

在引言给出的语义模式中，查询模式可以表示为P = <(小小世界)，*，(画廊)，(加勒比海盗)，*，(星际历险)，+，(歌舞基地)>，对于该模式的模式长度为5.

定义6.最大匹配子模式(Maximum Matching Subpattern，MMS(traj，P))：对于模式P=及给定轨迹traj，S为traj匹配的所有子模式的集合，最大匹配子模式返回P′∈S，对∀P*∈S，有PLen(P′)≥PLen(P*)，则P′为traj对应于P的最大匹配子模式.

定义7.模式匹配度(Degree of Pattern Match，DPM(traj，P))：对于模式P=及给定轨迹traj，模式匹配度为最大匹配子模式长度与模式P长度的比值，表示为：

DPM(traj，P)=PLen(MMS(traj，P))/PLen(P)

由上述公式计算可得轨迹与给定查询模式的匹配程度，得到的值为(0，1]区间内，注意值域左边为开区间，表示模式匹配度值域不包含0.根据近似模式匹配定义，子模式中至少包含一个或一个以上的语义标签信息，因此DPM(traj，P)>0必然成立.

定义8.轨迹插值(Interpolate(I，traj))：给定时间区间I，Interpolate(I，traj)返回轨迹traj在时间区间I内的子轨迹段.

定义9.模式匹配时空距离(Pattern Match Spatio-Temporal Distance，PSTDist)：给定时间区间I，查询轨迹Qtraj，查询模式P，及模式匹配程度系数α，其中0≤α<1，traj的模式匹配时空距离表示为：

PSTDist(P，Qtraj，α，traj，I)=α*(DPM(traj，P))+(1-α)

其中I′表示时间区间I与Qtraj的定义时间区间的交集，Interpolate(I′，traj)表示时间区间I′内的轨迹插值，即为I′内的子轨迹段，MaxDist表示时空上的最大距离值，选取轨迹数据中距离最远的两个点作为最大距离值MaxDist.

定义10.K近邻近似模式匹配查询(K Nearest Neighbor Approximate Pattern Match Query，KAPMQ)：给定时间区间I，查询轨迹Qtraj，查询模式P，及模式匹配程度系数α，其中0≤α<1，返回轨迹集合D中大小为k的子集D′：

1) 对∀traj∈D′，Interpolate(I∩Qtraj.interval，traj)≠φ；

2) 对∀traj′∈D-D′，都有PSTDist(P，Qtraj，α，traj，I)≥PSTDist(P，Qtraj，α，traj′，I).

3.2 标签R树

标签R树LR-Tree(Label R-Tree)，形式上由一个 3DR-Tree[10]和一个标签表组成，标签表中不重复的保存时空标签轨迹数据集中出现的所有标签，而空间位图层与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为所指向的时空标签轨迹包含的所有标签到标签表的映射计算所得的位图.

4 K近邻近似模式匹配查询

K近邻近似模式匹配查询返回在时间区间I内，综合考虑与查询轨迹间的距离值及与给定查询模式的匹配程度，返回模式匹配时空距离值最大的前K条轨迹.提出基于LR-Tree的K近邻近似模式匹配查询算法，在遍历LR-Tree的过程中利用优先队列Q存储当前找到的模式匹配时空距离最大的前K条轨迹，并以查询时间区间、节点项位图及队列Q中最小模式匹配时空距离值作为剪枝条件，最后Q中的所有轨迹即为本次K近邻近似模式匹配查询结果.

定义11.项模式匹配度(Degree of Pattern Match in Entry，DPME(E，P))：给定模式P=及节点项E，对于查询模式P的位图Tbit中为1的每一位，统计项位图Ebit对应位为1的个数记为Enum，与P的模式长度PLen(P)的比值称为项模式匹配度，表示为：

DPME(E，P)=Enum/PLen(P)

定义12.项模式匹配时空距离(Entry Pattern Match Spatio-Temporal Distance，EPSTDist(E，QBox，α))：给定项E，查询轨迹矩形框QBox，及模式匹配程度系数α，其中0≤α<1，项E的模式匹配时空距离表示为：

EPSTDist(E，QBox，α)=

在近似模式匹配查询中返回的是模式匹配时空距离最大的前K个，因此不能仅根据矩形框间距离值进行剪枝，需要同时考虑匹配程度.基于LR-Tree的K近邻近似模式匹配查询算法如算法1所示，主要包括以下步骤：

算法1.K近邻近似模式匹配查询

输入：查询模式P

查询时间区间1

查询轨迹Qtraj

查询结果个数k

移动对象集合D

偏好系数α

LR-Tree

输出：优先队列Q

1：Q←φ；S←φ；

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

3:QMBR←q.MBR();

4:WHILE(S不为空)

5： Node←S.top();S.pop();

6: L←φ;

7:FOREACHentryNode

8: EMBR←entry.MBR();

9:IF(((Ι∩Qtraj.timeIntercval)与EMBR.timeIntercval相交)&(EPE(E,P)≠0))

10:IF(Node为非叶节点)

11： minValue←minDist(Q.PSTDist);

12:IF((|Q|=k & EPSTDist(E,QBox,α)>min Value)||(|Q|

13： L.push(E);

14:ENDIF

15:ENDIF

16:IF(Node为叶节点)

17： UpdateQ(E,Q,P,α,Qtraj,k);

18:ENDIF

19:ENDIF

20:ENDFOR

21:IF(L≠φ)

22:L.sort();//将L中项按EPSTDist值排序

23：将L中所有项指向节点按从小到大的顺序依次入栈S；

24:ENDIF

25:ENDWHILE

26:RETURNQ

1)设置保存查询结果长度为K的优先队列Q，其中Q按照模式匹配时空距离值排序，存储LR-Tree内部节点的栈S，及对内部节点排序的列表L，首先将LR-Tree根节点入栈S；

2)将栈S中节点N出栈，对于N中所有节点项E，判断查询模式位图Tbit为1的所有位在E中位图对应位上是否至少存在一个为1，将不存在的节点项所指向的子树从树中裁剪，进一步判断当前节点项的定义时间区间是否与给定时间区间I和查询轨迹Qtraj的定义时间区间的交集相交，对不相交的节点项进行剪枝，最后计算E的项模式匹配时空距离EPSTDist；

3)对于满足2)的节点项，如果当前节点N为非叶节点，若队列Q未满，则将E加入L中，若Q长度为k，则将EPSTDist与Q中最小模式匹配时空距离值minValue比较，当EPSTDist>minValue，则将E加入L中.将N中所有满足条件的节点项加入L中后，按项模式匹配时空距离大小排序，将排序后L中所有节点项指向的子节点按顺序依次入栈S，确保下次出栈的为栈S中项模式匹配时空距离最大值节点；如果N为叶节点，若Q未满，将E所指向时空标签轨迹M加入Q中，若队列若Q长度为K，当EPSTDist>minValue时，则对节点项E所指向的时空标签轨迹M进行精细计算，得到模式匹配时空距离PSTDist，当PSTDist>minValue时将M加入Q中，并将PSTDist值最小的队首元素删除，保持队列长度为K；

4)遍历LR-Tree结束，栈S为空，队列Q中保存的所有轨迹即为K近邻近似模式匹配查询结果.

4.1 K近邻近似模式匹配查询筛选

基于LR-Tree的K近邻近似模式匹配查询算法的筛选步骤主要由三部分组成：

1)查询时间区间，查询时间区间由给定时间区间与查询轨迹定义时间区间的交集所组成；

2)LR-Tree叶节点中位图，由叶节点项中位图可得当前项所指向的子节点所包含的时空标签轨迹中存在的标签，若查询模式中所有标签在项位图对应位上全为0，如算法1第9行所示EPE(E，P)=0，表示当前项所指向子节点中不包含查询模式中任意一个标签，则该子节点包含的所有时空标签轨迹均不可能作为结果返回，因此可以将以该项所指向的节点为根节点的子树剪去；

3)优先队列Q中最小模式匹配时空距离值minValue，对于每个访问的项可以计算出相应的项模式匹配时空距离值EPSTDist，将EPSTDist与minValue对比，在特定的情况下对LR-Tree进行剪枝.计算过程中采用根节点的MBR对角线长度作为最大距离值MaxDist.

图2 边框矩形与轨迹关系Fig.2 MBR and trajectory

引理1.非叶节点项的项模式匹配时空距离值EPSTDist1大于等于所指向子节点中项的项模式匹配时空距离值EPSTDist2.

证明：由项模式匹配时空距离值定义，

EPSTDist(E，QBox，α)

EPSTDist值的大小受距离值Dist(E.box，QBox)和项模式匹配度DPME(E，P)影响.

1)图2中BBox1和BBox2表示非叶节点项E1和子节点项E2的边框矩形，可以看出边框矩形BBox1与查询轨迹Qtraj的距离dis1比边框矩形BBox2与查询轨迹Qtraj的距离dis2更近，可得Dist(BBox1，QBox)≤Dist(BBox2，QBox).

2)而由LR-Tree定义可知，上层节点项E1中位图BSet1由所指向的下层节点中所有项执行按位或操作所得，因此E2位图BSet2中为1的位在E1位图中也必定为1，且E1中位为1的个数必定大于等于E2中1的个数，则DPME(E1，P)≥DPME(E2，P).

由定义可知，EPSTDist值与DPME呈正相关，与Dist呈负相关，综合(1)(2)可知

EPSTDist(E1，QBox，α)≥EPSTDist(E2，QBox，α)

引理1得证.

引理2.叶节点项的项模式匹配时空距离大于等于项所指向的时空标签轨迹的模式匹配距离.

证明：对于叶节点项E及其指向的时空标签轨迹traj，由图2可以看出查询轨迹Qtraj的边框矩形QBox与E的边框矩形BBox2的距离值dis2小于等于Qtraj与traj两条轨迹本身间的距离值dis3，即Dist(BBox2，QBox)≤Dist(traj，Qtraj).

而从项中位图考虑，在位图中仅考虑查询模式中标签的存在性，而对于时空标签轨迹，还需进一步考虑语义标签的顺序是否匹配，因此最大匹配子模式PLen(MMS(traj，P))≤Enum，根据模式匹配度定义，可得DPM(traj，P)≤DPME(E，P).

由项模式匹配时空距离及模式匹配时空距离定义可知

EPSTDist(E，QBox，α)≥PSTDist(P，Qtraj，α，traj)

引理2得证.

K近邻近似模式匹配中需要综合考虑距离值及模式匹配程度两方面，因此在访问LR-Tree的内部节点时，无法仅根据空间距离值来进行剪枝，而空间剪枝在提高查询效率的过程中占很重要的作用，因此需要考虑引入新属性对节点进行剪枝.由于项中保存了表示标签存在性的位图及最小边框矩形MBR，分别对应至语义及时空两种属性，因此考虑利用位图和MBR计算出项模式匹配时空距离值EPSTDist，将EPSTDist的值与优先队列Q中的最小模式匹配时空距离值minValue比较，由引理1及引理2可知，当节点项的EPSTDist小于等于minValue时，节点项所指向的子节点的EPSTDist或时空标签轨迹的PSTDist均小于当前节点的EPSTDist，因此不可能作为结果返回，可以将以当前项所指向的节点为根节点的子树裁剪.

在遍历LR-Tree过程中，对每个访问的内部节点设置列表L，如算法1第13行所示将满足条件的节点项E加入L中，在当前节点中所有项访问结束后，将L中所有项按照EPSTDist的值进行排序，并将排序后的L中所有项所指向的节点按顺序入栈S，保证下次栈S中出栈的节点为L中EPSTDist值最大项对应节点.EPSTDist值越大表示项模式匹配度越高或距离越近，查询结果出现在此节点中的概率越大，因此优先队列Q长度能尽早达到K，并利用长度为K的优先队列中的最小模式匹配时空距离minValue进行剪枝，提高查询效率.

4.2 K近邻近似模式匹配查询精细计算

在遍历LR-Tree过程中得到EPSTDist>minValue的节点项，需要进行进一步的精细计算，判断项所指向的时空标签轨迹能否加入返回结果队列Q中，具体步骤如算法2所示.

算法2.优先队列更新UpdateQ

输入:节点项E

优先队列Q

查询模式P

偏好系数α

查询轨迹Qtraj

查询结果个数k

输出：更新entry后的优先队列Q

1：IF(|Q|

2: Q.insert(entry.tid);//插入后的栈中的entry按距离值排序

3：ELSE

4: min Value←(Q.top()).PSTDist;

5:IF(EPSTDist(E,QBox,α)>min Value)

6: traj←entry.ptr指向移动对象；

7：IF(PSTDist(P,Qtraj,α,traj)>min Value)

8: Q.insert(entry.tid);

9: Q.pop();//保持优先队列长度为k

10： min Value←(Q.top()).PSTDist;//得到新阈值min Value

11:ENDIF

12:ENDIF

13:ENDIF

14:RETURNQ

当优先队列Q未满时将项所指向的时空标签轨迹直接插入至优先队列中，而当|Q|=K时，需要进行进一步计算.由引理2可知对于叶节点项E及E指向的时空标签轨迹，存在EPSTDist≥PSTDist，因此仅得到EPSTDist>minValue并不能判断出时空标签轨迹的模式匹配时空距离值大于阈值minValue，需要进行精细计算得到时空标签轨迹的PSTDist，当PSTDist> minValue时，才将时空标签轨迹加入Q中.

在精细计算PSTDist时，主要计算两部分：

1)模式匹配度，模式匹配度通过轨迹最大匹配子模式MMS(traj，P)与给定查询模式P的模式长度比值所得；

2)轨迹间距离值，首先计算时空标签轨迹在给定时间区间与查询轨迹定义时间区间交集I′内的轨迹插值，得到I′内的子轨迹段，利用子轨迹段与查询轨迹进行轨迹间距离值计算.在得到1)2)后，根据模式匹配时空距离值定义计算得到PSTDist.遍历LR-Tree后Q中所有轨迹即为K近邻近似模式匹配查询结果.

5 实验与性能测试

5.1 对比实验索引介绍

对比实验实现语义索引RR-Tree及三种传统移动对象索引3DR-Tree[10]、SETI[11]、TB-Tree[12].RR-Tree通过语义属性及时空属性进行剪枝， 3DR-Tree、SETI、TB-Tree通过时空属性进行剪枝.

模式匹配查询中需要对整条轨迹上的语义进行比较，而在网格索引结构中将轨迹划分为不同的轨迹段，可能造成重复计算，因此将HAG中的网格结构替换为R树索引结构.RR-Tree采用[13]中的思想，实现在R树节点项中插入最大最小值的结构，并命名为RR-Tree.RR-Tree节点结构如图3所示，N为RR-Tree的节点，N中包含若干节点项E，E中包含MBR和pointer/tid，与R-Tree定义相同，其中Min(Max)表示以该节点项为根节点的子树中包含的最小(大)语义数值.

图3 RR-Tree节点结构Fig.3 RR-Tree node structure

在RR-Tree中，每个语义标签对应唯一的ID，节点项中Min(Max)代表所有子节点最小(大)ID.在查询过程中，首先判断查询模式P中所有的语义标签是否都出现在[Min，Max]范围内，对于满足条件的节点项再进一步根据结点项中的MBR与给定查询时空条件计算来进行剪枝，3DR-Tree在时空上的计算与RR-Tree相同.

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

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

5.2 查询性能测试

实验使用真实数据集和合成数据集，两种数据均表示语义属性对应至时间区间上的时空轨迹.合成数据集为开源数据库SECONDO[15]中模拟地铁轨迹的数据Trains，其中包含562辆地铁的运动轨迹，为每条轨迹贴上不同的合成标签，其中标签为1-50中的任意数字，每个数字表示不同的标签，每种标签出现的概率相同，每条轨迹包含5-10个标签.采用数据加倍方法对轨迹进行空间x、y方向上的偏移，得到平移的轨迹数据.数据集信息如表1所示，Train(n)表示在Train的基础上进行x、y方向上的平移得到的n平方倍数据.

表1 数据集数据统计Table 1 Data set statistics

真实数据集是微软亚洲研究院Geolife[14]，项目组收集182个用户3年内的GPS数据，其中部分用户用交通方式标记了他们的运动数据(如步行、火车等)，表2记录Geolife中出现的所有标签，统计不同标签出现次数.

表2 标签频数Table 2 Labelfrequency

表3 实验参数Table 3 Experimental parameters

为验证本章提出的基于LR-Tree的K近邻近似模式匹配查询算法的有效性，采用C++语言在Linux环境下扩展可扩充移动对象数据库SECONDO，对LR-Tree、RR-Tree、3DR-Tree、SETI及TB-Tree索引结构进行实现，实验环境为：Intel(R) Core(TM) I3-2120 CPU @3及SECONDO系统中合成地铁轨迹数据集Train，本部分实验参数设置如表3所示.

5.2.1 数据集对算法性能影响

本部分实验以不同规模数据集为实验数据，在查询模式，偏好系数α、给定时间区间及返回结果数参数相同的情况下，对比五种不同的索引在不同的数据集下的I/O次数和CPU时间，实验结果如图4所示，随着数据集大小增加，I/O次数及CPU时间也呈迅速增长趋势，由低到高依次是LR-Tree、RR-Tree、3DR-Tree、TB-Tree及SETI.相较于包含语义信息的RR-Tree索引，基于LR-Tree的K近邻近似模式匹配查询算法降低了约60%的I/O次数及CPU时间.这是由于基于LR-Tree的查询算法在查询过程中能更好的利用项模式匹配时空距离和Q中minValue值对比，将不可能作为结果返回的节点进行剪枝，从而达到提高查询效率的效果.

图4 数据集对算法性能影响Fig.4 Effect of dataset amount

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

本部分实验考虑相同条件下标签数量对查询算法效率的影响，其中标签数量表示查询模式中单元模式及除通配符外简单模式的个数.

图5 标签数对算法性能影响Fig.5 Effect of label number

如图5所示，随着标签数增加，I/O次数和CPU时间也增加，这是因为随着标签数增加，大程度匹配给定查询模式的轨迹减少，因此Q中minValue的值降低，导致LR-Tree的剪枝效果降低，进而使得I/O次数及CPU时间增加.当标签数大于3时，另四种索引的空间剪枝能力大幅降低，基于LR-Tree的K近邻近似模式匹配查询算法提高了约90%以上的查询效率，显著优于基于RR-Tree、3DR-Tree、TB-Tree及SETI的查询算法.

基于LR-Tree的K近邻近似模式匹配算法中，对于出栈的非叶节点中所有满足条件的节点项，按照节点项的项模式匹配时空距离EPSTDist排序后，将所指向的子节点依次入栈.本部分实验对比排序及不排序的基于LR-Tree的K近邻近似模式匹配算法在不同标签数下的I/O次数及CPU时间，实验结果如图6所示.

由图6可以看出基于LR-Tree的排序算法效果优于不排序算法.因为排序后入栈能保证下一次出栈的节点是当前栈中EPSTDist值最大的节点，当EPSTDist值越大，以该节点为根节点的时空标签轨迹中包含较大的模式匹配时空距离值PSTDist值的可能性越大.因此能尽早将队列Q填满，更有效的利用Q中的minValue值进行剪枝.因此相较于不排序算法，排序算法能更有效的提高约30%查询效率.

图6 排序算法影响Fig.6 Algorithm withor without sort

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

本部分实验以GeoLife为实验数据，比较在真实数据下不同出现频率的标签对K近邻近似模式匹配查询算法的影响.在查询模式中只包含其中一个标签，GeoLife中标签出现频率如表2所示，结合图7可以看出，相较于不包含语义的索引，标签出现频率越小，如airplane、train等，基于LR-Tree的查询算法的I/O次数和CPU时间减少约40%以上.在筛选过程中包含位图筛选，由于标签出现频率越低，对应位图中位为1的节点项越少，包含语义属性的索引LR-Tree中位图剪枝效果越好.

图7 查询模式对算法性能影响Fig.7 Effect of query pattern

5.2.4 给定时间区间长度对算法性能影响

本部分实验设置在其他查询参数一定的情况下，对比不同时间区间长度对查询算法影响，查询时间区间的开始时刻设置为查询轨迹的定义时间区间开始时刻，实验结果如图8所示.

图8 给定时间区间长度对算法性能影响Fig.8 Effect of time interval

由图8可以看出，随着查询时间区间长度增加，I/O次数及CPU时间增加并逐渐趋于稳定.这是因为基于LR-Tree的K近邻近似模式匹配算法的筛选过程中包含时间区间筛选，时间区间长度增加，定义时间区间与查询时间区间相交的轨迹数量也增加，被裁剪的节点减少，导致I/O次数及CPU时间增加.而查询轨迹的定义时间区间长度为3h-4h，在计算过程中查询时间区间是由给定时间区间及查询轨迹定义时间区间的交集所得，因此当给定时间区间长度大于查询轨迹定义时间区间时，查询时间区间即为查询轨迹定义时间区间，I/O次数及CPU时间保持不变.相较于RR-Tree查询效率降低了40%-50%.

5.2.5 返回结果数对算法性能影响

本部分实验对比不同返回结果数K对K近邻近似模式匹配查询算法的影响.由图9可以看出，随着返回结果数增加，I/O次数及CPU时间也呈增加趋势.这是因为在遍历LR-Tree过程中，需要利用Q中最小模式匹配时空距离值minValue进行剪枝，当返回结果数K越大，队列Q长度越大，导致minValue值越小，在筛选过程中利用minValue剪枝的效果降低，导致I/O次数及CPU时间增加.而从图10可以看出，由于K数值增大，空间剪枝能力大幅降低，基于LR-Tree的查询算法相较于同样能表示语义信息的RR-Tree的查询算法效率降低约60%-70%，表现出更好的剪枝效果.

图9 返回结果数K对算法性能影响Fig.9 Effect of resultnumber

5.2.6 偏好系数α对算法性能影响

在其它查询参数相同的情况下，本部分实验对比不同偏好系数α对K近邻近似模式匹配查询结果的影响.实验结果如图10所示，可以看出，随着偏好系数α增加，I/O次数及CPU时间增大.这是因为α是模式匹配程度的偏好系数，α值越小，查询越接近于不包含语义属性的K近邻查询，根据时空属性能进行很好的裁剪，因此五种索引剪枝效果较好，而当α值越大，时空属性占比减小，导致时空剪枝能力降低，时空索引I/O次数及CPU时间显著增加.在K近邻近似模式匹配查询中，基于LR-Tree的时空属性剪枝效果比语义剪枝效果好，因此当偏好系数增加时，I/O次数及CPU时间增加.相较于能表示语义的RR-Tree，基于LR-Tree的K近邻近似模式匹配查询算法在不同偏好系数下查询效率提高了约70%.