梁珺秀，許建秋，秦小麟

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

1 引 言

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

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

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

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

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

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

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

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

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

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

2 相關(guān)工作

目前針對(duì)具有語義的時(shí)空軌跡已有大量研究，主要包含活動(dòng)軌跡[4]、語義軌跡[5]及符號(hào)軌跡[6].

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

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

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

3 問題描述

3.1 問題定義

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

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

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

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

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

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

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

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

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

定義4.近似模式匹配(Approximate Pattern Match，APmatch(traj，P))：對(duì)于模式P=及軌跡traj，若存在P中子模式P′=，其中1≤i≤j≤n，P′中包含單元模式或所有的簡單模式p不全為*，+等通配符，使得traj匹配模式<*，P′，*>，則稱traj近似模式匹配P.

由定義可知，traj近似模式匹配P表示P中存在子模式P′，使得traj模式匹配<*，P′，*>，且子模式P′中包含單元模式或所有的簡單模式不全為模式定義中給出的通配符，即子模式P′中存在一個(gè)或一個(gè)以上的語義標(biāo)簽.

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

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

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

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

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

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

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

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

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

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

定義10.K近鄰近似模式匹配查詢(K Nearest Neighbor Approximate Pattern Match Query，KAPMQ)：給定時(shí)間區(qū)間I，查詢軌跡Qtraj，查詢模式P，及模式匹配程度系數(shù)α，其中0≤α<1，返回軌跡集合D中大小為k的子集D′：

1) 對(duì)?traj∈D′，Interpolate(I∩Qtraj.interval，traj)≠φ；

2) 對(duì)?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)，形式上由一個(gè) 3DR-Tree[10]和一個(gè)標(biāo)簽表組成，標(biāo)簽表中不重復(fù)的保存時(shí)空標(biāo)簽軌跡數(shù)據(jù)集中出現(xiàn)的所有標(biāo)簽，而空間位圖層與3DR-Tree不同的是：

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

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

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

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

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

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

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

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

EPSTDist(E，QBox，α)=

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

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

輸入：查詢模式P

查詢時(shí)間區(qū)間1

查詢軌跡Qtraj

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

移動(dòng)對(duì)象集合D

偏好系數(shù)α

LR-Tree

輸出：優(yōu)先隊(duì)列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é)點(diǎn))

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é)點(diǎn))

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

18:ENDIF

19:ENDIF

20:ENDFOR

21:IF(L≠φ)

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

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

24:ENDIF

25:ENDWHILE

26:RETURNQ

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

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

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

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

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

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

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

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

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

圖2 邊框矩形與軌跡關(guān)系Fig.2 MBR and trajectory

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

證明：由項(xiàng)模式匹配時(shí)空距離值定義，

EPSTDist(E，QBox，α)

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

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

2)而由LR-Tree定義可知，上層節(jié)點(diǎn)項(xiàng)E1中位圖BSet1由所指向的下層節(jié)點(diǎn)中所有項(xiàng)執(zhí)行按位或操作所得，因此E2位圖BSet2中為1的位在E1位圖中也必定為1，且E1中位為1的個(gè)數(shù)必定大于等于E2中1的個(gè)數(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é)點(diǎn)項(xiàng)的項(xiàng)模式匹配時(shí)空距離大于等于項(xiàng)所指向的時(shí)空標(biāo)簽軌跡的模式匹配距離.

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

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

由項(xiàng)模式匹配時(shí)空距離及模式匹配時(shí)空距離定義可知

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

引理2得證.

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

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

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

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

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

輸入:節(jié)點(diǎn)項(xiàng)E

優(yōu)先隊(duì)列Q

查詢模式P

偏好系數(shù)α

查詢軌跡Qtraj

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

輸出：更新entry后的優(yōu)先隊(duì)列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指向移動(dòng)對(duì)象；

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

8: Q.insert(entry.tid);

9: Q.pop();//保持優(yōu)先隊(duì)列長度為k

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

11:ENDIF

12:ENDIF

13:ENDIF

14:RETURNQ

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

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

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

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

5 實(shí)驗(yàn)與性能測(cè)試

5.1 對(duì)比實(shí)驗(yàn)索引介紹

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

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

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

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

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

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

5.2 查詢性能測(cè)試

實(shí)驗(yàn)使用真實(shí)數(shù)據(jù)集和合成數(shù)據(jù)集，兩種數(shù)據(jù)均表示語義屬性對(duì)應(yīng)至?xí)r間區(qū)間上的時(shí)空軌跡.合成數(shù)據(jù)集為開源數(shù)據(jù)庫SECONDO[15]中模擬地鐵軌跡的數(shù)據(jù)Trains，其中包含562輛地鐵的運(yùn)動(dòng)軌跡，為每條軌跡貼上不同的合成標(biāo)簽，其中標(biāo)簽為1-50中的任意數(shù)字，每個(gè)數(shù)字表示不同的標(biāo)簽，每種標(biāo)簽出現(xiàn)的概率相同，每條軌跡包含5-10個(gè)標(biāo)簽.采用數(shù)據(jù)加倍方法對(duì)軌跡進(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)計(jì)Table 1 Data set statistics

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

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

表3 實(shí)驗(yàn)參數(shù)Table 3 Experimental parameters

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

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

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

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

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

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

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

如圖5所示，隨著標(biāo)簽數(shù)增加，I/O次數(shù)和CPU時(shí)間也增加，這是因?yàn)殡S著標(biāo)簽數(shù)增加，大程度匹配給定查詢模式的軌跡減少，因此Q中minValue的值降低，導(dǎo)致LR-Tree的剪枝效果降低，進(jìn)而使得I/O次數(shù)及CPU時(shí)間增加.當(dāng)標(biāo)簽數(shù)大于3時(shí)，另四種索引的空間剪枝能力大幅降低，基于LR-Tree的K近鄰近似模式匹配查詢算法提高了約90%以上的查詢效率，顯著優(yōu)于基于RR-Tree、3DR-Tree、TB-Tree及SETI的查詢算法.

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

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

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

5.2.3 查詢模式對(duì)算法性能影響

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

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

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

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

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

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

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

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

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

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

在其它查詢參數(shù)相同的情況下，本部分實(shí)驗(yàn)對(duì)比不同偏好系數(shù)α對(duì)K近鄰近似模式匹配查詢結(jié)果的影響.實(shí)驗(yàn)結(jié)果如圖10所示，可以看出，隨著偏好系數(shù)α增加，I/O次數(shù)及CPU時(shí)間增大.這是因?yàn)棣潦悄Ｊ狡ヅ涑潭鹊钠孟禂?shù)，α值越小，查詢?cè)浇咏诓话Z義屬性的K近鄰查詢，根據(jù)時(shí)空屬性能進(jìn)行很好的裁剪，因此五種索引剪枝效果較好，而當(dāng)α值越大，時(shí)空屬性占比減小，導(dǎo)致時(shí)空剪枝能力降低，時(shí)空索引I/O次數(shù)及CPU時(shí)間顯著增加.在K近鄰近似模式匹配查詢中，基于LR-Tree的時(shí)空屬性剪枝效果比語義剪枝效果好，因此當(dāng)偏好系數(shù)增加時(shí)，I/O次數(shù)及CPU時(shí)間增加.相較于能表示語義的RR-Tree，基于LR-Tree的K近鄰近似模式匹配查詢算法在不同偏好系數(shù)下查詢效率提高了約70%.

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

6 總 結(jié)

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