K近鄰近似模式匹配查詢

梁珺秀，許建秋，秦小麟

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

1 引 言

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

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

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

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

目前還未有針對上述查詢的研究成果發(fā)表，本文將這類查詢定義為K近鄰近似模式匹配查詢，查詢返回在給定時間區(qū)間內(nèi)，模式匹配時空距離值最大的前K條軌跡，即返回結(jié)果匹配給定查詢模式的同時能更接近查詢軌跡.

圖1 K近鄰近似模式匹配查詢Fig.1 K nearest neighbor approximate pattern match query

為解決K近鄰近似模式匹配查詢，本文主要貢獻(xiàn)如下：

1)給出近似模式匹配及相關(guān)定義；

2)提出基于標(biāo)簽R樹的K近鄰近似模式匹配查詢算法；

3)實現(xiàn)基于RR-Tree、3DR-Tree、TB-Tree和SETI的K近鄰近似模式匹配查詢算法，通過真實數(shù)據(jù)和合成數(shù)據(jù)，與基于標(biāo)簽R樹的算法進(jìn)行比較.

2 相關(guān)工作

目前針對具有語義的時空軌跡已有大量研究，主要包含活動軌跡[4]、語義軌跡[5]及符號軌跡[6].

活動軌跡[4]是由Zheng K等人提出的表示包含關(guān)于特定地點處的用戶活動信息的新類型的軌跡數(shù)據(jù)，活動軌跡由點序列構(gòu)成，每個點處包含時空屬性和活動屬性，時空屬性即為時間點及對應(yīng)的空間位置，活動屬性由零個或多個活動所組成.在[4]中提出了ATSQ(Activity Trajectory Similarity Query)查詢，查詢結(jié)果返回覆蓋查詢活動且產(chǎn)生最短最小匹配距離的前K條軌跡，而查詢OATSQ(Order-Sensitive Activity Trajectory Similarity Query)中考慮提出的活動是有順序的，即返回的軌跡需匹配給定活動順序.在[7]中提出了基于等級的活動軌跡搜索RTS(Ranking Based Activity Trajectory Search)，查詢輸入為一組活動和距離閾值，查詢返回在距離閾值內(nèi)包含所有查詢活動，且排名最高前K條軌跡，基于順序的活動軌跡搜索ORTS (Order-Sensitive Ranking Based Activity Trajectory Search)查詢將活動順序考慮在內(nèi).

語義軌跡是由 Alvares LO等人在[5]中提出用注釋標(biāo)記整個軌跡或其部分軌跡段，每個注釋表示在其對應(yīng)點處用戶的狀態(tài)或行為，用這些狀態(tài)或行為來豐富幾何軌跡.在文獻(xiàn)[8]中，提出語義軌跡的模糊關(guān)鍵字查詢，用戶給出查詢關(guān)鍵字，綜合考慮語義軌跡與查詢關(guān)鍵字的編輯距離和經(jīng)過給定關(guān)鍵字的軌跡長度，返回代價最小的前K條軌跡.

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

3 問題描述

3.1 問題定義

定義1.時空標(biāo)簽軌跡：時空標(biāo)簽軌跡可表示為

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

其中任意[Ij，lj，loc1j，loc2j]表示第j個時空標(biāo)簽軌跡單元；其中Ij表示第j個單元對應(yīng)的時間區(qū)間，lj表示單元j對應(yīng)的標(biāo)簽；loc11表示時間區(qū)間Ij開始時刻Inss對應(yīng)的地理位置，loc2j表示時間區(qū)間Ij結(jié)束時刻Inse對應(yīng)的地理位置.

定義2.模式：P=，其中pi為以下兩種形式之一：

1)pi為標(biāo)簽，表示不同的語義標(biāo)簽，稱這種為單元模式.

2)pi為*，+，[p]，[pi | pj]，[p]+，[p]*，或[p]?，稱這種為簡單模式，簡單模式中的p為單元模式或簡單模式，簡單模式中*表示存在0或0個以上的簡單模式，+表示存在至少一個簡單模式，|表示兩個簡單模式中僅存在其中一個，?表示前面修飾的簡單模式最多只出現(xiàn)一次.

由定義可知當(dāng)traj中存在軌跡段的標(biāo)簽信息，與P中標(biāo)簽的內(nèi)容相同且順序一致時，稱軌跡與P模式匹配.模式匹配查詢存在以下特點：

1) 模式匹配能處理較復(fù)雜的語義屬性查詢請求；

2)將模式匹配與時空屬性查詢相結(jié)合，能解決不同維度的查詢.

定義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′中存在一個或一個以上的語義標(biāo)簽.

定義5.模式長度(Pattern length，PLen(P))：對模式P=，模式中所有單元模式和非通配符簡單模式的個數(shù)即為當(dāng)前模式P的模式長度.

在引言給出的語義模式中，查詢模式可以表示為P = <(小小世界)，*，(畫廊)，(加勒比海盜)，*，(星際歷險)，+，(歌舞基地)>，對于該模式的模式長度為5.

定義6.最大匹配子模式(Maximum Matching Subpattern，MMS(traj，P))：對于模式P=及給定軌跡traj，S為traj匹配的所有子模式的集合，最大匹配子模式返回P′∈S，對?P*∈S，有PLen(P′)≥PLen(P*)，則P′為traj對應(yīng)于P的最大匹配子模式.

定義7.模式匹配度(Degree of Pattern Match，DPM(traj，P))：對于模式P=及給定軌跡traj，模式匹配度為最大匹配子模式長度與模式P長度的比值，表示為：

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

由上述公式計算可得軌跡與給定查詢模式的匹配程度，得到的值為(0，1]區(qū)間內(nèi)，注意值域左邊為開區(qū)間，表示模式匹配度值域不包含0.根據(jù)近似模式匹配定義，子模式中至少包含一個或一個以上的語義標(biāo)簽信息，因此DPM(traj，P)>0必然成立.

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

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

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

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

定義10.K近鄰近似模式匹配查詢(K Nearest Neighbor Approximate Pattern Match Query，KAPMQ)：給定時間區(qū)間I，查詢軌跡Qtraj，查詢模式P，及模式匹配程度系數(shù)α，其中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 標(biāo)簽R樹

標(biāo)簽R樹LR-Tree(Label R-Tree)，形式上由一個 3DR-Tree[10]和一個標(biāo)簽表組成，標(biāo)簽表中不重復(fù)的保存時空標(biāo)簽軌跡數(shù)據(jù)集中出現(xiàn)的所有標(biāo)簽，而空間位圖層與3DR-Tree不同的是：

1) 每個節(jié)點的項(entry)中增加一個預(yù)設(shè)定長度的位圖，樹中所有節(jié)點項中位圖長度相同，位圖由一串”0/1”組成，“0/1”代表了當(dāng)前項指向的子節(jié)點的標(biāo)簽存在性，當(dāng)位為1時，表示位對應(yīng)至標(biāo)簽表中的標(biāo)簽存在，為0則不存在；

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

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

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

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

定義11.項模式匹配度(Degree of Pattern Match in Entry，DPME(E，P))：給定模式P=及節(jié)點項E，對于查詢模式P的位圖Tbit中為1的每一位，統(tǒng)計項位圖Ebit對應(yīng)位為1的個數(shù)記為Enum，與P的模式長度PLen(P)的比值稱為項模式匹配度，表示為：

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

定義12.項模式匹配時空距離(Entry Pattern Match Spatio-Temporal Distance，EPSTDist(E，QBox，α))：給定項E，查詢軌跡矩形框QBox，及模式匹配程度系數(shù)α，其中0≤α<1，項E的模式匹配時空距離表示為：

EPSTDist(E，QBox，α)=

在近似模式匹配查詢中返回的是模式匹配時空距離最大的前K個，因此不能僅根據(jù)矩形框間距離值進(jìn)行剪枝，需要同時考慮匹配程度.基于LR-Tree的K近鄰近似模式匹配查詢算法如算法1所示，主要包括以下步驟：

算法1.K近鄰近似模式匹配查詢

輸入：查詢模式P

查詢時間區(qū)間1

查詢軌跡Qtraj

查詢結(jié)果個數(shù)k

移動對象集合D

偏好系數(shù)α

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

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

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

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

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

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

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

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

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

圖2 邊框矩形與軌跡關(guān)系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的個數(shù)必定大于等于E2中1的個數(shù)，則DPME(E1，P)≥DPME(E2，P).

由定義可知，EPSTDist值與DPME呈正相關(guān)，與Dist呈負(fù)相關(guān)，綜合(1)(2)可知

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

引理1得證.

引理2.葉節(jié)點項的項模式匹配時空距離大于等于項所指向的時空標(biāo)簽軌跡的模式匹配距離.

證明：對于葉節(jié)點項E及其指向的時空標(biāo)簽軌跡traj，由圖2可以看出查詢軌跡Qtraj的邊框矩形QBox與E的邊框矩形BBox2的距離值dis2小于等于Qtraj與traj兩條軌跡本身間的距離值dis3，即Dist(BBox2，QBox)≤Dist(traj，Qtraj).

而從項中位圖考慮，在位圖中僅考慮查詢模式中標(biāo)簽的存在性，而對于時空標(biāo)簽軌跡，還需進(jìn)一步考慮語義標(biāo)簽的順序是否匹配，因此最大匹配子模式PLen(MMS(traj，P))≤Enum，根據(jù)模式匹配度定義，可得DPM(traj，P)≤DPME(E，P).

由項模式匹配時空距離及模式匹配時空距離定義可知

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

引理2得證.

K近鄰近似模式匹配中需要綜合考慮距離值及模式匹配程度兩方面，因此在訪問LR-Tree的內(nèi)部節(jié)點時，無法僅根據(jù)空間距離值來進(jìn)行剪枝，而空間剪枝在提高查詢效率的過程中占很重要的作用，因此需要考慮引入新屬性對節(jié)點進(jìn)行剪枝.由于項中保存了表示標(biāo)簽存在性的位圖及最小邊框矩形MBR，分別對應(yīng)至語義及時空兩種屬性，因此考慮利用位圖和MBR計算出項模式匹配時空距離值EPSTDist，將EPSTDist的值與優(yōu)先隊列Q中的最小模式匹配時空距離值minValue比較，由引理1及引理2可知，當(dāng)節(jié)點項的EPSTDist小于等于minValue時，節(jié)點項所指向的子節(jié)點的EPSTDist或時空標(biāo)簽軌跡的PSTDist均小于當(dāng)前節(jié)點的EPSTDist，因此不可能作為結(jié)果返回，可以將以當(dāng)前項所指向的節(jié)點為根節(jié)點的子樹裁剪.

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

4.2 K近鄰近似模式匹配查詢精細(xì)計算

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

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

輸入:節(jié)點項E

優(yōu)先隊列Q

查詢模式P

偏好系數(shù)α

查詢軌跡Qtraj

查詢結(jié)果個數(shù)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

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

在精細(xì)計算PSTDist時，主要計算兩部分：

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

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

5 實驗與性能測試

5.1 對比實驗索引介紹

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

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

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

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

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

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

5.2 查詢性能測試

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

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

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

表2 標(biāo)簽頻數(shù)Table 2 Labelfrequency

表3 實驗參數(shù)Table 3 Experimental parameters

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

5.2.1 數(shù)據(jù)集對算法性能影響

本部分實驗以不同規(guī)模數(shù)據(jù)集為實驗數(shù)據(jù)，在查詢模式，偏好系數(shù)α、給定時間區(qū)間及返回結(jié)果數(shù)參數(shù)相同的情況下，對比五種不同的索引在不同的數(shù)據(jù)集下的I/O次數(shù)和CPU時間，實驗結(jié)果如圖4所示，隨著數(shù)據(jù)集大小增加，I/O次數(shù)及CPU時間也呈迅速增長趨勢，由低到高依次是LR-Tree、RR-Tree、3DR-Tree、TB-Tree及SETI.相較于包含語義信息的RR-Tree索引，基于LR-Tree的K近鄰近似模式匹配查詢算法降低了約60%的I/O次數(shù)及CPU時間.這是由于基于LR-Tree的查詢算法在查詢過程中能更好的利用項模式匹配時空距離和Q中minValue值對比，將不可能作為結(jié)果返回的節(jié)點進(jìn)行剪枝，從而達(dá)到提高查詢效率的效果.

圖4 數(shù)據(jù)集對算法性能影響Fig.4 Effect of dataset amount

5.2.2 查詢標(biāo)簽數(shù)量對算法性能影響

本部分實驗考慮相同條件下標(biāo)簽數(shù)量對查詢算法效率的影響，其中標(biāo)簽數(shù)量表示查詢模式中單元模式及除通配符外簡單模式的個數(shù).

圖5 標(biāo)簽數(shù)對算法性能影響Fig.5 Effect of label number

如圖5所示，隨著標(biāo)簽數(shù)增加，I/O次數(shù)和CPU時間也增加，這是因為隨著標(biāo)簽數(shù)增加，大程度匹配給定查詢模式的軌跡減少，因此Q中minValue的值降低，導(dǎo)致LR-Tree的剪枝效果降低，進(jìn)而使得I/O次數(shù)及CPU時間增加.當(dāng)標(biāo)簽數(shù)大于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近鄰近似模式匹配算法在不同標(biāo)簽數(shù)下的I/O次數(shù)及CPU時間，實驗結(jié)果如圖6所示.

由圖6可以看出基于LR-Tree的排序算法效果優(yōu)于不排序算法.因為排序后入棧能保證下一次出棧的節(jié)點是當(dāng)前棧中EPSTDist值最大的節(jié)點，當(dāng)EPSTDist值越大，以該節(jié)點為根節(jié)點的時空標(biāo)簽軌跡中包含較大的模式匹配時空距離值PSTDist值的可能性越大.因此能盡早將隊列Q填滿，更有效的利用Q中的minValue值進(jìn)行剪枝.因此相較于不排序算法，排序算法能更有效的提高約30%查詢效率.

圖6 排序算法影響Fig.6 Algorithm withor without sort

5.2.3 查詢模式對算法性能影響

本部分實驗以GeoLife為實驗數(shù)據(jù)，比較在真實數(shù)據(jù)下不同出現(xiàn)頻率的標(biāo)簽對K近鄰近似模式匹配查詢算法的影響.在查詢模式中只包含其中一個標(biāo)簽，GeoLife中標(biāo)簽出現(xiàn)頻率如表2所示，結(jié)合圖7可以看出，相較于不包含語義的索引，標(biāo)簽出現(xiàn)頻率越小，如airplane、train等，基于LR-Tree的查詢算法的I/O次數(shù)和CPU時間減少約40%以上.在篩選過程中包含位圖篩選，由于標(biāo)簽出現(xiàn)頻率越低，對應(yīng)位圖中位為1的節(jié)點項越少，包含語義屬性的索引LR-Tree中位圖剪枝效果越好.

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

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

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

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

由圖8可以看出，隨著查詢時間區(qū)間長度增加，I/O次數(shù)及CPU時間增加并逐漸趨于穩(wěn)定.這是因為基于LR-Tree的K近鄰近似模式匹配算法的篩選過程中包含時間區(qū)間篩選，時間區(qū)間長度增加，定義時間區(qū)間與查詢時間區(qū)間相交的軌跡數(shù)量也增加，被裁剪的節(jié)點減少，導(dǎo)致I/O次數(shù)及CPU時間增加.而查詢軌跡的定義時間區(qū)間長度為3h-4h，在計算過程中查詢時間區(qū)間是由給定時間區(qū)間及查詢軌跡定義時間區(qū)間的交集所得，因此當(dāng)給定時間區(qū)間長度大于查詢軌跡定義時間區(qū)間時，查詢時間區(qū)間即為查詢軌跡定義時間區(qū)間，I/O次數(shù)及CPU時間保持不變.相較于RR-Tree查詢效率降低了40%-50%.

5.2.5 返回結(jié)果數(shù)對算法性能影響

本部分實驗對比不同返回結(jié)果數(shù)K對K近鄰近似模式匹配查詢算法的影響.由圖9可以看出，隨著返回結(jié)果數(shù)增加，I/O次數(shù)及CPU時間也呈增加趨勢.這是因為在遍歷LR-Tree過程中，需要利用Q中最小模式匹配時空距離值minValue進(jìn)行剪枝，當(dāng)返回結(jié)果數(shù)K越大，隊列Q長度越大，導(dǎo)致minValue值越小，在篩選過程中利用minValue剪枝的效果降低，導(dǎo)致I/O次數(shù)及CPU時間增加.而從圖10可以看出，由于K數(shù)值增大，空間剪枝能力大幅降低，基于LR-Tree的查詢算法相較于同樣能表示語義信息的RR-Tree的查詢算法效率降低約60%-70%，表現(xiàn)出更好的剪枝效果.

圖9 返回結(jié)果數(shù)K對算法性能影響Fig.9 Effect of resultnumber

5.2.6 偏好系數(shù)α對算法性能影響

在其它查詢參數(shù)相同的情況下，本部分實驗對比不同偏好系數(shù)α對K近鄰近似模式匹配查詢結(jié)果的影響.實驗結(jié)果如圖10所示，可以看出，隨著偏好系數(shù)α增加，I/O次數(shù)及CPU時間增大.這是因為α是模式匹配程度的偏好系數(shù)，α值越小，查詢越接近于不包含語義屬性的K近鄰查詢，根據(jù)時空屬性能進(jìn)行很好的裁剪，因此五種索引剪枝效果較好，而當(dāng)α值越大，時空屬性占比減小，導(dǎo)致時空剪枝能力降低，時空索引I/O次數(shù)及CPU時間顯著增加.在K近鄰近似模式匹配查詢中，基于LR-Tree的時空屬性剪枝效果比語義剪枝效果好，因此當(dāng)偏好系數(shù)增加時，I/O次數(shù)及CPU時間增加.相較于能表示語義的RR-Tree，基于LR-Tree的K近鄰近似模式匹配查詢算法在不同偏好系數(shù)下查詢效率提高了約70%.

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

6 總 結(jié)

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