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

梁珺秀,許建秋

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

0 引 言

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

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

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

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

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

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

1 相關(guān)工作

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

文獻(xiàn)[7]提出活動軌跡由一組同時包含位置和用戶活動的點所組成，描述用戶的活動信息；文獻(xiàn)[8]提出語義軌跡，在時空軌跡的基礎(chǔ)上描述移動對象在時刻點處的語義；文獻(xiàn)[9]提出軌跡表示為隨時間變化標(biāo)簽的符號軌跡，標(biāo)簽為字符串形式，不包含經(jīng)緯度信息。

Chen等[10]提出了基于活動軌跡的面向出行的活動軌跡搜索(Trip Oriented Search on Activity Trajectory，TOSAT)，給定起點和終點，返回在給定距離閾值內(nèi)，完全覆蓋給定活動且有最高軌跡匹配距離的前K條軌跡；Zheng等[11]提出語義軌跡的模糊關(guān)鍵字查詢，用戶給出查詢關(guān)鍵字，綜合考慮語義軌跡與查詢關(guān)鍵字的編輯距離和經(jīng)過給定關(guān)鍵字的軌跡長度，返回代價最小的前K條軌跡；Damiani等[12]提出了從符號的維度提取滿足給定模式的符號軌跡子軌跡，由子軌跡的時間范圍來限制空間維度在符號屬性和空間軌跡上的混合查詢。

2 問題描述

2.1 相關(guān)定義

定義1時空標(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)簽，loc1j表示開始時刻的地理位置，loc2j表示結(jié)束時刻的地理位置。

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

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

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

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

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

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

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

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

圖1 范圍模式匹配查詢

2.2 標(biāo)簽R樹

標(biāo)簽R樹索引(Label R-Tree，LR-Tree)，形式上由一個3DR-Tree[13]和一個標(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)簽表的映射計算所得的位圖。

定義6位圖匹配(Bitmap Match,BMatch(P,E))：對于給定模式P的位圖Tbit和LR-Tree項中位圖Ebit，?bit∈Tbit，當(dāng)Tbit(bit)=1時，若Ebit中對應(yīng)的位Ebit(bit)=1，則表示當(dāng)前位圖Ebit與查詢模式P位圖匹配，反之若存在一個或一個以上位不為1，則不匹配，其中模式P的位圖Tbit由模式P中所有出現(xiàn)的標(biāo)簽與LR-Tree中標(biāo)簽表對應(yīng)所得。

3 范圍模式匹配查詢

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

算法1 篩選過程

輸入：查詢模式P；查詢時間區(qū)間I；查詢空間范圍R；時空標(biāo)簽軌跡集合D；LR-Tree

輸出：中間結(jié)果集合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，設(shè)置棧S、保存LR-Tree篩選結(jié)果的隊列Q及最終查詢結(jié)果的隊列Res，首先將LR-Tree根節(jié)點入棧：

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

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

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

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

3.1 范圍模式匹配查詢篩選

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

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

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

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

3.2 范圍模式匹配查詢精細(xì)計算

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

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

算法2 精細(xì)計算

輸入：查詢模式P；查詢時間區(qū)間I；查詢空間范圍R；中間結(jié)構(gòu)集合Q

輸出：查詢結(jié)果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為時空標(biāo)簽軌跡，用來判斷traj是否經(jīng)過查詢空間范圍R，將軌跡投影至XY平面，得到軌跡在二維空間上的投影，實線部分為范圍R內(nèi)的子軌跡段subtraj，即為traj與查詢空間R的交集。對于subtraj，再與查詢時間區(qū)間計算，得到查詢時間區(qū)間內(nèi)的子軌跡段subtraj′，即為給定時空范圍內(nèi)的子軌跡段。根據(jù)范圍模式匹配定義，在得到子軌跡段subtraj′后，只需要考慮子軌跡段的模式匹配，判斷subtraj′是否與給定查詢模式P模式匹配，將匹配的子軌跡對應(yīng)的時空標(biāo)簽軌跡加入到返回結(jié)果集合Res中，最終Res中得到的所有軌跡即為范圍模式匹配查詢的結(jié)果。

圖2 軌跡投影

4 實驗性能與測試

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

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

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

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

4.1 對比索引介紹

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

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

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

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

為了驗證本文提出的基于LR-Tree范圍模式匹配查詢算法的有效性，采用C++語言在Linux環(huán)境下擴(kuò)展可擴(kuò)充移動對象數(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.30 GHz，4 GB內(nèi)存，Ubuntu14.04 64 bit操作系統(tǒng)，本部分實驗參數(shù)設(shè)置如表3所示。

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

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

本節(jié)實驗以不同數(shù)據(jù)集為實驗數(shù)據(jù)，比較5種索引在相同的查詢條件下，在不同數(shù)量級的數(shù)據(jù)集上的性能，得到的結(jié)果如圖4所示?？梢钥闯鲭S著數(shù)據(jù)量增長，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ù)據(jù)集對算法性能影響

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

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

(a) CPU時間比較

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

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

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

(a) CPU時間比較

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

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

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

(a) CPU時間比較

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

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

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

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

(a) CPU時間比較

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

5 結(jié)束語

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