基于時空標(biāo)簽軌跡的k近鄰模式匹配查詢

許建秋，梁珺秀，秦小麟

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

1 引言

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

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

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

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

圖1 k近鄰模式匹配查詢

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

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

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

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

2 相關(guān)工作

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

2.1 文本信息軌跡

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

2.2 時空文本索引

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

綜上所述，符號軌跡僅考慮語義信息忽略了位置，不支持同時具有語義和時空信息的查詢。語義軌跡和活動軌跡解決了時間點(diǎn)處的位置語義描述，但沒有考慮且不支持基于時間區(qū)間的語義屬性。針對該問題提出時空標(biāo)簽軌跡模型，為有效支持基于時空標(biāo)簽軌跡的k近鄰模式匹配查詢，設(shè)計標(biāo)簽R樹索引以解決傳統(tǒng)移動對象索引結(jié)構(gòu)不能對映射至?xí)r間區(qū)間上的語義屬性進(jìn)行很好的描述的問題。

3 問題定義

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

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

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

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

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

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

定義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。

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

定義 4k近鄰模式匹配查詢(KPMQ)。 給定時間區(qū)間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)表示在時間區(qū)間I內(nèi)traj的子軌跡段，B為D中匹配模式的軌跡集合，D′軌跡集合為B中距離Qtraj最近的前k條軌跡組成的子集，則D′即為k近鄰模式匹配查詢的結(jié)果。

4 標(biāo)簽R樹

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

4.1 LR-Tree結(jié)構(gòu)

4.1.1 LR-Tree節(jié)點(diǎn)項

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

如圖2所示，N表示節(jié)點(diǎn)，E表示節(jié)點(diǎn)中的項，節(jié)點(diǎn)N2中2個項E3、E4的位圖即為對應(yīng)N4、N5中所有位圖進(jìn)行按位或操作所得，每個項包含指針指向?qū)?yīng)的下層子節(jié)點(diǎn)。

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

4.1.2 LR-Tree位圖

移動對象的全部標(biāo)簽保存在LR-Tree標(biāo)簽層的標(biāo)簽表中，標(biāo)簽表與項中的位圖通過散列函數(shù)相關(guān)聯(lián)，標(biāo)簽通過散列函數(shù)映射到位圖中，位圖中每位對應(yīng)標(biāo)簽表中的一個或多個標(biāo)簽，當(dāng)標(biāo)簽出現(xiàn)在移動對象中時，將通過散列函數(shù)映射到位圖的比特置1。

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

圖2 標(biāo)簽R樹

4.2 LR-Tree構(gòu)建

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

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

5 k近鄰模式匹配查詢

5.1 算法基本思想

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

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

基于k近鄰模式匹配查詢?nèi)缢惴?所示，主要包括以下步驟。

1) 設(shè)定長度k的優(yōu)先隊列Q保存當(dāng)前查詢結(jié)果，棧S保存查詢節(jié)點(diǎn)，將LR-Tree根節(jié)點(diǎn)入棧。

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

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

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

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

輸入 查詢模式P

查詢時間區(qū)間I

查詢軌跡Qtraj

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

移動對象集合D

LR-Tree

輸出 優(yōu)先隊列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 給定時間區(qū)間I和查詢軌跡Qtraj，若節(jié)點(diǎn)項時間區(qū)間E.Interval∩(I∩Qtraj.Interval)=?，將以項指向的節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹裁剪。

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

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

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

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

算法2 Update

輸入 棧S

查詢軌跡Qtraj

優(yōu)先隊列Q

項entry

查詢模式P

輸出 更新entry后的S、Q

1) if (Node為內(nèi)部節(jié)點(diǎn))

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表示取查詢時間內(nèi)的軌跡段

6)Q.push_back(entry.tid);

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

8) end if

9) end if

10) end if

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

5.3 精細(xì)計算過程

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

圖4 軌跡插值

在插值得到子軌跡段后，先對子軌跡段進(jìn)行模式匹配，將由正則表達(dá)式表示的查詢模式P轉(zhuǎn)化為NFA，并判斷每個子軌跡段能否到達(dá) NFA中的終態(tài)，將可到達(dá)終態(tài)的軌跡段取出，再進(jìn)行距離計算，由優(yōu)先隊列的roof值對軌跡段進(jìn)行篩選，最終優(yōu)先隊列Q中保存的軌跡即為查詢結(jié)果。

6 實(shí)驗(yàn)及分析

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

6.1 實(shí)驗(yàn)數(shù)據(jù)

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

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

6.2 索引構(gòu)建

6.2.1 索引構(gòu)建性能比較

本節(jié)實(shí)驗(yàn)研究比較采用批量更新算法和直接插入算法在構(gòu)建LR-Tree上的性能比較，使用合成數(shù)據(jù)集構(gòu)建LR-Tree，實(shí)驗(yàn)結(jié)果如圖5所示?？梢钥闯鲋苯硬迦胨惴ǖ乃饕龢?gòu)建開銷遠(yuǎn)大于采用批量更新算法。隨著數(shù)據(jù)量的增加，直接插入算法的構(gòu)建時間呈顯著增長趨勢，而批量更新算法增長更為緩慢，相較于直接插入方法，批量更新方法的構(gòu)建時間降低了約90%。

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

6.2.2 位圖長度對空間影響

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

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

6.3 查詢性能實(shí)驗(yàn)

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

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

表2 實(shí)驗(yàn)參數(shù)

6.3.1 數(shù)據(jù)量對算法性能影響

本部分實(shí)驗(yàn)以不同數(shù)據(jù)集為實(shí)驗(yàn)數(shù)據(jù)，在相同查詢時間、返回結(jié)果及查詢模式下，比較4種索引在不同數(shù)量級的數(shù)據(jù)集上的性能，結(jié)果如圖 7所示?？梢钥闯鲭S著數(shù)據(jù)量增長，相較于另外 3種索引，LR-Tree的I/O代價及CPU時間增長更為緩慢，相較3DR-Tree降低了50%～70%的I/O及CPU代價。

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

圖7 數(shù)據(jù)集對查詢性能影響

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

在本節(jié)實(shí)驗(yàn)中，同時對比基于LR-Tree的深度優(yōu)先算法（DF）和廣度優(yōu)先算法(BF)受標(biāo)簽數(shù)量變化的影響，結(jié)果如圖8(c)所示?？梢钥闯鱿噍^于BF算法，采用DF算法的I/O次數(shù)降低了50%以上，體現(xiàn)了基于LR-Tree的DF算法的優(yōu)越性。

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

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

圖8 標(biāo)簽數(shù)對查詢算法影響

表3 標(biāo)簽頻數(shù)

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

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

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

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

7 結(jié)束語

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

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

參考文獻(xiàn)：

[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.