基于時間的關鍵字路網(wǎng)路徑規(guī)劃

盧航，李艷紅，黃金亮

（中南民族大學 計算機科學學院， 武漢 430074）

智能手機等移動設備基本上都具備了GPS 芯片，它們每天都能產(chǎn)生大量的位置信息，輕松地獲取用戶的位置數(shù)據(jù).為了給用戶提供基于位置的服務（LBS），產(chǎn)生了大量的LBS 應用，例如，谷歌地圖，高德地圖等.在日常生活中有很多應用場景，如用戶希望找到道路網(wǎng)絡上某兩個點之間的最短路徑.隨著用戶的需求越來越高，近年來附加了文本信息的空間對象查詢，即空間關鍵字查詢［1-4］，受到廣泛的關注.每個對象都包含一個或者多個關鍵字來描述它，當用戶需要某個關鍵字提供的功能時，而具備關鍵字的目標點往往不是唯一的，因此需要從搜索地點尋找一條最短或者最合適的路徑，這樣的過程被稱為路徑規(guī)劃［5-6］.

然而，現(xiàn)有的研究主要集中在尋找代價最低的路徑，例如基于動態(tài)權(quán)值的路徑規(guī)劃研究等［7-8］.實際上，時間是一個非常重要的影響因素.圖1 中，用戶位于o點，計劃去餐飲店，此時是21：10，根據(jù)用戶的需求，查詢的關鍵字應為“Restaurant”.如圖1 所示，用戶o距離包含關鍵字“Restaurant”的對象v1最近，但v1的營業(yè)時間為（15：00-20：30），因此對象v1并不能被選擇作為目標點；對象v5雖然距離用戶o相較v1更遠，但v5此時正在營業(yè)，因而應該推薦給該用戶從o點到頂點v5的最短路徑.為此，將“有效時間”的概念引入路徑規(guī)劃問題中，為每個對象都設置一個有效時間，當查詢時間不在對象有效時間內(nèi)時，具有關鍵詞的對象將不能被推薦.

圖1 路網(wǎng)圖Fig.1 Road network map

為了便于道路網(wǎng)絡距離的計算、對象文本信息和時間信息的組織和快速獲取，本文在G-Tree［9-10］的基礎上改進索引結(jié)構(gòu)，增加時間戳和倒排序列相關信息，將改進后的索引結(jié)構(gòu)稱為IGT-Tree.它用GTree 組織路網(wǎng)結(jié)構(gòu)和路網(wǎng)距離信息，用倒排文件組織對象的關鍵字信息，并為關鍵字增加有效時間，采用時間戳的方式來存儲有效時間.因而可以根據(jù)路網(wǎng)距離、關鍵字信息和有效時間進行剪枝，提高搜索效率.并基于構(gòu)建的IGT-Tree 設計兩種推薦算法，一種是基于時間的目標點查詢算法，用于尋找符合有效時間的最近目標點；另一種是在目標點查詢算法基礎上的路徑推薦算法，用在基于時間的道路網(wǎng)絡中，為查詢點和目標點之間推薦一條最佳路徑.簡而言之，本文的主要貢獻概括如下：

—提出了一種改進G-Tree 的索引結(jié)構(gòu)IGTTree，有效地組織路網(wǎng)結(jié)構(gòu)信息、對象關鍵字信息和有效時間信息.

—通過模擬實驗驗證了所提出的基于IGT-Tree算法的目標關鍵字查詢結(jié)果和所規(guī)劃路徑的準確率比基于G-Tree的方法更高.

1 準備工作

本節(jié)介紹必要的背景信息，以及道路網(wǎng)絡上路徑規(guī)劃所采用的數(shù)據(jù)模型和查詢模型.

1.1 路網(wǎng)模型

將道路網(wǎng)絡抽象成一個無向加權(quán)圖G=（V，E），其中V是頂點的集合，E是邊的集合，每條邊（u，v）∈E連接著兩個相鄰的頂點u和v（u、v∈V）.并且每條邊都關聯(lián)一個表示距離或者行程時間的非負權(quán)重w（u，v）＞0.路徑P（v1，vn）=｛v1，v2，…，vn｝（n≥1）是一個有序的頂點集合，即（vi，vi+1）∈E（1≤i≤n-1）.給定頂點u和v，使用δ（u，v）表示從頂點u到v的最短路徑，用距離權(quán)值dist（u，v）表示δ（u，v）路徑上各條邊的權(quán)重之和.圖1顯示了道路網(wǎng)絡的示意圖，如果給定起始點v1和目標點v7，那么δ（v1，v7）=｛v1，v4，v6，v7｝表示v1到v7間的最短路徑，其距離權(quán)值dist（v1，v7）=9.

1.2 時間范圍最佳路徑

給定查詢起始位置st、目標位置ed 和一組關鍵字K=｛k1，k2，…，kn｝，其中ki（i∈（1，n））代表各個關鍵字，道路網(wǎng)絡上每個頂點vi（i∈（1，n））都有相應的關鍵字描述，并且每個頂點v都具有一個有效時間T=［t1，t2］，t1和t2代表時間戳（Timestamp，ts），即一個時間點.例如，［8：30-11：30］代表開始時間戳為8.5，結(jié)束時間戳為11.5，在這兩個時間戳范圍內(nèi)該關鍵字是有效關鍵字.從查詢起始點st 到含有符合有效時間t和一組關鍵字K的目標點ed 的最短路徑，稱為有效時間的最佳路徑（Time-aware Best Path， TBP）.

1.3 數(shù)據(jù)模型

給定對象o，具有空間位置L=｛l1，l2，…，lm｝（m≥1）和一組關鍵字K=｛k1，k2，…，kn｝（n≥1），并且每個對象都存在一個有效時間T=［t1，t2］.邊（o1，o2）∈E的權(quán)值w（o1，o2）表示兩個空間相鄰對象o1和o2之間的路網(wǎng)距離或者行駛時間，本文假設空間文本對象o位于頂點vi（i∈（1，n））上（表1）.

表1 頂點關鍵字-有效時間表Tab.1 Vertex keyword-effective timetable

1.4 查詢模型

給定道路網(wǎng)G，假定用戶位于查詢點st，其關鍵字集合為K=｛k1，k2，…，kn｝（1≤i≤n）.基于上述信息，希望找到一條最佳路徑TBP（st，ed，K，t），在查詢時間t從起始點st 到符合其有效時間T且含有目標關鍵字K的結(jié)點ed 之間的一條最短路徑δ（st，ed），其權(quán)值為dist（st，ed）.

2 數(shù)據(jù)索引IGT-Tree

IGT-Tree用于規(guī)劃道路網(wǎng)絡最佳路徑查詢的索引技術.G-Tree 和IR2-Tree［11-12］這兩個索引啟發(fā)了通過設計IGT-Tree 來解決TBP（st，ed，K，t）的查詢問題.G-Tree 被用于道路網(wǎng)絡上的路網(wǎng)距離計算，而IR2-Tree 被用于歐氏空間中的空間關鍵字查詢.雖然這兩種索引結(jié)構(gòu)不能直接用于道路網(wǎng)絡上最佳路徑查詢，但可以基于該思想，改進并創(chuàng)建一種新的索引結(jié)構(gòu)IGT-Tree，以滿足最佳路徑查詢的要求.

2.1 IGT-Tree的圖劃分

以圖1 路網(wǎng)為例，使用多級劃分算法［13］將路網(wǎng)抽象出的無向圖劃分成了若干個子圖，由于圖劃分過程是通過多級劃分算法來執(zhí)行的，保證了每個子圖大小幾乎相同.圖2 是IGT-Tree 的圖劃分例子，整個道路網(wǎng)路被劃分為兩個子圖，分別用G1和G2表示.然后，G1繼續(xù)被劃分為G3和G4兩個子圖，類似的G2被劃分為G5和G6兩個子圖，直到每個子圖的頂點個數(shù)小于預設值（一般大于等于2）時停止劃分.將兩個子圖連接起來的頂點稱為邊界點.圖G1由子圖G3和G4組成，頂點v1、v2和v3構(gòu)成了G1的邊界點；G1和G2共同組合成了G0，G0的邊界點由v1、v2、v4和v7組成.

圖2 IGT-Tree的路網(wǎng)圖劃分Fig.2 Road network map division of IGT-Tree

2.2 IGT-Tree的倒排索引

圖1中，每個頂點都包含關鍵字的信息，對IGTTree每個結(jié)點通過倒排文件索引該結(jié)點覆蓋區(qū)域內(nèi)頂點的關鍵字信息.假定系統(tǒng)有N個關鍵字，對系統(tǒng)中的所有關鍵字按順序排列，每個關鍵字對應一個序號.IGT-Tree 每個結(jié)點設置一個N位的二進制數(shù)，以表示該結(jié)點是否包含此關鍵字.對于葉子結(jié)點，對于每個關鍵字，如果該葉結(jié)點包含的對象存在該關鍵字，則對應位置為1，否則為0；對于非葉子節(jié)點，將對應孩子結(jié)點的倒排序列通過邏輯“或”運算來得到其倒排索引.例如，對于葉子節(jié)點G4，它對應的頂點v1、v2和v9所包含的關鍵字為“Restaurant”、“Tea”和“Supermarket”，這些關鍵字所對應的倒排序列分別為10000、01000、00010，對它們進行邏輯“或”運算后得到11010，因此葉子結(jié)點G4的倒排索引為11010.由此可見，根結(jié)點G0的倒排索引通常全為1.關鍵字索引如表2所示.

表2 關鍵字索引Tab.2 Keyword index

2.3 IGT-Tree的距離矩陣

雖然各個結(jié)點添加倒排索引，能夠快速地區(qū)分各個子圖是否存在目標關鍵詞，但還是無法知道搜索位置與目標地點的路徑距離，因此，計算并保存邊界點距離矩陣，便于尋找出頂點之間的最小代價路徑.連接兩個子圖的頂點被標記為邊界點，并存儲在IGT-Tree 中，邊界點距離矩陣保存的是每個子圖內(nèi)部邊界點之間的最小權(quán)值路徑距離.以G0為例，它的邊界點是v1、v2、v4和v7，其邊界點距離矩陣保存的是各個邊界點之間具有最小權(quán)重的路徑距離，由圖3中G0的邊界點距離矩陣可知，v1到v2、v4和v7的最小權(quán)重路徑距離分別為2、5 和9.邊界點-頂點距離矩陣保存圖的邊界點到子圖里其他頂點的最小權(quán)重路徑距離，因此只有葉子結(jié)點存在邊界點-頂點距離矩陣.表3-6為邊界點-頂點距離矩陣.

表3 G3的邊界點-頂點距離矩陣Tab.3 G3 boundary point-vertex distance matrix

表4 G4的邊界點-頂點距離矩陣Tab.4 G4 boundary point-vertex distance matrix

表5 G5的邊界點-頂點距離矩陣Tab.5 G5 boundary point-vertex distance matrix

表6 G6的邊界點-頂點距離矩陣Tab.6 G6 boundary point-vertex distance matrix

圖3 IGT-Tree索引結(jié)構(gòu)Fig.3 The structure of IGT-Tree index

2.4 IGT-Tree索引的有效時間

由于每個頂點所包含的關鍵字均具有有效時間，為了表示頂點對象的有效時間間隔，引入時間戳的概念，以1 個小時為1 個時間單位，每天都被劃分成了24個時間單位，例如（21：00，22：00），可以轉(zhuǎn)化為［21，22］來表示時間段二十一點至二十二點.如表1所示，每個結(jié)點都包含了關鍵詞和有效時間的信息.關鍵字和有效時間保存在IGT-Tree中對應的葉子結(jié)點中，對于非葉子結(jié)點的有效時間，其處理和倒排索引類似，都使用其子結(jié)點的邏輯“或”來計算.例如對于非葉子結(jié)點G3來說，其子結(jié)點為v3和v8，它們對應的有效時間分別為（12：00，24：00）和（10：00，18：00），將它們轉(zhuǎn)化為時間戳（12，24）∪（10，18），然后通過“或”運算，得到結(jié)點G3的時間戳為（10，24）.所以根結(jié)點G0的時間戳一般為（0，24）.

2.5 IGT-Tree整體結(jié)構(gòu)

IGT-Tree 結(jié)構(gòu)見圖3，對于每個非葉子結(jié)點，包含子圖的名稱、對應的邊界點距離矩陣、倒排索引和時間戳；對于每個葉子結(jié)點，包含子圖名稱、對應的倒排索引、邊界點-頂點距離矩陣以及時間戳.

3 關鍵字查詢和路網(wǎng)規(guī)劃

基于所構(gòu)建的IGT-Tree 索引結(jié)構(gòu)，提出了兩種查詢處理算法，即有效時間目標點查詢算法和有效時間最佳路徑規(guī)劃算法.

3.1 基于有效時間目標關鍵字查詢算法

本算法為用戶查找在時間感知路網(wǎng)下包含目標關鍵字的頂點.算法的主要步驟是尋找包含查詢點st 所位于的最小邊界矩形（Minimal Bounding Rectangle），即包含st 的葉子結(jié)點Gst，再通過它的倒排索引，判斷Gst所包含的頂點是否有滿足條件的關鍵字K，如果存在目標點ed′，再查詢頂點ed′對應時間戳ted′，從而計算出發(fā)點st到目標點ed′所耗費的時間tb=dist（st，ed′）/θ（θ為速度變量，這里取6 km/h）和查詢時間t之和得到的預期時間T=t+tb，判斷T是否滿足結(jié)點ed′的有效時間（t1ed，t2ed），若滿足，則結(jié)點ed′即為目標點ed；若不滿足，那么再通過Gst的父結(jié)點Gf依次進行查詢.

例如，當用戶位于道路網(wǎng)絡中的頂點v6時，在14：30 時搜索關鍵詞“Restaurant”，此時st=v6，t=14.5，需找到包含關鍵詞K=｛Restaurant｝的目標點ed，同時滿足從st 到達ed 時的預期時間T在有效時間（t1ed，t2ed）內(nèi).首先將關鍵詞K=｛Restaurant｝轉(zhuǎn)換為其對應的二進制序列，即10000；然后查詢IGT-Tree，找到st 所位于的MBR 即葉子結(jié)點G6.遍歷IGT-Tree可知結(jié)點G6的關鍵字倒排索引KG6為00111，表2 可知結(jié)點G6沒有關鍵字K=｛Restaurant｝對應的二進制序列10000，結(jié)點G6不符合.然后從G6的父結(jié)點G2開始查詢，結(jié)點G2的倒排索引為11111，存在關鍵字K對應的二進制序列10000，遍歷G2的孩子結(jié)點，得到G5包含目標關鍵字的葉子結(jié)點G5.遍歷G5包含的頂點，可得頂點v5包含關鍵詞K，計算dist（st，v5）=2，可得T=t+dist（st，v5）/θ=14.83，而頂點v5的有效時間為［17，23］，顯然預期時間T不滿足v5的有效時間.雖然頂點v5含有目標關鍵字K，但它不能滿足查詢要求，故排除掉.再從G2的父節(jié)點G0開始查詢，通過以上方法可知頂點v1包含關鍵字K，計算dist（st，v1）=7，得T=t+dist（st，v1）/θ=14.5+1.17=15.67，查詢頂點v1的有效時間為［15，20.5］，預期時間T滿足v1的有效時間.因此可得查詢的目標點ed=v1，如算法1所示.

為了得到包含有效時間的關鍵字目標點ed，需要從葉子結(jié)點Gst開始，通過對包含在葉子結(jié)點內(nèi)的每個節(jié)點進行時間戳和倒排序列的剪枝處理，需要對每個非根結(jié)點進行一次搜索，時間代價主要集中在對葉子結(jié)點Gst、Ged和最近公共父結(jié)點Gp之間層數(shù)差的遍歷操作中，對每層相鄰樹結(jié)點之間都要進行一次最小邊界點的計算，而層數(shù)差j 的最大值為IGT-Tree 的高度H=logf(V/τ)+1，其中V為頂點總數(shù)、τ 為葉子結(jié)點包含的頂點數(shù)、f為非葉子結(jié)點的扇出，因此基于有效時間目標關鍵字查詢算法的時間復雜度為O(logf(V/τ)).

Algorithm 1 Finding the nearest target point ed on IGT-Tree Input： IGT-Tree ， st ， K ，t Output： ed 1： Convert the key K to a binary sequence Kb //將關鍵字K轉(zhuǎn)化為二進制序列Kb 2： Convert Search time t to timestamp ts //將查詢時間轉(zhuǎn)化為時間戳ts 3： Find the leaf node Gst that contains st //找到包含起始點st 的葉子結(jié)點Gst 4： while parent node of Gst ！= ? do 5： Search the inverted index KGst of Gst //輸出結(jié)點Gst的倒排索引KGst 6： if KGst contains Kb then 7： Find the vertex ved that contains the keyword K //找到包含關鍵字K的頂點ved 8： Search the valid time Tved of vertex ved //查詢ved的有效時間Tved 9： Calculate t = t + dist（st，ved）/θ 10： if Tved contains t then 11： return ed = ved 12： else 13： Find the Parent node GstP of Gst //找到Gst的父結(jié)點GstP 14： continue 15： end if 16： else 17： Find the Parent node GstP of Gst //找到Gst的父結(jié)點GstP 18： continue 19： end if 20： end while

3.2 基于有效時間最佳路徑規(guī)劃算法

由上述3.1 可知，當用戶位于結(jié)點v6，搜索關鍵字為“Restaurant”即K=｛Restaurant｝，此時查詢時間為14：30 即T=14.5 時，符合條件的最近目標點ed=v1，因此δ（v6，v1）=（v6，v4，v1）即TBP=（v6，v4，v1），如何找到TBP中的每個頂點，是本節(jié)要解決的問題.

第一步判斷起始點st 和目標點ed 是否被包含在同一葉子結(jié)點內(nèi)，由IGT-Tree 可知，包含起始點v6的結(jié)點為G6，而包含目標點v1的結(jié)點為G4，它們不在相同的葉子結(jié)點內(nèi)；若它們包含在同一葉子結(jié)點內(nèi)，可由該葉子結(jié)點的邊界點-頂點距離矩陣直接得出最短路徑.接下來根據(jù)包含頂點v6和v1的葉子結(jié)點G6和G4，遍歷IGT-Tree 找到最近的公共父結(jié)點Gf即G0，查詢G6和G4的邊界點矩陣分別找到它們的邊界點BG6和BG4（BG代表圖G中的任意的邊界點），計算dist（v6，BG6）和dist（v1，BG4）找到權(quán)值最小的邊界點Bv6=v6和Bv1=v1（Bv代表頂點v為邊界點）；若邊界點不為目標點ed，則將Bed作為中間點.由G0的邊界點距離矩陣可知，G0的邊界點為v1、v2、v4和v7，且位于G0不同孩子結(jié)點的最小權(quán)值為dist（v1，v4）=5.判斷Bv6和Bv1是否為G0的邊界點，顯然Bv1=BG0=v1，而Bv6≠BG0不為G0的邊界點，比較出dist（v6，BG0）的最小權(quán)值的邊界點v7.雖然到起始點v6權(quán)值最小的邊界點為v7，但不能直接將v7作為中間節(jié)點，需要比較起始點v6到G0中距目標點v1權(quán)值最小的邊界點v4，即dist（v6，v4）+ dist（v4，v1）=7，和dist（v6，v7）+dist（v7，v1）=11，選擇權(quán)值更小的為中間點，故將v4作為中間點，根據(jù)G0的邊界點距離矩陣，可得δ（v4，v1）=｛v4，v1｝；若目標點ed不為G0的邊界點，則計算dist（ed，BG0）選擇權(quán)值最小的邊界點作為中間點.因此最終dist（st，ed）=dist（v6，v4）+dist（v4，v1）=7，而δ（st，ed）=｛v6，v4，v1｝，即TBP（v6，v1，｛restaurant｝）=｛v6，v4，v1｝.如算法2所示.

為了尋找起始位置st 和目標位置ed 間的最佳路徑，需要對節(jié)點st和ed分別位于的葉子結(jié)點Gst和Ged尋找最近非空父結(jié)點進行查詢，對于被查詢的結(jié)點，需要對其包含的i個滿足關鍵字條件的對象，計算一次有效時間的匹配性，而i不大于τ。同時最多遍歷n個樹結(jié)點，因此基于有效時間最佳路徑規(guī)劃算法的時間復雜度為O(n·τ).

Algorithm 2 Finding the best path from st to ed on IGT-Tree Input：IGT-Tree，st，ed Output：δ（st，ed）1： Find the leaf node Gst that contains st //找到包含起始點st 的葉子結(jié)點Gst 2： Find the leaf node Ged that contains ed //找到包含目標點ed 的葉子結(jié)點Ged 3： while nearest parent node Gf of Gst and Ged ！= ? do //Gst和Ged的最近父結(jié)點Gf不為空4： Search the boundary point distance matrix of Gst to get the boundary point BGst //找到葉子結(jié)點Gst的邊界點BGst 5： Search the boundary point distance matrix of Ged to get the boundary point BGed 6： if st = BGst then 7： if ed = BGed then 8： Search the boundary point distance matrix of Gf to get δ（st，ed） //由Gf的邊界點距離矩陣可得δ（st，ed）9： return δ（st，ed）10： else 11： Find the boundary point Bed of the minimum value of dist（ed，BGed） //找到邊界點BGed距離ed最近的那個Bed 12： Search the boundary point distance matrix of Gf to get δ（st，Bed）13： return δ（st，ed） = δ（st，Bed）+δ（Bed，ed）14： end if 15： else 16： Find the boundary point Bst of the minimum value of dist（st，BGst）17： if ed = BGed then 18： Search the boundary point distance matrix of Gf to get δ（Bst，ed）19： return δ（st，ed） = δ（st，Bst）+δ（Bst，ed）20： else 21： Find the boundary point Bed of the minimum value of dist（ed，BGed）22： Search the boundary point distance matrix of Gf to get δ（Bed，ed）23： return δ（st，ed）=δ（st，Bst）+δ（Bst+Bed）+δ（Bed，ed）24： end if 25： end if 26： end while

4 實驗

采用了兩個合成的數(shù)據(jù)集CA 和SF（通過真實的California和San Francisco兩個城市的路網(wǎng)數(shù)據(jù)和實驗系統(tǒng)產(chǎn)生的數(shù)據(jù)對象合成的），其中隨機產(chǎn)生的對象包含了關鍵字信息、有效時間信息和位置信息.其中CA 包含1458 個數(shù)據(jù)對象和46 個關鍵字，SF 包含10000 個數(shù)據(jù)對象和215 個關鍵字，對于CA中的每一個對象，通過zipf分布［14］為其分配1-2個關鍵字，每個對象的有效時間范圍設置在［0-24］，且遵循高斯分布［15］；對于SF 中的每一個對象同樣采用zipf 分布的方式為其分配3 個關鍵字.現(xiàn)實生活中，每個對象能具備多個關鍵字，SF 和CA 的對象的有效時間設置方式相同.另外，每個對象的位置都隨機分布在路網(wǎng)的節(jié)點上，由于以上的數(shù)據(jù)集是根據(jù)數(shù)據(jù)對象的時間特征和關鍵字特征進行合成的，因此對實驗結(jié)果沒有影響.表7為兩個數(shù)據(jù)集的特征.

表7 實驗數(shù)據(jù)集特征Tab.7 Characteristices of data sets

4.1 系統(tǒng)設置

設備為Intel Core i5-8400，2.8 GHz CPU，GTX 1060TI，16 GB RAM Windows10 的電腦，所有算法的開發(fā)及運行均在Java 1.8.0_302的運行環(huán)境下完成.

4.2 實驗結(jié)果分析

4.2.1 索引建立性能分析

本節(jié)評估IGT-Tree索引的構(gòu)建時間和內(nèi)存空間消耗這兩方面的性能.圖4（a）顯示在CA 和SF 兩個大小不同的數(shù)據(jù)集下，IGT-Tree 和G-Tree 索引建立耗費的時間和占內(nèi)存空間的大小.盡管IGT-Tree 索引加入了有效時間，其創(chuàng)建時間和G-Tree 相差無幾；不過隨著數(shù)據(jù)集的增大，它們兩者的索引創(chuàng)建時間差距會稍微增大.圖4（b）顯示IGT-Tree 索引所占內(nèi)存空間大小略大于G-Tree 索引，這是因為IGTTree 索引相較于G-Tree 中除了邊界點距離矩陣、倒排索引和邊界點-頂點距離矩陣以外，每個結(jié)點和葉子結(jié)點所包含的頂點還包含了時間戳的內(nèi)容.

圖4 IGT-Tree和G-Tree的索引創(chuàng)建時間與大小Fig.4 Index creation time and size of IGT-Tree and G-Tree

4.2.2 關鍵字查詢分析

根據(jù)CA 和SF 兩個數(shù)據(jù)集，設置不同的關鍵字數(shù)，CA 設置為1 個，SF 設置為2～3 個，設置每個對象的有效時間T 隨機分布在［0-24］內(nèi)，查詢G-Tree 和IGT-Tree兩種索引結(jié)構(gòu)下查詢算法對于目標關鍵字查詢的正確率.圖5（a）顯示IGT-Tree 的查詢時間比G-Tree 稍大，圖5（b）中，在關鍵字K更大的SF 數(shù)據(jù)集里，查詢時間變長但正確率會隨之變大，當數(shù)據(jù)集變大后，IGT-Tree 和G-Tree 的查詢正確率也變得比較接近，并且正確率同時都在提高.因為隨著單個對象包含的關鍵字數(shù)增多，在有效時間不變的情況下，有效的目標對象會隨之增多，因此增大了查詢的正確率，并且在G-Tree 下查詢的關鍵字，由于可選的對象增多，在查詢時，目標對象處于有效時間的可能性同時變大，因此隨著K的數(shù)值變大，G-Tree的查詢正確率會逐漸接近IGT-Tree.

圖5 IGT-Tree和G-Tree關鍵字查詢時間與正確率Fig.5 IGT-Tree and G-Tree keyword query time and accuracy rate

4.2.3 不同時間段查詢的準確率分析

為了探究在一天內(nèi)各個不同時間點查詢目標的正確率，G-Tree和IGT-Tree兩者的性能差別，根據(jù)CA 和SF 兩個數(shù)據(jù)集，設置不同的關鍵字數(shù)，CA 設置為1 個，SF 設置為2-3 個，設置每個對象的有效時間T 隨機分布在［0-24］內(nèi)，對比G-Tree 和IGT-Tree兩種索引下查詢算法在不同時間內(nèi)目標關鍵字的查詢正確率.根據(jù)圖6，結(jié)果顯示隨著數(shù)據(jù)集變大，兩者查詢的正確率都隨之提高.在［8，16］這個時間區(qū)間內(nèi)，IGT-Tree 和G-Tree 查詢的正確率差值收小并且變化規(guī)律類似，但在［20，24］∪［0，8］這個時間區(qū)間內(nèi)，IGT-Tree 的查詢正確率相較于G-Tree 提升明顯，隨著數(shù)據(jù)集的增大，兩者之間的正確率的差距也有所縮小.因為查詢時間越晚，處于有效時間的對象數(shù)量也在減少.G-Tree 的查詢對象往往都是時間代價最小的，但隨著T處于［20，24］∪［0，8］這個時間區(qū)間內(nèi)，很多對象已經(jīng)不在有效時間范圍內(nèi)，這也導致IGT-Tree查詢正確率的降低.

圖6 不同時間點查詢準確率對比Fig.6 Comparison of query accuracy at different time points

5 結(jié)論

為解決基于時間的關鍵字路網(wǎng)路徑規(guī)劃問題，本文提出一種有效的路網(wǎng)索引結(jié)構(gòu)IGT-Tree，并在此基礎上提出關鍵字查詢算法和路徑規(guī)劃算法.對比以往的索引結(jié)構(gòu)G-Tree，在有效時間的路網(wǎng)關鍵字查詢下，能提高查詢的準確率，尤其是在T=［20，24］∪［0，8］這個時間段內(nèi)，查詢準確率相較于G-Tree提升明顯.實驗結(jié)果驗證了本文提出的IGT-Tree 索引結(jié)構(gòu)和算法在處理基于時間的路網(wǎng)關鍵字查詢和路徑規(guī)劃的可行性和準確性.