梁珺秀,許建秋

(南京航空航天大學計算機科學與技術學院,江蘇 南京 210016)

0 引 言

隨著無線通信技術和智能終端的迅速發(fā)展，每天產生大量移動對象數(shù)據，并同時與空間環(huán)境和運動模式等相關聯(lián)。移動對象查詢不再僅限于時空屬性，更擴展至與時空屬性相關的語義屬性上。有效地組織管理移動對象，分析移動對象的運動，可用于大量位置服務應用(Location Based Service，LBS)[1]。

現(xiàn)有的語義相關查詢或是僅要求覆蓋給定查詢語義[2]，或是語義屬性滿足簡單順序即可[3]，或是不考慮軌跡間的距離進行計算，這種對軌跡的分析模式很大程度地忽略了軌跡中的有效信息。因此需要提出一種同時包含復雜語義屬性和時空屬性的查詢，來解決日益復雜的用戶查詢要求。

在某些情況下，用戶可能只對某一特定區(qū)域軌跡的語義感興趣，如分析用戶在超市中包含語義的時空軌跡，返回在早上8:00至10:00時間區(qū)間內經過水果區(qū)或蔬菜區(qū)及日用品區(qū)的軌跡。通常在該時間段內經過這些地方購買的多為家庭主婦，因此可為返回軌跡結果對應的移動對象推送商品優(yōu)惠、限時蔬菜打折之類的消息?？紤]在特定范圍內的模式匹配查詢可以更有針對性地制定合適的方案。本文主要工作如下：

1)結合傳統(tǒng)移動對象查詢及模式匹配查詢，提出范圍模式匹配查詢。

2)給出基于標簽R樹的范圍模式匹配查詢算法。

3)通過合成數(shù)據及真實數(shù)據，與已有索引對比，驗證查詢算法的有效性。

1 相關工作

常見移動對象查詢包括范圍查詢[4]、K近鄰查詢[5]及相似軌跡查詢[6]等。范圍查詢返回在給定時空范圍內的所有移動對象，K近鄰查詢返回距離給定查詢對象最近的前K條軌跡，相似軌跡查詢給定相似性度量的距離函數(shù)判斷軌跡間的相似性。而軌跡中語義屬性的出現(xiàn)，使得用戶查詢在傳統(tǒng)查詢基礎上添加語義查詢請求。

文獻[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個單元對應的時間區(qū)間，lj表示單元j對應的標簽，loc1j表示開始時刻的地理位置，loc2j表示結束時刻的地理位置。

定義2模式：P=〈p1, …, pn〉，其中pi為以下2種形式之一：

1)pi為標簽，表示不同的語義標簽，稱為單元模式。

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

定義3模式匹配(Pattern Match，Pmatch(traj,P))：對于給定模式P，當且僅當時空標簽軌跡traj中存在軌跡段的標簽信息，與P中標簽的內容相同且順序一致時，即traj軌跡段中的標簽順序匹配P所表示的正則表達式，則稱軌跡與P模式匹配。

定義4軌跡插值(Interpolate(R,I,traj))：給定區(qū)域R，時間區(qū)間I，Interpolate(R,I,traj)返回軌跡traj在時間區(qū)間I及范圍R內的子軌跡段。

定義5范圍模式匹配查詢(Range Pattern Match Query,RPMQ)：給定空間區(qū)域R，時間區(qū)間I以及模式P=，返回軌跡集合D′∈D：

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

如圖1所示，給定查詢模式P=，該查詢模式表示查詢從p1出發(fā)，中間經過一個或一個以上的地點，然后返回p1并經過p2的軌跡。圖1中虛線框表示時空范圍的限制，因此對于4條軌跡，先得到滿足時空限制條件的子軌跡段traj′，在圖1中用實線表示traj′，虛線表示查詢時空范圍外的部分。對于traj1，軌跡語義p1段部分在框內，因此滿足P中的由p1出發(fā)的請求，后經過，滿足查詢模式的中間部分，因此traj1可以作為查詢結果返回；對于traj2，雖然滿足P，但軌跡最后一段完全不在虛線框內，因此子軌跡中只包含部分，不匹配模式P，而traj3和traj4不匹配給定模式，因此最后將traj1作為范圍模式匹配查詢結果返回。

圖1 范圍模式匹配查詢

2.2 標簽R樹

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

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

2)位圖的每位通過哈希函數(shù)對應到標簽表中的一個或多個位置，其中標簽表的每行保存不同標簽。

葉節(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為所指向的時空標簽軌跡包含的所有標簽到標簽表的映射計算所得的位圖。

定義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中所有出現(xiàn)的標簽與LR-Tree中標簽表對應所得。

3 范圍模式匹配查詢

范圍模式匹配查詢返回在給定的時間空間范圍內，子軌跡段匹配給定模式的所有軌跡。利用LR-Tree處理范圍模式匹配查詢，分為篩選和精細計算2步，首先遍歷LR-Tree，找到樹中與給定查詢模式P位圖匹配且與查詢時空范圍對應矩形框相交的所有葉節(jié)點項，然后對得到的葉節(jié)點項所指向的時空標簽軌跡進行精細計算，判斷時空范圍內的子軌跡段是否匹配給定模式，將模式匹配的所有軌跡作為查詢結果返回。基于LR-Tree的范圍模式匹配查詢如算法1及算法2(見3.2節(jié))所示。算法1主要步驟如下：

算法1 篩選過程

輸入：查詢模式P；查詢時間區(qū)間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為葉節(jié)點項)

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

采用深度優(yōu)先方法遍歷LR-Tree，設置棧S、保存LR-Tree篩選結果的隊列Q及最終查詢結果的隊列Res，首先將LR-Tree根節(jié)點入棧：

1)對于每個出棧節(jié)點，依次判斷節(jié)點中項是否與給定模式P位圖匹配，對于匹配的位圖，進一步判斷節(jié)點項對應的最小邊框矩形MBR是否與給定查詢范圍R的邊框矩形相交，對于不相交的矩形框，將以該節(jié)點項指向的節(jié)點為根節(jié)點的子樹從樹中裁剪，對滿足前2個條件的項判斷是否與給定查詢時間區(qū)間相交，將滿足3個條件的節(jié)點項進行下一步。

2)對于滿足前2個條件的節(jié)點項，若當前節(jié)點為非葉節(jié)點，則將節(jié)點項所指向的子節(jié)點入棧S；若當前節(jié)點為葉節(jié)點，則將葉節(jié)點項保存入隊列Q中。

3)在遍歷LR-Tree后，對于Q中所有葉節(jié)點項，將其所指向的時空標簽軌跡取出，判斷軌跡是否存在與給定時空范圍相交的子軌跡段，對于非空子軌跡段再進一步判斷是否匹配給定查詢模式，將子軌跡段匹配模式的軌跡加入返回結果集合Res中。

最終集合Res中保存的所有軌跡，即為范圍模式匹配查詢的查詢結果。

3.1 范圍模式匹配查詢篩選

算法1所示為范圍模式匹配查詢中的篩選過程算法，篩選過程由3個部分組成：1)節(jié)點項是否與給定模式P位圖匹配；2)項中MBR在空間上的投影是否與給定查詢范圍R的矩形框相交；3)項中MBR在時間區(qū)間上的投影是否與給定查詢時間區(qū)間I相交。

對于第1個部分，項中位圖由項所指向的子節(jié)點中所有節(jié)點項位圖按位或操作所得，若當前節(jié)點項位圖某位為0，則表示以其子節(jié)點為根節(jié)點的所有節(jié)點項中位圖對應的位均為0；若節(jié)點項與查詢模式位圖Tbit不與位圖匹配，即在Tbit為1的所有位上，節(jié)點項位圖中存在一個或一個以上的位不為1，則當前節(jié)點的所有子孫節(jié)點均不可能存在對應位為1的項。因此不匹配的節(jié)點項所指向的時空標簽軌跡不包含查詢模式中的所有標簽，不可能完全匹配給定查詢模式，則可以將這部分節(jié)點剪枝而不需要進一步的計算。

對于第2個和第3個部分，根據范圍模式匹配查詢定義，返回在給定時空范圍內匹配模式的軌跡，因此返回結果中的軌跡必然與給定查詢時空范圍相交。對于空間范圍R，LR-Tree中非葉節(jié)點項的MBR是將所有子節(jié)點項包圍的最小邊框矩形，因此若MBR與給定R不存在相交部分，則該子節(jié)點與R也不可能存在相交部分，因此可以作為篩選條件；而對于時間范圍I，根據定義，若節(jié)點項的定義時間區(qū)間與I不存在交集，也必然不會出現(xiàn)在返回結果中。

根據上述3個部分篩選條件，可以在訪問LR-Tree的節(jié)點時，篩選出所有不可能作為結果返回的軌跡，大量減少進一步的計算，從而降低磁盤I/O和CPU計算時間。

3.2 范圍模式匹配查詢精細計算

對于經過篩選過程后保留在隊列Q中的所有項，需要進行進一步的精細計算來判斷項所指向的時空標簽軌跡是否滿足給定查詢條件。算法2為范圍模式匹配查詢精細計算過程，精細計算過程主要分2步：1)判斷當前項所指向的軌跡與給定時空查詢范圍的交集是否為空；2)判斷查詢范圍內的子軌跡段與給定模式是否匹配。對于滿足上述2個條件的軌跡則作為結果加入Res中，最終保存在Res中的所有軌跡即為范圍模式匹配查詢結果。

范圍模式匹配查詢返回與給定時空范圍相交的軌跡，因此對于Q中葉節(jié)點項指向的每條軌跡，首先考慮與查詢時空范圍是否相交。在篩選過程后得到的所有軌跡與查詢時間區(qū)間必然存在交集，而對于空間屬性來說，篩去的是軌跡的MBR在空間上的投影與查詢范圍不相交的軌跡，軌跡本身與查詢范圍是否相交需要進行進一步的計算。

算法2 精細計算

輸入：查詢模式P；查詢時間區(qū)間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，再與查詢時間區(qū)間計算，得到查詢時間區(qū)間內的子軌跡段subtraj′，即為給定時空范圍內的子軌跡段。根據范圍模式匹配定義，在得到子軌跡段subtraj′后，只需要考慮子軌跡段的模式匹配，判斷subtraj′是否與給定查詢模式P模式匹配，將匹配的子軌跡對應的時空標簽軌跡加入到返回結果集合Res中，最終Res中得到的所有軌跡即為范圍模式匹配查詢的結果。

圖2 軌跡投影

4 實驗性能與測試

表1 數(shù)據集的數(shù)據統(tǒng)計

實驗使用真實數(shù)據集和合成數(shù)據集，如表1所示。真實數(shù)據集是微軟亞洲研究院GeoLife[14]的項目組收集182個用戶3年內的GPS數(shù)據，其中部分用戶用交通方式標記了他們的運動數(shù)據(如步行、火車等)，合成數(shù)據集是SECONDO系統(tǒng)中人工合成地鐵軌跡數(shù)據的Trains。

表2記錄了GeoLife中出現(xiàn)的所有標簽及不同標簽出現(xiàn)的次數(shù)。

表2 標簽頻數(shù)

4.1 對比索引介紹

RR-Tree采用文獻[15]中的思想，將HAG索引的網格結構替換為R樹索引結構，實現(xiàn)在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é)點的子樹中包含的最小(大)語義數(shù)值。在查詢過程中，首先判斷查詢模式P中所有的語義標簽是否都出現(xiàn)在[Min,Max]范圍內，對于滿足條件的節(jié)點項進一步根據節(jié)點項中的MBR與給定查詢時空條件計算來進行剪枝，3DR-Tree[13]在時空上的計算與RR-Tree相同。

圖3 RR-Tree節(jié)點結構

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

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

4.2 范圍模式匹配查詢性能測試

為了驗證本文提出的基于LR-Tree范圍模式匹配查詢算法的有效性，采用C++語言在Linux環(huán)境下擴展可擴充移動對象數(shù)據庫SECONDO，對LR-Tree、RR-Tree、3DR-Tree、SETI及TB-Tree索引結構進行實現(xiàn)，實驗環(huán)境為：Intel(R) Core(TM) I3-2120 CPU@3.30 GHz，4 GB內存，Ubuntu14.04 64 bit操作系統(tǒng)，本部分實驗參數(shù)設置如表3所示。

表3 范圍模式匹配查詢實驗參數(shù)

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

本節(jié)實驗以不同數(shù)據集為實驗數(shù)據，比較5種索引在相同的查詢條件下，在不同數(shù)量級的數(shù)據集上的性能，得到的結果如圖4所示?？梢钥闯鲭S著數(shù)據量增長，5種索引的I/O次數(shù)及CPU時間均呈增長趨勢，由低到高依次為LR-Tree、RR-Tree、3DR-Tree、TB-Tree及SETI，相較于另外4種索引，LR-Tree增長更為緩慢，體現(xiàn)了LR-Tree高效的剪枝性能。

(a) CPU時間比較

(b) I/O次數(shù)比較圖4 數(shù)據集對算法性能影響

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

本部分實驗以GeoLife真實數(shù)據作為實驗數(shù)據，對GeoLife中出現(xiàn)的8種標簽，在相同的查詢條件下設置僅含一個標簽的不同查詢模式，實驗得到的結果如圖5所示。對比表3中標簽出現(xiàn)次數(shù)，可以看出相較于另外4種索引，對于出現(xiàn)頻率較低的標簽，如airplane和train，由于在LR-Tree節(jié)點項位圖中對應位為1的節(jié)點少，因此能更好地利用節(jié)點中的位圖有效地使用關鍵字剪枝，從而減少I/O代價和CPU時間，提高查詢效率。

(a) CPU時間比較

(b) I/O次數(shù)比較圖5 查詢模式對算法性能影響

4.2.3 查詢標簽數(shù)量對算法性能影響

本節(jié)實驗采用合成數(shù)據Train，對比查詢模式中包含不同的標簽數(shù)量對查詢效率的影響，得到實驗結果如圖6所示。隨著查詢模式中標簽數(shù)量增加，I/O代價及CPU時間逐漸降低并趨于穩(wěn)定，由于在固定范圍內匹配給定模式的軌跡數(shù)量減少，因此I/O代價降低，且由圖6可以看出LR-Tree的I/O代價及CPU時間明顯低于另外4種索引。

(a) CPU時間比較

(b) I/O次數(shù)比較圖6 查詢標簽數(shù)量對算法性能影響

4.2.4 查詢時間區(qū)間長度對算法性能影響

由圖7可以看出隨著查詢時間長度增加，I/O次數(shù)及CPU時間均呈增長趨勢。

(a) CPU時間比較

(b) I/O次數(shù)比較圖7 查詢時間區(qū)間長度對算法性能影響

在查詢過程中，給定查詢時間區(qū)間長度的不同，導致與給定時間區(qū)間相交的節(jié)點增加或減少，影響查詢返回結果，因此本節(jié)實驗考慮查詢時間區(qū)間長度的影響。由于查詢時間長度增加，與查詢時間區(qū)間相交的節(jié)點增加，通過索引過濾的軌跡數(shù)量減少，因此產生更多的I/O，導致CPU時間的增加。在5種索引中，隨著查詢時間增加，LR-Tree增長緩慢，可以看出基于LR-Tree的范圍模式查詢算法表現(xiàn)出良好的剪枝性能。

4.2.5 查詢范圍邊長對算法性能影響

在本節(jié)實驗比較查詢空間范圍的大小對查詢效率的影響。本節(jié)實驗設置(8500，9000)為查詢矩形框左下方坐標，設置查詢邊長為矩形框邊長，并以500為單位逐漸增大，實驗結果如圖8所示。可以看出隨著矩形框范圍逐漸增大，查詢的I/O次數(shù)及CPU時間逐漸增加。由于查詢空間范圍增加，返回結果數(shù)增加，導致I/O次數(shù)及CPU時間增加。另外4種索引I/O次數(shù)增長較明顯的同時，LR-Tree增長緩慢，可以看出LR-Tree查詢算法相較于另外4種索引表現(xiàn)出更高效的剪枝能力。

(a) CPU時間比較

(b) I/O次數(shù)比較圖8 查詢范圍邊長對算法性能影響

5 結束語

本文提出范圍模式匹配查詢，并設計了一種基于標簽R樹的查詢算法，考慮在給定時間區(qū)間范圍內的語義查詢問題。從不同參數(shù)的角度與基于已有索引的查詢算法在真實數(shù)據和合成數(shù)據上進行對比，實驗結果表明相較于包含語義信息的RR-Tree，基于標簽R樹的范圍模式匹配查詢算法查詢效率提高40%～70%，驗證了基于標簽R樹的范圍模式匹配查詢算法的有效性。未來將基于本文算法，提出在時間區(qū)間內包含多標簽的范圍模式匹配查詢。