K近鄰近似模式匹配查詢

梁珺秀，許建秋，秦小麟

(南京航空航天大學 計算機科學與技術學院，南京 211106)

1 引 言

隨著智能終端的廣泛應用，包含語義的時空軌跡在用戶查詢中越來越常見，用戶查詢內容不再局限于時空屬性，更包括軌跡上相應的語義屬性.對包含語義屬性的移動對象進行管理在眾多領域中都具有廣闊的應用前景[1-3].

常見的語義查詢給出空間限制及查詢語義，大多是在查詢語義完全滿足的情況下再進一步考慮在時空屬性上是否滿足，當查詢用戶并不要求語義屬性完全滿足且期望在時空距離上更接近時，現有包含語義屬性的時空軌跡查詢并不能全面地描述這類問題.為此，需要提出一種適用于此類近似匹配查詢語義的技術，以支持更多查詢請求.

給定語義模式：在迪斯尼樂園中，從小小世界出發(fā)，經過迪斯尼畫廊和加勒比海盜，一段時間后經過巴斯光年的星際歷險，游玩了若干景點最后到達歌舞基地.查詢在2017年7月期間，滿足部分給定語義模式，且距離用戶上傳軌跡較近的前K條軌跡，作為好友推薦目標.

如圖1所示，[t1，t2]表示查詢時間區(qū)間范圍，Qtraj表示查詢軌跡，traj1和traj2為軌跡集合中的兩條軌跡，虛線部分表示與查詢模式近似匹配的軌跡段.當查詢條件中K為1，即返回與查詢模式近似匹配且與查詢軌跡較近的唯一一條軌跡，從語義屬性角度來說，traj1與給定查詢模式完全匹配，而traj2只匹配查詢模式中部分模式，而從時空距離觀察可得，traj2與查詢軌跡距離比traj1更近.由于traj2模式匹配程度高，且從與查詢軌跡的距離角度來說，與traj1相比，traj2距離Qtraj更近，當同時考慮模式匹配程度及時空距離時可以將traj2作為K近鄰近似模式匹配查詢結果返回.

目前還未有針對上述查詢的研究成果發(fā)表，本文將這類查詢定義為K近鄰近似模式匹配查詢，查詢返回在給定時間區(qū)間內，模式匹配時空距離值最大的前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]中提出用注釋標記整個軌跡或其部分軌跡段，每個注釋表示在其對應點處用戶的狀態(tài)或行為，用這些狀態(tài)或行為來豐富幾何軌跡.在文獻[8]中，提出語義軌跡的模糊關鍵字查詢，用戶給出查詢關鍵字，綜合考慮語義軌跡與查詢關鍵字的編輯距離和經過給定關鍵字的軌跡長度，返回代價最小的前K條軌跡.

符號軌跡[6]是由 Güting RH等人提出的不包含空間位置屬性，軌跡表現為隨時間變化的標簽，即為時間區(qū)間到標簽值上映射的軌跡.文獻[6]提出了一種模式匹配語言，模式通過符號來描述具有期望結構的列表，當給出的模式中內容與符號軌跡單元內容相同，則稱這兩個匹配.當指定的模式與軌跡匹配時，可用于從數據庫關系中過濾得到滿足特定模式的軌跡.在[9]中提出了一種在符號屬性和空間軌跡上的混合查詢，從符號的維度提取滿足給定模式的符號子軌跡，由子軌跡的時間范圍來限制空間維度，當子軌跡空間維度與幾何條件匹配時，則將其作為結果返回，最終得到同時滿足符號和時空條件的軌跡集合.

3 問題描述

3.1 問題定義

定義1.時空標簽軌跡：時空標簽軌跡可表示為

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

其中任意[Ij，lj，loc1j，loc2j]表示第j個時空標簽軌跡單元；其中Ij表示第j個單元對應的時間區(qū)間，lj表示單元j對應的標簽；loc11表示時間區(qū)間Ij開始時刻Inss對應的地理位置，loc2j表示時間區(qū)間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]區(qū)間內，注意值域左邊為開區(qū)間，表示模式匹配度值域不包含0.根據近似模式匹配定義，子模式中至少包含一個或一個以上的語義標簽信息，因此DPM(traj，P)>0必然成立.

定義8.軌跡插值(Interpolate(I，traj))：給定時間區(qū)間I，Interpolate(I，traj)返回軌跡traj在時間區(qū)間I內的子軌跡段.

定義9.模式匹配時空距離(Pattern Match Spatio-Temporal Distance，PSTDist)：給定時間區(qū)間I，查詢軌跡Qtraj，查詢模式P，及模式匹配程度系數α，其中0≤α<1，traj的模式匹配時空距離表示為：

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

其中I′表示時間區(qū)間I與Qtraj的定義時間區(qū)間的交集，Interpolate(I′，traj)表示時間區(qū)間I′內的軌跡插值，即為I′內的子軌跡段，MaxDist表示時空上的最大距離值，選取軌跡數據中距離最遠的兩個點作為最大距離值MaxDist.

定義10.K近鄰近似模式匹配查詢(K Nearest Neighbor Approximate Pattern Match Query，KAPMQ)：給定時間區(qū)間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) 每個節(jié)點的項(entry)中增加一個預設定長度的位圖，樹中所有節(jié)點項中位圖長度相同，位圖由一串”0/1”組成，“0/1”代表了當前項指向的子節(jié)點的標簽存在性，當位為1時，表示位對應至標簽表中的標簽存在，為0則不存在；

2) 位圖的每位通過哈希函數對應到標簽表中的一個或多個位置，其中標簽表的每行保存不同標簽.葉節(jié)點項位圖中的每一位表示所指向移動對象標簽的存在性，非葉節(jié)點項中的位圖通過所有子節(jié)點的位圖執(zhí)行按位或操作得出.

LR-Tree內部節(jié)點項表示為(rid，MBR，bitset)，其中rid指向當前節(jié)點的下層子節(jié)點，MBR是將rid指向的子節(jié)點中所有項的MBR包圍的最小矩形框，bitset由rid所指向的子節(jié)點中所有子節(jié)點項位圖執(zhí)行按位或操作得到.葉節(jié)點項存儲形式為(tid，MBR，bitset)，其中tid指向存儲在磁盤空間上的時空標簽軌跡，MBR為將該軌跡包圍的最小邊框矩形，bitset為所指向的時空標簽軌跡包含的所有標簽到標簽表的映射計算所得的位圖.

4 K近鄰近似模式匹配查詢

K近鄰近似模式匹配查詢返回在時間區(qū)間I內，綜合考慮與查詢軌跡間的距離值及與給定查詢模式的匹配程度，返回模式匹配時空距離值最大的前K條軌跡.提出基于LR-Tree的K近鄰近似模式匹配查詢算法，在遍歷LR-Tree的過程中利用優(yōu)先隊列Q存儲當前找到的模式匹配時空距離最大的前K條軌跡，并以查詢時間區(qū)間、節(jié)點項位圖及隊列Q中最小模式匹配時空距離值作為剪枝條件，最后Q中的所有軌跡即為本次K近鄰近似模式匹配查詢結果.

定義11.項模式匹配度(Degree of Pattern Match in Entry，DPME(E，P))：給定模式P=及節(jié)點項E，對于查詢模式P的位圖Tbit中為1的每一位，統(tǒng)計項位圖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

查詢時間區(qū)間1

查詢軌跡Qtraj

查詢結果個數k

移動對象集合D

偏好系數α

LR-Tree

輸出：優(yōu)先隊列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為非葉節(jié)點)

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為葉節(jié)點)

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

18:ENDIF

19:ENDIF

20:ENDFOR

21:IF(L≠φ)

22:L.sort();//將L中項按EPSTDist值排序

23： 將L中所有項指向節(jié)點按從小到大的順序依次入棧S；

24:ENDIF

25:ENDWHILE

26:RETURNQ

1)設置保存查詢結果長度為K的優(yōu)先隊列Q，其中Q按照模式匹配時空距離值排序，存儲LR-Tree內部節(jié)點的棧S，及對內部節(jié)點排序的列表L，首先將LR-Tree根節(jié)點入棧S；

2)將棧S中節(jié)點N出棧，對于N中所有節(jié)點項E，判斷查詢模式位圖Tbit為1的所有位在E中位圖對應位上是否至少存在一個為1，將不存在的節(jié)點項所指向的子樹從樹中裁剪，進一步判斷當前節(jié)點項的定義時間區(qū)間是否與給定時間區(qū)間I和查詢軌跡Qtraj的定義時間區(qū)間的交集相交，對不相交的節(jié)點項進行剪枝，最后計算E的項模式匹配時空距離EPSTDist；

3)對于滿足2)的節(jié)點項，如果當前節(jié)點N為非葉節(jié)點，若隊列Q未滿，則將E加入L中，若Q長度為k，則將EPSTDist與Q中最小模式匹配時空距離值minValue比較，當EPSTDist>minValue，則將E加入L中.將N中所有滿足條件的節(jié)點項加入L中后，按項模式匹配時空距離大小排序，將排序后L中所有節(jié)點項指向的子節(jié)點按順序依次入棧S，確保下次出棧的為棧S中項模式匹配時空距離最大值節(jié)點；如果N為葉節(jié)點，若Q未滿，將E所指向時空標簽軌跡M加入Q中，若隊列若Q長度為K，當EPSTDist>minValue時，則對節(jié)點項E所指向的時空標簽軌跡M進行精細計算，得到模式匹配時空距離PSTDist，當PSTDist>minValue時將M加入Q中，并將PSTDist值最小的隊首元素刪除，保持隊列長度為K；

4)遍歷LR-Tree結束，棧S為空，隊列Q中保存的所有軌跡即為K近鄰近似模式匹配查詢結果.

4.1 K近鄰近似模式匹配查詢篩選

基于LR-Tree的K近鄰近似模式匹配查詢算法的篩選步驟主要由三部分組成：

1)查詢時間區(qū)間，查詢時間區(qū)間由給定時間區(qū)間與查詢軌跡定義時間區(qū)間的交集所組成；

2)LR-Tree葉節(jié)點中位圖，由葉節(jié)點項中位圖可得當前項所指向的子節(jié)點所包含的時空標簽軌跡中存在的標簽，若查詢模式中所有標簽在項位圖對應位上全為0，如算法1第9行所示EPE(E，P)=0，表示當前項所指向子節(jié)點中不包含查詢模式中任意一個標簽，則該子節(jié)點包含的所有時空標簽軌跡均不可能作為結果返回，因此可以將以該項所指向的節(jié)點為根節(jié)點的子樹剪去；

3)優(yōu)先隊列Q中最小模式匹配時空距離值minValue，對于每個訪問的項可以計算出相應的項模式匹配時空距離值EPSTDist，將EPSTDist與minValue對比，在特定的情況下對LR-Tree進行剪枝.計算過程中采用根節(jié)點的MBR對角線長度作為最大距離值MaxDist.

圖2 邊框矩形與軌跡關系Fig.2 MBR and trajectory

引理1.非葉節(jié)點項的項模式匹配時空距離值EPSTDist1大于等于所指向子節(jié)點中項的項模式匹配時空距離值EPSTDist2.

證明：由項模式匹配時空距離值定義，

EPSTDist(E，QBox，α)

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

1)圖2中BBox1和BBox2表示非葉節(jié)點項E1和子節(jié)點項E2的邊框矩形，可以看出邊框矩形BBox1與查詢軌跡Qtraj的距離dis1比邊框矩形BBox2與查詢軌跡Qtraj的距離dis2更近，可得Dist(BBox1，QBox)≤Dist(BBox2，QBox).

2)而由LR-Tree定義可知，上層節(jié)點項E1中位圖BSet1由所指向的下層節(jié)點中所有項執(zhí)行按位或操作所得，因此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.葉節(jié)點項的項模式匹配時空距離大于等于項所指向的時空標簽軌跡的模式匹配距離.

證明：對于葉節(jié)點項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的內部節(jié)點時，無法僅根據空間距離值來進行剪枝，而空間剪枝在提高查詢效率的過程中占很重要的作用，因此需要考慮引入新屬性對節(jié)點進行剪枝.由于項中保存了表示標簽存在性的位圖及最小邊框矩形MBR，分別對應至語義及時空兩種屬性，因此考慮利用位圖和MBR計算出項模式匹配時空距離值EPSTDist，將EPSTDist的值與優(yōu)先隊列Q中的最小模式匹配時空距離值minValue比較，由引理1及引理2可知，當節(jié)點項的EPSTDist小于等于minValue時，節(jié)點項所指向的子節(jié)點的EPSTDist或時空標簽軌跡的PSTDist均小于當前節(jié)點的EPSTDist，因此不可能作為結果返回，可以將以當前項所指向的節(jié)點為根節(jié)點的子樹裁剪.

在遍歷LR-Tree過程中，對每個訪問的內部節(jié)點設置列表L，如算法1第13行所示將滿足條件的節(jié)點項E加入L中，在當前節(jié)點中所有項訪問結束后，將L中所有項按照EPSTDist的值進行排序，并將排序后的L中所有項所指向的節(jié)點按順序入棧S，保證下次棧S中出棧的節(jié)點為L中EPSTDist值最大項對應節(jié)點.EPSTDist值越大表示項模式匹配度越高或距離越近，查詢結果出現在此節(jié)點中的概率越大，因此優(yōu)先隊列Q長度能盡早達到K，并利用長度為K的優(yōu)先隊列中的最小模式匹配時空距離minValue進行剪枝，提高查詢效率.

4.2 K近鄰近似模式匹配查詢精細計算

在遍歷LR-Tree過程中得到EPSTDist>minValue的節(jié)點項，需要進行進一步的精細計算，判斷項所指向的時空標簽軌跡能否加入返回結果隊列Q中，具體步驟如算法2所示.

算法2.優(yōu)先隊列更新UpdateQ

輸入:節(jié)點項E

優(yōu)先隊列Q

查詢模式P

偏好系數α

查詢軌跡Qtraj

查詢結果個數k

輸出：更新entry后的優(yōu)先隊列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();//保持優(yōu)先隊列長度為k

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

11:ENDIF

12:ENDIF

13:ENDIF

14:RETURNQ

當優(yōu)先隊列Q未滿時將項所指向的時空標簽軌跡直接插入至優(yōu)先隊列中，而當|Q|=K時，需要進行進一步計算.由引理2可知對于葉節(jié)點項E及E指向的時空標簽軌跡，存在EPSTDist≥PSTDist，因此僅得到EPSTDist>minValue并不能判斷出時空標簽軌跡的模式匹配時空距離值大于閾值minValue，需要進行精細計算得到時空標簽軌跡的PSTDist，當PSTDist> minValue時，才將時空標簽軌跡加入Q中.

在精細計算PSTDist時，主要計算兩部分：

1)模式匹配度，模式匹配度通過軌跡最大匹配子模式MMS(traj，P)與給定查詢模式P的模式長度比值所得；

2)軌跡間距離值，首先計算時空標簽軌跡在給定時間區(qū)間與查詢軌跡定義時間區(qū)間交集I′內的軌跡插值，得到I′內的子軌跡段，利用子軌跡段與查詢軌跡進行軌跡間距離值計算.在得到1)2)后，根據模式匹配時空距離值定義計算得到PSTDist.遍歷LR-Tree后Q中所有軌跡即為K近鄰近似模式匹配查詢結果.

5 實驗與性能測試

5.1 對比實驗索引介紹

對比實驗實現語義索引RR-Tree及三種傳統(tǒng)移動對象索引3DR-Tree[10]、SETI[11]、TB-Tree[12].RR-Tree通過語義屬性及時空屬性進行剪枝， 3DR-Tree、SETI、TB-Tree通過時空屬性進行剪枝.

模式匹配查詢中需要對整條軌跡上的語義進行比較，而在網格索引結構中將軌跡劃分為不同的軌跡段，可能造成重復計算，因此將HAG中的網格結構替換為R樹索引結構.RR-Tree采用[13]中的思想，實現在R樹節(jié)點項中插入最大最小值的結構，并命名為RR-Tree.RR-Tree節(jié)點結構如圖3所示，N為RR-Tree的節(jié)點，N中包含若干節(jié)點項E，E中包含MBR和pointer/tid，與R-Tree定義相同，其中Min(Max)表示以該節(jié)點項為根節(jié)點的子樹中包含的最小(大)語義數值.

圖3 RR-Tree節(jié)點結構Fig.3 RR-Tree node structure

在RR-Tree中，每個語義標簽對應唯一的ID，節(jié)點項中Min(Max)代表所有子節(jié)點最小(大)ID.在查詢過程中，首先判斷查詢模式P中所有的語義標簽是否都出現在[Min，Max]范圍內，對于滿足條件的節(jié)點項再進一步根據結點項中的MBR與給定查詢時空條件計算來進行剪枝，3DR-Tree在時空上的計算與RR-Tree相同.

對于TB-Tree，以軌跡段MBR作為葉節(jié)點項的MBR構造TB-Tree，每個葉節(jié)點中只包含同一軌跡中的軌跡段，并有指針指向下一個包含同一軌跡的葉節(jié)點.對于TB-Tree節(jié)點項中MBR，若節(jié)點項與查詢時間區(qū)間不相交或節(jié)點項的MBR計算后與空間查詢條件不滿足，則將節(jié)點裁剪.當遍歷至葉節(jié)點處讀取完整軌跡，判斷是否模式匹配并進行進一步的軌跡時空距離計算.

對于SETI網格索引，將給定空間等分為大小相同的網格，在每個網格中建一維R樹索引軌跡段的時間屬性.在查詢過程中，首先判斷每個網格與查詢空間范圍關系是否滿足空間屬性要求，滿足則根據網格中的一維R-Tree判斷是否存在與查詢時間區(qū)間相交的項.將滿足時空屬性的項對應軌跡進行進一步的精細計算，判斷是否滿足查詢條件.

5.2 查詢性能測試

實驗使用真實數據集和合成數據集，兩種數據均表示語義屬性對應至時間區(qū)間上的時空軌跡.合成數據集為開源數據庫SECONDO[15]中模擬地鐵軌跡的數據Trains，其中包含562輛地鐵的運動軌跡，為每條軌跡貼上不同的合成標簽，其中標簽為1-50中的任意數字，每個數字表示不同的標簽，每種標簽出現的概率相同，每條軌跡包含5-10個標簽.采用數據加倍方法對軌跡進行空間x、y方向上的偏移，得到平移的軌跡數據.數據集信息如表1所示，Train(n)表示在Train的基礎上進行x、y方向上的平移得到的n平方倍數據.

表1 數據集數據統(tǒng)計Table 1 Data set statistics

真實數據集是微軟亞洲研究院Geolife[14]，項目組收集182個用戶3年內的GPS數據，其中部分用戶用交通方式標記了他們的運動數據(如步行、火車等)，表2記錄Geolife中出現的所有標簽，統(tǒng)計不同標簽出現次數.

表2 標簽頻數Table 2 Labelfrequency

表3 實驗參數Table 3 Experimental parameters

為驗證本章提出的基于LR-Tree的K近鄰近似模式匹配查詢算法的有效性，采用C++語言在Linux環(huán)境下擴展可擴充移動對象數據庫SECONDO，對LR-Tree、RR-Tree、3DR-Tree、SETI及TB-Tree索引結構進行實現，實驗環(huán)境為：Intel(R) Core(TM) I3-2120 CPU @3及SECONDO系統(tǒng)中合成地鐵軌跡數據集Train，本部分實驗參數設置如表3所示.

5.2.1 數據集對算法性能影響

本部分實驗以不同規(guī)模數據集為實驗數據，在查詢模式，偏好系數α、給定時間區(qū)間及返回結果數參數相同的情況下，對比五種不同的索引在不同的數據集下的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值對比，將不可能作為結果返回的節(jié)點進行剪枝，從而達到提高查詢效率的效果.

圖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%以上的查詢效率，顯著優(yōu)于基于RR-Tree、3DR-Tree、TB-Tree及SETI的查詢算法.

基于LR-Tree的K近鄰近似模式匹配算法中，對于出棧的非葉節(jié)點中所有滿足條件的節(jié)點項，按照節(jié)點項的項模式匹配時空距離EPSTDist排序后，將所指向的子節(jié)點依次入棧.本部分實驗對比排序及不排序的基于LR-Tree的K近鄰近似模式匹配算法在不同標簽數下的I/O次數及CPU時間，實驗結果如圖6所示.

由圖6可以看出基于LR-Tree的排序算法效果優(yōu)于不排序算法.因為排序后入棧能保證下一次出棧的節(jié)點是當前棧中EPSTDist值最大的節(jié)點，當EPSTDist值越大，以該節(jié)點為根節(jié)點的時空標簽軌跡中包含較大的模式匹配時空距離值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的節(jié)點項越少，包含語義屬性的索引LR-Tree中位圖剪枝效果越好.

圖7 查詢模式對算法性能影響Fig.7 Effect of query pattern

5.2.4 給定時間區(qū)間長度對算法性能影響

本部分實驗設置在其他查詢參數一定的情況下，對比不同時間區(qū)間長度對查詢算法影響，查詢時間區(qū)間的開始時刻設置為查詢軌跡的定義時間區(qū)間開始時刻，實驗結果如圖8所示.

圖8 給定時間區(qū)間長度對算法性能影響Fig.8 Effect of time interval

由圖8可以看出，隨著查詢時間區(qū)間長度增加，I/O次數及CPU時間增加并逐漸趨于穩(wěn)定.這是因為基于LR-Tree的K近鄰近似模式匹配算法的篩選過程中包含時間區(qū)間篩選，時間區(qū)間長度增加，定義時間區(qū)間與查詢時間區(qū)間相交的軌跡數量也增加，被裁剪的節(jié)點減少，導致I/O次數及CPU時間增加.而查詢軌跡的定義時間區(qū)間長度為3h-4h，在計算過程中查詢時間區(qū)間是由給定時間區(qū)間及查詢軌跡定義時間區(qū)間的交集所得，因此當給定時間區(qū)間長度大于查詢軌跡定義時間區(qū)間時，查詢時間區(qū)間即為查詢軌跡定義時間區(qū)間，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%.

圖10 偏好系數α對算法性能影響Fig.10 Effect of preference factor α

6 總 結

本文提出將軌跡的語義匹配程度和查詢距離在同一優(yōu)先級考慮的K近鄰近似模式匹配查詢，并引入新的裁剪策略，給出基于標簽R樹的查詢算法，通過在不同參數下與已有索引對比，驗證了提出算法的有效性.今后的工作可以將近似模式匹配查詢應用在多標簽的場景下，提出有效的索引機制以支持多標簽近似模式匹配查詢.