基于時空標簽軌跡的k近鄰模式匹配查詢

許建秋，梁珺秀，秦小麟

（南京航空航天大學計算機科學與技術學院，江蘇 南京 211106）

1 引言

隨著智能電話及汽車導航系統等含 GPS技術的設備廣泛普及，每天都有大量的移動對象位置數據采集，目前，針對移動對象的查詢主要包含k近鄰查詢、范圍查詢、反向 k近鄰查詢和軌跡相似查詢[1～4]等。

越來越多的應用把移動對象軌跡數據與對象的文本屬性關聯起來，得到時空文本屬性隨時間變化的移動對象。目前，針對包含文本屬性的移動對象提出了語義軌跡[5]、活動軌跡[6]、符號軌跡[7]等，衍生出應用廣泛的關于時空文本的移動對象查詢[8～10]，即結合時空查詢和文本查詢以尋求最優結果的混合查詢，如可以作為路徑推薦的活動軌跡相似查詢（ATSQ,activity trajectory similarity query）[6]、k近鄰關鍵字查詢[11]、符號空間軌跡混合查詢[12]等。

在某些應用場景下，人們更傾向于提出給定模式的查詢，如“查找在15:00～18:00，距離查詢軌跡最近的前 k個從 P4出發經過若干景點后先經過P1后經過 P2的移動對象”。其中，P表示景點，查詢中提出的由P4出發先經過P1和P2是有順序要求的，且時間在給定的查詢范圍內，這種含有順序的文本屬性請求被稱為給定模式，目前還未有上述查詢請求的研究成果發表。將這種位置隨時間變化且包含文本信息到時間區間映射的軌跡稱為時空標簽軌跡，將這類查詢定義為基于時空標簽軌跡的k近鄰模式匹配查詢。與現有查詢相比，k近鄰模式匹配查詢存在以下特點：1) 模式匹配能處理較復雜的文本屬性查詢請求；2) 將模式匹配與時空屬性查詢相結合，同時解決不同維度的查詢。

如圖1所示，查找[t1,t2]時間范圍內由P4出發，先經過P1，后經過P2且距離Qtraj最近的軌跡，可以看出在給定查詢時間區間內，距離Qtraj最近的軌跡為traj2，而在時間區間[t1,t2]內，traj2不存在匹配給定模式的子軌跡段，在traj1和traj3中都存在匹配模式的軌跡段，而traj1距離Qtraj更近，因此，返回traj1為查詢結果。

圖1 k近鄰模式匹配查詢

為了解決k近鄰模式匹配查詢請求，本文主要貢獻如下。

1) 將時空屬性與隨時間變化的文本屬性結合，提出時空標簽軌跡。

2) 提出基于時空標簽軌跡的k近鄰模式匹配查詢（KPMQ,knearest neighbor pattern match query），并給出了KPMQ的定義。

3) 提出標簽R樹索引，并設計基于標簽R樹的深度優先遍歷算法處理基于模式匹配的k近鄰查詢，提高上述查詢效率。

2 相關工作

本文主要研究時空標簽軌跡的查詢及索引問題，相關工作包括2個部分：文本信息軌跡以及時空文本索引。

2.1 文本信息軌跡

目前，針對含文本屬性移動對象已有大量研究，主要包含活動軌跡、語義軌跡、符號軌跡等。活動軌跡是由Zheng等[6]提出的表示包含關于特定地點處的用戶活動信息的新類型的軌跡數據。針對這種軌跡提出了基于等級的活動軌跡搜索及基于順序的活動軌跡搜索等查詢。但是這種軌跡數據僅適用于描述用戶活動，并不能描述其他文本類型的軌跡數據。語義軌跡是由Alvares等[5]提出來的表示用注釋標記整個軌跡或其部分軌跡段的軌跡，每個注釋表示在其對應點處用戶的狀態或行為，用這些狀態或行為來豐富幾何軌跡。語義軌跡的概念已經吸引了在不同領域工作的許多研究者的興趣，如數據分析、概念建模、語義網、隱私等，研究問題主要包括語義[13]、移動知識發現[14]、隱私保護[15]3個方面。很多學者都考慮研究軌跡的停留點處的語義信息，在文獻[5]中，采用SmoT算法提取軌跡中的停留點，在文獻[16]中用 CBSMOT算法提取。語義軌跡關注點在軌跡的拐點處，而忽略了在軌跡的運動過程中可能產生的有用信息。符號軌跡是由Güting等[7]提出的不包含空間位置屬性，軌跡表現為隨時間變化的標簽。不同于上述2種軌跡，符號軌跡可以用于表示個人在時間區間內的活動等，例如，表示從家到工作地點的交通工具，在旅行期間訪問的景點等，并針對符號軌跡提出了模式匹配查詢和符號軌跡的重寫操作[17]。在文獻[12]中提出了一種結合符號軌跡和空間軌跡的混合查詢，從符號的維度提取滿足給定模式的符號子軌跡，由得到的子軌跡的時間范圍來限制空間維度，當子軌跡空間維度與幾何條件匹配時，則將其作為結果返回，最終得到同時滿足符號和時空條件的軌跡集合，但這種混合查詢僅考慮軌跡本身的屬性，不考慮軌跡間的相互關系。

2.2 時空文本索引

當查詢記錄過大時，為提高移動對象的查詢效率，索引是其中不可或缺的環節。常見的索引包括R樹[18]、網格索引及其變體等。3DR-Tree是R樹在時間空間上的擴展，由時間和空間3個維度組成，它將時間作為額外的維度，處理時間范圍的查詢，3DR-tree中每個節點中的項包含指向所有子節點的指針及其最小邊框矩形（MBR,minimal bounding rectangle），MBR為覆蓋其所有子節點的最小邊框矩形。SETI (scalable and efficient trajectory index)由Prasad等[19]提出，索引使用簡單的2層索引結構，將時間和空間屬性分開，分別對時間維度和空間維度進行索引，將空間維度按固定大小的網格劃分為不重疊的單元，分布在同一單元格的軌跡段保存在同一數據文件中，對每個單元格中的所有軌跡段的時間屬性建立一維R-Tree索引，因此，在同一個數據文件中的軌跡段在空間上是相近的。TB-Tree（trajectory bundle Tree）由 Dieter[20]提出，每個葉子節點只保存相同軌跡的軌跡段，這種結構保存了移動對象軌跡，忽略了軌跡空間屬性，導致同一個移動對象分布在不同的葉子節點中，導致節點重疊，空間分辨能力減弱。IR-Tree由Cong[21]提出，本質上是由倒排文件擴展的R樹，在樹的每個節點中含有指向倒排文件的指針，文件描述了存儲在節點中對象的活動。GAT（grid index for activity trajectories）由Zheng等[6]提出，建立分層網格，將整個空間劃分為d-Grid（2d×2d個網格），并進一步構建(d-1)- Grid,…,1-Grid，由d-Grid往上層構建倒排索引表示各個活動出現的網格，同時，在d-Grid層每個網格中，為每個出現的活動建立倒排索引表示哪些軌跡包含當前活動，最后建立一個數據結構表示每條軌跡中包含的所有活動。在這些包含文本屬性的索引中，文本屬性對應的都是軌跡的點，而不是整個時間區間，因此，不適用于時空標簽軌跡。

綜上所述，符號軌跡僅考慮語義信息忽略了位置，不支持同時具有語義和時空信息的查詢。語義軌跡和活動軌跡解決了時間點處的位置語義描述，但沒有考慮且不支持基于時間區間的語義屬性。針對該問題提出時空標簽軌跡模型，為有效支持基于時空標簽軌跡的k近鄰模式匹配查詢，設計標簽R樹索引以解決傳統移動對象索引結構不能對映射至時間區間上的語義屬性進行很好的描述的問題。

3 問題定義

KPMQ返回給定時間區間內滿足給定模式且與查詢軌跡Qtraj距離最近的前k條軌跡。移動對象包含的文本信息以標簽（label）的形式保存，為了明確所解決的問題，下面給出相關定義。

定義 1 時空標簽軌跡。traj=＜[I1,l1,loc11,loc21],… ,[In,ln,loc1n,loc2n]＞，其中，Ij表示時間區間，lj表示Ij對應的標簽，loc1j表示時間區間開始時刻移動對象的位置，loc2j表示時間區間結束時刻移動對象的位置，其中，每個[Ij,lj,loc1j,loc2j]為軌跡單元。

定義 2 模式。P=＜p1,…,pn＞，其中，pi為以下2種形式之一。

1)pi為(l)或()，其中，l為標簽，稱這種為單元模式。

2)pi為*、+、[p]、[pi|pj]、[p]+、[p]*或[p]?，稱這種為簡單模式，簡單模式中的p為單元模式或簡單模式，簡單模式中符號與正則表達式中符號表示意思相同。

每個單元模式表示一個事件，例如，將圖1查詢模式表示為＜(P4),*,(P1) ,(P2),*>，為了表示事件的順序性，引入正則表達式來描述完整的事件。

定義3 模式匹配（PMatch）。模式P=＜p1,…,pn＞與包含模式P'=＜p1′,…,pm′＞的軌跡traj模式匹配。

1) ?i∈[1,n]，?j∈[1,m]：pi=p′j。

2) ?i1，i2∈[1,n]，i1＜i2，?j1,j2∈[1,m]：pi1=p′j1，pi2=p′j2，且j1＜ j2。

綜上，當traj中存在軌跡段的標簽信息與P中標簽的內容相同且順序一致時，稱軌跡與P模式匹配。如圖1所示，軌跡traj1中的＜(P4),(P3),(P1),(P2)>子軌跡段模式與模式＜(P4),*,(P1),(P2),*>匹配。

定義 4k近鄰模式匹配查詢(KPMQ)。 給定時間區間I，查詢軌跡Qtraj以及模式P，返回軌跡集合D中大小為k的子集D′。

1) ?traj∈D′，PMatch(Interpolate(I,traj),P)。

2) 對于軌跡集合B，?t∈B,PMatch (Interpolate(I,t),P)，?traj′∈B-D′，有 Distance (Qtraj,traj’)≥Distance(Qtraj,traj)。

Interpolate (I,traj)表示在時間區間I內traj的子軌跡段，B為D中匹配模式的軌跡集合，D′軌跡集合為B中距離Qtraj最近的前k條軌跡組成的子集，則D′即為k近鄰模式匹配查詢的結果。

4 標簽R樹

標簽R樹（LR-Tree）形式上由一個3DR-Tree和一個標簽表組成，與 3DR-Tree的不同點如下。1) 每個 R樹節點的項（entry）中增加一個固定大小的位圖，位圖中的信息“0/1”代表了當前項指向的子節點的標簽存在性，當位圖的位為1時，表示位圖中的位對應的標簽表中的標簽存在，為0則不存在。2) 位圖的每個位通過散列函數對應到標簽表中的一個或多個位置，表中每位保存一個標簽。葉子節點項位圖中的每一位表示對應的移動對象的標簽存在性，非葉子節點項中的位圖通過其子節點的位圖執行按位或操作得出。

4.1 LR-Tree結構

4.1.1 LR-Tree節點項

LR-Tree葉子節點項表示為(rid,MBR,bitset)，其中，rid表示項所指向的下層節點，MBR即為將所有子節點項中的MBR包圍的最小矩形框，即為當前項的MBR，bitset由節點項所指向的子節點的所有位圖執行按位或操作得到。葉節點項表示為(tid,MBR,bitset)，其中，tid表示項所指向的移動對象，MBR為將移動對象包圍的最小矩形，bitset為指向的移動對象包含的標簽到標簽表的映射計算所得的位圖。

如圖2所示，N表示節點，E表示節點中的項，節點N2中2個項E3、E4的位圖即為對應N4、N5中所有位圖進行按位或操作所得，每個項包含指針指向對應的下層子節點。

LR-Tree在R-Tree的基礎上增加標簽信息，使在原有索引結構基礎上，不僅能表示地理位置，還能包含軌跡標簽信息存在性，因此，在查詢過程中可以同時考慮時空和文本約束條件，來提高查詢效率。增加的標簽信息在節點項中以位圖為單位存儲，占用空間大小以 bit為單位，位圖大小的設定可以根據標簽表中標簽數量大小改變，使索引所占空間較R樹空間增長較小。

4.1.2 LR-Tree位圖

移動對象的全部標簽保存在LR-Tree標簽層的標簽表中，標簽表與項中的位圖通過散列函數相關聯，標簽通過散列函數映射到位圖中，位圖中每位對應標簽表中的一個或多個標簽，當標簽出現在移動對象中時，將通過散列函數映射到位圖的比特置1。

LR-Tree中位圖長度在初始化后不能改變，當標簽表長度大于位圖長度時，可以通過散列函數將表中不同的標簽映射到位圖中的同一位。如圖2所示，LR-Tree固定位圖長度為5，而標簽表長度為6時，E7中的1號位指向表中1號標簽，而E13中1號位指向標簽表中6號標簽，可以看出1號和6號標簽同時映射到位圖中的1號位，因此，當位圖1號位為1時，表示1號標簽和6號標簽中至少有一個存在。

圖2 標簽R樹

4.2 LR-Tree構建

在標簽 R樹索引構造過程中，采用批量更新（bulkload）[22]構造，首先將所有軌跡的MBR按空間位置順序進行排序，將排序后的項依次插入到空節點N中，當N中項的數目達到上限或當前插入的項距離N太遠時，將N插入至LR-Tree中，并新建一個節點M，將該項插入M中。在將節點插入LR-Tree時，對當前節點項中所有位圖進行或操作，得到的結果作為插入項的位圖。

對于直接插入算法（directly insert），將待插入軌跡直接插入LR-Tree中，在建樹過程中先保留葉子節點處位圖，只考慮空間屬性自底向上建樹，將內部節點位圖均置為 0。在建樹完成后，自底向上更新LR-Tree中所有位圖。相較于直接插入，批量更新方法避免了對每一個插入項都產生一次 I/O，提高了標簽R樹索引構建效率。

5 k近鄰模式匹配查詢

5.1 算法基本思想

k近鄰模式匹配查詢（KPMQ）返回在時間區間I內，匹配給定模式P，且距離查詢軌跡Qtraj最近的前k條軌跡。利用LR-Tree處理該查詢，采用深度優先方法由根節點開始遍歷 LR-Tree。設置一個長度為k的優先隊列Q，存儲當前找到的k個結果。在訪問LR-Tree中的每個節點時，以I、P中標簽對應位圖、Q中移動對象的MBR與Qtraj的MBR間的最大距離值，作為LR-Tree的剪枝條件。在遍歷LR-Tree后，保存在優先隊列Q中的k條軌跡匹配模式P且距離查詢軌跡Qtraj最近，即為k近鄰模式匹配查詢的結果。在查詢過程中充分利用已知限制條件，遍歷LR-Tree從候選節點裁剪掉不可能的部分，提高查詢效率，具體步驟如圖3所示。

定義 5 位圖匹配（BMatch）。對于給定模式P的位圖Tbit和LR-Tree項中位圖Ebit，?Tbit[i]=1，若Ebit中對應的位Ebit[i]=1，則位圖Ebit與給定模式P位圖匹配，反之若?Tbit[i]=1而Ebit[i]≠1，則不匹配。

基于k近鄰模式匹配查詢如算法1所示，主要包括以下步驟。

1) 設定長度k的優先隊列Q保存當前查詢結果，棧S保存查詢節點，將LR-Tree根節點入棧。

2) 對于每個出棧的節點N，判斷N中的項是否與查詢時間區間相交且位圖匹配。Q.top()處保存當前隊列中距離查詢軌跡最遠的移動對象，若當前隊列Q長度為k，將最大距離值定為roof，進一步計算項的MBR與查詢軌跡的MBR間距離，將距離值大于roof的項過濾，若Q長度小于k則轉入步驟3)。

3) 對于步驟 2)中滿足條件的項，如算法 2所示，若當前節點為非葉節點，則將項按與查詢軌跡Qtraj的MBR間的距離值順序入棧；若節點為葉子節點，判斷項指向移動對象進行軌跡插值后的子軌跡段segtra是否匹配模式P，對于匹配項進一步計算插值后的Qtraj與segtra間的距離，若距離值小于roof則將其加入優先隊列中，并更新roof值作為之后的判斷條件。

4) 在遍歷LR-Tree后，Q中得到的所有軌跡則為匹配模式且距離查詢軌跡最近的前k條軌跡。

算法1 K近鄰模式匹配查詢（KPMQ）

輸入 查詢模式P

查詢時間區間I

查詢軌跡Qtraj

查詢結果個數k

移動對象集合D

LR-Tree

輸出 優先隊列Q

1)Q←?；S←?;

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

3) QMBR←Qtraj.MBR();

4) while (S不為空)

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

6) for eachentry∈Node

7) EMBR←entry.MBR();

8) if((I∩Qtraj.Interval)與 EMBR.Interval相交)

9) if(BMatch(P.Tbit,E.Ebit))

圖3 k近鄰模式匹配查詢過程

10) if(|Q| =k)

11)roof= Distance(Q.top(),Qtraj)

12) if(Distance(QMBR,EMBR)＜roof)

13) Update(S,Qtraj,Q,entry,P);

14) end if

15) else

16) Update(S,Qtraj,Q,entry,P);

17) end if

18) end if

19) end if

20) end for

21) end while

22) returnQ

5.2 過濾過程

由k近鄰查詢過程得到如下幾個重要引理。

引理1 給定時間區間I和查詢軌跡Qtraj，若節點項時間區間E.Interval∩(I∩Qtraj.Interval)=?，將以項指向的節點為根節點的子樹裁剪。

引理2 給定模式的位圖Tbit與節點項中位圖Ebit，若BMatch(Tbit,Ebit)=false，則將項指向的節點從樹中裁剪。

考慮給定模式P，提取P中所有標簽，并通過標簽表及對應的散列函數得到模式位圖Tbit，對于與Tbit位圖不匹配的節點項，則表示當前節點項的所有葉子節點中的位圖，必然存在一個或一個以上對應的位不為 1，則所指向的時空標簽軌跡中必然不存在查詢模式中的所有標簽，因此將以該項指向的子節點為根的子樹裁剪。

引理3 節點項最小邊框矩形EMBR、查詢軌跡 QMBR及優先隊列的最大距離值roof，若Distance (QMBR,EMBR)≥roof，則將項指向的節點從樹中裁剪。

在遍歷標簽R樹的過程中，將符合查詢條件的時空標簽軌跡保存在優先隊列Q中，Q存儲當前查詢中找到的滿足條件且距離查詢軌跡Qtraj最近的前k條軌跡。因此，若節點項 EMBR與查詢軌跡QMBR間的距離值大于或等于roof，則查詢軌跡與節點項 EMBR中包含的所有軌跡的距離必然不小于roof值，不可能作為距離最近的前k條軌跡保存在Q中，因此，將項所指向的節點從樹中裁剪。

算法2 Update

輸入 棧S

查詢軌跡Qtraj

優先隊列Q

項entry

查詢模式P

輸出 更新entry后的S、Q

1) if (Node為內部節點)

2)S.push(entry.ptr);//插入后的棧中的entry按距離值排序

3) else

4) if(PMatch(P,Interpolate(I,Qtraj))

5) if(Distance(Interpolate(I,Qtraj),Interpolate(I,entry.traj))＜roof)

//Interpolate表示取查詢時間內的軌跡段

6)Q.push_back(entry.tid);

7) 更新Q中最大距離值roof;

8) end if

9) end if

10) end if

采用深度優先方法遍歷 LR-Tree，對于每個出棧的節點，在將其所有子節點入棧前，在步驟2)中先將其中不符合條件的項過濾。對于篩選后的子節點按照它與Qtraj的MBR間的距離排序后從大到小入棧，確保下回出棧的節點是當前棧中距離Qtraj最近的矩形框，盡早利用優先隊列的roof值剪枝，提高LR-Tree空間剪枝能力。

5.3 精細計算過程

對于篩選過后要進行精細計算的每條軌跡，進行模式匹配與距離計算查詢前，先進行軌跡插值計算得到子軌跡段。如圖4所示，查詢時間區間箭頭寬度表示查詢區間范圍，利用查詢區間范圍對每條軌跡進行約束，取軌跡定義時間區間與查詢時間區間交集內的子軌跡段中的信息，包含時空信息及標簽信息，圖4中虛線部分即為插值后的子軌跡段。

圖4 軌跡插值

在插值得到子軌跡段后，先對子軌跡段進行模式匹配，將由正則表達式表示的查詢模式P轉化為NFA，并判斷每個子軌跡段能否到達 NFA中的終態，將可到達終態的軌跡段取出，再進行距離計算，由優先隊列的roof值對軌跡段進行篩選，最終優先隊列Q中保存的軌跡即為查詢結果。

6 實驗及分析

為了驗證提出的標簽R樹處理k近鄰模式匹配查詢算法的有效性，采用C++語言在Linux環境下，擴展可擴充數據庫SECONDO[23]，向數據庫中添加操作代碼，實現基于時空標簽軌跡的k近鄰模式匹配查詢。實驗環境為：Intel(R)Core(TM) I3-2120 CPU@ 3.30 GHz，4 GB內存，Ubuntu14.04 64bit操作系統。

6.1 實驗數據

實驗中使用真實數據集和合成數據集做對比實驗。2種數據均表示語義屬性對應至時間區間上的時空軌跡。真實數據集是微軟亞洲研究院Geolife[24]。項目組收集182個用戶3年內的GPS數據，其中，部分用戶用交通方式標記了他們的運動數據（如步行、火車等）。數據記錄真實世界中不同出現頻率的標簽，因此，能準確地表示不同標簽在查詢中影響。合成數據集是 SECONDO系統中人工合成地鐵軌跡的數據Train，包含562輛地鐵的運動軌跡，為每條軌跡貼上不同的合成標簽，其中，標簽為1～50中的任意數字，每個數字表示不同的標簽，每種標簽出現的概率相同，每條軌跡包含5～10個標簽。地鐵數據模擬帶標簽的數據集合，從大規模數據及多種標簽角度考慮對查詢效率的影響。采用數據加倍方法對軌跡進行x、y方向上的偏移，得到平移的軌跡數據。數據集信息如表1所示，Train(n)是在Train的基礎上進行x、y方向上平移得到的n2倍數據。

表1 數據集的數據統計

6.2 索引構建

6.2.1 索引構建性能比較

本節實驗研究比較采用批量更新算法和直接插入算法在構建LR-Tree上的性能比較，使用合成數據集構建LR-Tree，實驗結果如圖5所示。可以看出直接插入算法的索引構建開銷遠大于采用批量更新算法。隨著數據量的增加，直接插入算法的構建時間呈顯著增長趨勢，而批量更新算法增長更為緩慢，相較于直接插入方法，批量更新方法的構建時間降低了約90%。

圖5 批量更新直接插入性能比較

6.2.2 位圖長度對空間影響

本部分實驗比較 LR-Tree中設置不同長度的位圖對索引空間大小的影響。LR-Tree保存在以1K為單位的數據塊中。圖6中st-status表示時空屬性占用空間大小，bitmap表示位圖占用空間大小。由圖6(a)可以看出位圖長度保持在10～30時，LR-Tree大小保持不變，長度為 40～50時，位圖空間增大。由于位圖占用空間較小，導致位圖長度在一定范圍內增長時，總體增長的空間大小不超過數據塊剩余空間大小，位圖占用空間無明顯增加，因此實驗設置位圖長度默認值為30。

由圖6(b)可以看出隨著數據量增加，樹的節點增加，位圖所占空間增加，但位圖所占大小始終保持在整體大小的4%～7%之間。

6.3 查詢性能實驗

實驗測試LR-Tree的查詢處理性能，包括數據量、模式中不同頻率的標簽、標簽數量、給定時間區間長度和返回結果數k。對不同的參數進行測試，比較k近鄰模式匹配查詢的平均I/O次數及CPU時間，測試LR-Tree的剪枝能力，從而比較其處理查詢性能，實驗參數設置如表2所示。

圖6 LR-Tree位圖—時空占用比

表2 實驗參數

6.3.1 數據量對算法性能影響

本部分實驗以不同數據集為實驗數據，在相同查詢時間、返回結果及查詢模式下，比較4種索引在不同數量級的數據集上的性能，結果如圖 7所示。可以看出隨著數據量增長，相較于另外 3種索引，LR-Tree的I/O代價及CPU時間增長更為緩慢，相較3DR-Tree降低了50%～70%的I/O及CPU代價。

6.3.2 查詢標簽數量對算法性能影響

圖7 數據集對查詢性能影響

圖8 (a)和圖8(b)顯示了標簽數量對查詢算法的影響，隨著標簽數量增加，LR-Tree的I/O代價增加不明顯并逐漸趨于穩定，而另外3種索引空間剪枝能力大幅度下降，I/O代價急劇增加。由于LR-Tree的剪枝同時包含標簽和時空，隨著標簽數量增加，導致匹配給定模式的移動對象數量急劇減少，使空間剪枝能力降低，I/O代價略微增加。因此，當標簽數量較多時，LR-Tree較另外3種索引具有明顯的剪枝能力，當查詢模式中標簽數大于3時，查詢效率提高了90%以上。

在本節實驗中，同時對比基于LR-Tree的深度優先算法（DF）和廣度優先算法(BF)受標簽數量變化的影響，結果如圖8(c)所示。可以看出相較于BF算法，采用DF算法的I/O次數降低了50%以上，體現了基于LR-Tree的DF算法的優越性。

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

本節實驗以 Geolife為實驗數據，統計不同標簽出現次數，得到的結果如表3所示。實驗得到的結果如圖9(a)和圖9(b)所示，對比表3中標簽出現次數，可以看出相較于另外3種索引，對于出現頻率較低的標簽，如飛機、自行車及火車、LR-Tree能有效地使用關鍵字剪枝，減少I/O代價和CPU時間，相較于3DR-Tree提高30%及以上的查詢效率。

圖8 標簽數對查詢算法影響

表3 標簽頻數

6.3.4 給定時間區間長度對算法性能影響

合成數據中軌跡的定義時間區間長度在 2～3h內，在本次實驗中將給定時間區間的開始時刻定義為查詢軌跡的開始時刻，得到的結果如圖9(c)和圖 9(d)所示。可以看出當給定時間區間的長度小于查詢軌跡的長度時，隨著時間區間長度增加I/O代價增加，當大于查詢軌跡長度時，則保持不變。由于過濾條件中包含查詢時間區間，隨著時間區間增大，過濾的節點減少導致I/O代價增加，當給定時間區間大于查詢軌跡定義時間區間長度時，過濾的時間區間固定為查詢軌跡的定義時間區間，因此過濾時間區間條件不變，對 I/O次數不產生影響。可以看出相較于另外 3種索引，LR-Tree產生了更少的I/O次數及CPU時間，表現出更好的剪枝能力，相較于 3DR-Tree提高40%～50%的查詢效率。

6.3.5 返回結果數k對算法性能影響

本部分實驗設置不同k值，得到基于4種不同索引的查詢算法性能對比如圖 9(e)和圖9(f)所示，可以看出隨著返回結果數量增加，I/O次數增加。由于4種索引都包含通過優先隊列的閾值剪枝的方法，k值影響空間剪枝能力，因此，當k值較小時，能盡早地利用優先隊列中的最大距離值對大于最大距離值的節點進行剪枝，當k值增加時，空間剪枝能力降低，I/O次數及CPU代價增加，相較于 3DR-Tree降低了 60%～80%的I/O次數及CPU代價。

7 結束語

本文設計了一種基于標簽R樹的k近鄰模式匹配查詢算法，增加一個標簽表并在已有R樹節點項中加入判斷標簽是否存在的位圖，使 R樹索引僅在已有空間剪枝能力基礎上，增加標簽屬性的剪枝能力，給出LR-Tree的批量更新方法并與直接插入建樹方法進行比較，體現了批量更新方法的高效性。對于k近鄰模式匹配查詢，用真實數據和合成數據比較 LR-Tree與 3DR-Tree、SETI及 TB-Tree索引在不同參數下的剪枝能力。實驗結果表明LR-Tree在位圖空間僅占據4%～7%空間的基礎上，能夠更有效地支持k近鄰模式匹配查詢，并在數據量增長較大時有良好的可擴展性。本文算法考慮的是模式完全匹配，在接下來的工作中可以考慮當模式部分匹配時，軌跡間相似程度的算法。

圖9 不同參數對CPU時間及I/O次數影響

參考文獻：

[1]XUAN K,ZHAO G,TANIAR D,et al. Continuous range search query processing in mobile navigation[C]//The IEEE International Conference on Parallel and Distributed Systems. 2008: 361-368.

[2]GAO Y J,LI C,CHEN G C,et al. Efficient k-nearest- neighbor search algorithms for historical moving object trajectories[J]. Journal of Computer Science and Technology,2007,22(2): 232-244.

[3]BENETIS R,JENSEN C S,KAR?IAUSKAS G,et al. Nearest neighbor and reverse nearest neighbor queries for moving objects[C]//The IEEE International Symposium on Database Engineering & Applications. 2002:44-53.

[4]TIAKAS E,PAPADOPOULOS A N,NANOPOULOS A,et al.Searching for similar trajectories in spatial networks[J]. Journal of Systems & Software,2009,82(5): 772-788.

[5]ALVARES L O,BOGORNY V,KUIJPERS B,et al. A model for enriching trajectories with semantic geographical information[C]//The ACM International Symposium on Advances in Geographic Information Systems. 2007: 22.

[6]ZHENG K,SHANG S,YUAN N J,et al. Towards efficient search for activity trajectories[C]//The IEEE International Conference on Data Engineering. 2013: 230-241.

[7]GüTING R H,VALDéS F,DAMIANI M L. Symbolic trajectories[J].ACM Transactions on Spatial Algorithms & Systems,2015,1(2): 1-51.

[8]WU D,YIU M L,JENSEN C S,et al. Efficient continuously moving top-k spatial keyword query processing[C]//The IEEE International Conference on Data Engineering. 2011: 541-552.

[9]ZHENG B,YUAN N J,ZHENG K,et al. Approximate keyword search in semantic trajectory database[C]//The IEEE International Conference on Data Engineering. 2015: 975-986.

[10]HAN Y,WANG L,ZHANG Y,et al. Spatial keyword range search on trajectories[M]//Database Systems for Advanced Applications.Springer International Publishing. 2015: 223-240.

[11]FELIPE I D,HRISTIDIS V,RISHE N. Keyword search on spatial databases[C]//The IEEE International Conference on Data Engineering.2008: 656-665.

[12]DAMIANI M L,ISSA H,GüTING R H,et al. Hybrid queries over symbolic and spatial trajectories: a usage scenario[C]//The IEEE International Conference on Mobile Data Management. 2014: 341-344.

[13]SPACCAPIETRA S,PARENT C,DAMIANI M L,et al. A conceptual view on trajectories[J]. Data & Knowledge Engineering,2008,65(1): 126-146.

[14]ZHANG C,HAN J,SHOU L,et al. Splitter: mining fine-grained sequential patterns in semantic trajectories[J]. Proceedings of the Very Large Data Bases Endowment,2014,7(9): 769-780.

[15]PARENT C,SPACCAPIETRA S,RENSO C,et al. Semantic trajectories modeling and analysis[J]. ACM Computing Surveys,2013,45(4): 1-32.

[16]PALMA A T,BOGORNY V,KUIJPERS B,et al. A clustering-based approach for discovering interesting places in trajectories[C]//The ACM Symposium on Applied Computing. 2008: 863-868.

[17]VALDéS F,DAMIANI M L,GüTING R H. Symbolic trajectories in SECONDO: Pattern Matching and Rewriting[J]. Lecture Notes in Computer Science,2013,7826(2): 450-453.

[18]GUTTMAN A. R-trees: a dynamic index structure for spatial searching[C]//The ACM SIGMOD International Conference on Management of Data. 1984: 47-57.

[19]PRASAD V,ADAM C,EVERSPAUGH C,et al. Indexing large trajectory data sets with SETI[C]// Conference on Innovative Data Systems Research. 2003.

[20]PFOSER D,JENSEN C S,THEODORIDIS Y. Novel approaches in query processing for moving object trajectories[C]//International Conference on Very Large Data Bases. 2000: 395-406.

[21]CONG G,JENSEN C S,WU D. Efficient retrieval of the top-k most relevant spatial web objects[J]. Proceedings of the Very Large Data Bases Endowment,2009,2(1): 337-348.

[22]BERCHTOLD S,B?HM C,KRIEGEL H P. Improving the query performance of high-dimensional index structures by bulk load operations[J]. Lecture Notes in Computer Science,1998,1377(2): 216-230.

[23]GUTING R H,ALMEIDA V,ANSORGE D,et al. SECONDO: an extensible DBMS platform for research prototyping and teaching[C]//International Conference on Data Engineering. 2005: 1115-1116.

[24]ZHENG Y,XIE X,MA W Y. GeoLife: a collaborative social networking service among user,location and trajectory[J]. Bulletin of the Technical Committee on Data Engineering,2010,33(2): 32-39.