盧航，李艷紅，黃金亮

（中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院， 武漢 430074）

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

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

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

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

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

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

1 準(zhǔn)備工作

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

1.1 路網(wǎng)模型

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

1.2 時(shí)間范圍最佳路徑

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

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

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

表1 頂點(diǎn)關(guān)鍵字-有效時(shí)間表Tab.1 Vertex keyword-effective timetable

1.4 查詢模型

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

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

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

2.1 IGT-Tree的圖劃分

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

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

2.2 IGT-Tree的倒排索引

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

表2 關(guān)鍵字索引Tab.2 Keyword index

2.3 IGT-Tree的距離矩陣

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

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

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

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

表6 G6的邊界點(diǎn)-頂點(diǎn)距離矩陣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索引的有效時(shí)間

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

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

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

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

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

3.1 基于有效時(shí)間目標(biāo)關(guān)鍵字查詢算法

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

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

為了得到包含有效時(shí)間的關(guān)鍵字目標(biāo)點(diǎn)ed，需要從葉子結(jié)點(diǎn)Gst開始，通過對包含在葉子結(jié)點(diǎn)內(nèi)的每個(gè)節(jié)點(diǎn)進(jìn)行時(shí)間戳和倒排序列的剪枝處理，需要對每個(gè)非根結(jié)點(diǎn)進(jìn)行一次搜索，時(shí)間代價(jià)主要集中在對葉子結(jié)點(diǎn)Gst、Ged和最近公共父結(jié)點(diǎn)Gp之間層數(shù)差的遍歷操作中，對每層相鄰樹結(jié)點(diǎn)之間都要進(jìn)行一次最小邊界點(diǎn)的計(jì)算，而層數(shù)差j 的最大值為IGT-Tree 的高度H=logf(V/τ)+1，其中V為頂點(diǎn)總數(shù)、τ 為葉子結(jié)點(diǎn)包含的頂點(diǎn)數(shù)、f為非葉子結(jié)點(diǎn)的扇出，因此基于有效時(shí)間目標(biāo)關(guān)鍵字查詢算法的時(shí)間復(fù)雜度為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 //將關(guān)鍵字K轉(zhuǎn)化為二進(jìn)制序列Kb 2： Convert Search time t to timestamp ts //將查詢時(shí)間轉(zhuǎn)化為時(shí)間戳ts 3： Find the leaf node Gst that contains st //找到包含起始點(diǎn)st 的葉子結(jié)點(diǎn)Gst 4： while parent node of Gst ！= ? do 5： Search the inverted index KGst of Gst //輸出結(jié)點(diǎn)Gst的倒排索引KGst 6： if KGst contains Kb then 7： Find the vertex ved that contains the keyword K //找到包含關(guān)鍵字K的頂點(diǎn)ved 8： Search the valid time Tved of vertex ved //查詢ved的有效時(shí)間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é)點(diǎn)GstP 14： continue 15： end if 16： else 17： Find the Parent node GstP of Gst //找到Gst的父結(jié)點(diǎn)GstP 18： continue 19： end if 20： end while

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

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

第一步判斷起始點(diǎn)st 和目標(biāo)點(diǎn)ed 是否被包含在同一葉子結(jié)點(diǎn)內(nèi)，由IGT-Tree 可知，包含起始點(diǎn)v6的結(jié)點(diǎn)為G6，而包含目標(biāo)點(diǎn)v1的結(jié)點(diǎn)為G4，它們不在相同的葉子結(jié)點(diǎn)內(nèi)；若它們包含在同一葉子結(jié)點(diǎn)內(nèi)，可由該葉子結(jié)點(diǎn)的邊界點(diǎn)-頂點(diǎn)距離矩陣直接得出最短路徑.接下來根據(jù)包含頂點(diǎn)v6和v1的葉子結(jié)點(diǎn)G6和G4，遍歷IGT-Tree 找到最近的公共父結(jié)點(diǎn)Gf即G0，查詢G6和G4的邊界點(diǎn)矩陣分別找到它們的邊界點(diǎn)BG6和BG4（BG代表圖G中的任意的邊界點(diǎn)），計(jì)算dist（v6，BG6）和dist（v1，BG4）找到權(quán)值最小的邊界點(diǎn)Bv6=v6和Bv1=v1（Bv代表頂點(diǎn)v為邊界點(diǎn)）；若邊界點(diǎn)不為目標(biāo)點(diǎn)ed，則將Bed作為中間點(diǎn).由G0的邊界點(diǎn)距離矩陣可知，G0的邊界點(diǎn)為v1、v2、v4和v7，且位于G0不同孩子結(jié)點(diǎn)的最小權(quán)值為dist（v1，v4）=5.判斷Bv6和Bv1是否為G0的邊界點(diǎn)，顯然Bv1=BG0=v1，而Bv6≠BG0不為G0的邊界點(diǎn)，比較出dist（v6，BG0）的最小權(quán)值的邊界點(diǎn)v7.雖然到起始點(diǎn)v6權(quán)值最小的邊界點(diǎn)為v7，但不能直接將v7作為中間節(jié)點(diǎn)，需要比較起始點(diǎn)v6到G0中距目標(biāo)點(diǎn)v1權(quán)值最小的邊界點(diǎn)v4，即dist（v6，v4）+ dist（v4，v1）=7，和dist（v6，v7）+dist（v7，v1）=11，選擇權(quán)值更小的為中間點(diǎn)，故將v4作為中間點(diǎn)，根據(jù)G0的邊界點(diǎn)距離矩陣，可得δ（v4，v1）=｛v4，v1｝；若目標(biāo)點(diǎn)ed不為G0的邊界點(diǎn)，則計(jì)算dist（ed，BG0）選擇權(quán)值最小的邊界點(diǎn)作為中間點(diǎ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 和目標(biāo)位置ed 間的最佳路徑，需要對節(jié)點(diǎn)st和ed分別位于的葉子結(jié)點(diǎn)Gst和Ged尋找最近非空父結(jié)點(diǎn)進(jìn)行查詢，對于被查詢的結(jié)點(diǎn)，需要對其包含的i個(gè)滿足關(guān)鍵字條件的對象，計(jì)算一次有效時(shí)間的匹配性，而i不大于τ。同時(shí)最多遍歷n個(gè)樹結(jié)點(diǎn)，因此基于有效時(shí)間最佳路徑規(guī)劃算法的時(shí)間復(fù)雜度為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 //找到包含起始點(diǎn)st 的葉子結(jié)點(diǎn)Gst 2： Find the leaf node Ged that contains ed //找到包含目標(biāo)點(diǎn)ed 的葉子結(jié)點(diǎn)Ged 3： while nearest parent node Gf of Gst and Ged ！= ? do //Gst和Ged的最近父結(jié)點(diǎn)Gf不為空4： Search the boundary point distance matrix of Gst to get the boundary point BGst //找到葉子結(jié)點(diǎn)Gst的邊界點(diǎn)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的邊界點(diǎn)距離矩陣可得δ（st，ed）9： return δ（st，ed）10： else 11： Find the boundary point Bed of the minimum value of dist（ed，BGed） //找到邊界點(diǎn)BGed距離ed最近的那個(gè)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í)驗(yàn)

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

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

4.1 系統(tǒng)設(shè)置

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

4.2 實(shí)驗(yàn)結(jié)果分析

4.2.1 索引建立性能分析

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

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

4.2.2 關(guān)鍵字查詢分析

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

圖5 IGT-Tree和G-Tree關(guān)鍵字查詢時(shí)間與正確率Fig.5 IGT-Tree and G-Tree keyword query time and accuracy rate

4.2.3 不同時(shí)間段查詢的準(zhǔn)確率分析

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

圖6 不同時(shí)間點(diǎn)查詢準(zhǔn)確率對比Fig.6 Comparison of query accuracy at different time points

5 結(jié)論

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