TD-H2H：時(shí)序圖上的最短路徑查詢

李新玲，王一舒，袁野，谷香，王國仁

1.東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，沈陽110167

2.北京理工大學(xué) 計(jì)算機(jī)學(xué)院，北京100081

圖數(shù)據(jù)已廣泛用于社交媒體營銷、知識(shí)發(fā)現(xiàn)、交通網(wǎng)絡(luò)以及移動(dòng)網(wǎng)絡(luò)分析等場(chǎng)景[1]。圖中的最短路徑查詢是一個(gè)已經(jīng)被廣泛研究的基本問題，是許多應(yīng)用的基礎(chǔ)，例如路徑規(guī)劃、信息與疾病傳播以及生物學(xué)中的代謝途徑分析等[2]。道路網(wǎng)絡(luò)中的路徑規(guī)劃問題是基于位置服務(wù)的重要研究[3]，合理的規(guī)劃方案能夠幫助人們更有預(yù)見性地旅行。為回答該問題，現(xiàn)有研究通常將道路網(wǎng)絡(luò)建模為靜態(tài)圖，并將給定節(jié)點(diǎn)對(duì)在圖中的最短路徑作為規(guī)劃結(jié)果返回，其中最短路徑是指邊權(quán)重和最小的路徑，即總距離最短的路徑。但是，現(xiàn)實(shí)生活中，同一條道路，在不同的出發(fā)時(shí)間下，所需的通過時(shí)間通常是不同的，例如，一條道路在早晚高峰時(shí)通過往往會(huì)花費(fèi)更多的時(shí)間。因此，距離最短的路徑并不完全等于旅行時(shí)間最短的路徑。顯然對(duì)于用戶來說，旅行時(shí)間最短的路徑才是更合理的路徑規(guī)劃結(jié)果。

由于需要考慮時(shí)間的影響，交通網(wǎng)絡(luò)是最適合建模為時(shí)序圖的網(wǎng)絡(luò)之一[4]。很多的交通管理系統(tǒng)能夠向用戶提供實(shí)時(shí)的交通信息，這些交通系統(tǒng)所管理的道路網(wǎng)絡(luò)都可以被刻畫為大規(guī)模的圖數(shù)據(jù)模型。在這些模型中，通過一條邊（道路）的代價(jià)不是一成不變的，而是會(huì)隨著時(shí)間的變化而變化[5]。因此，本文將道路網(wǎng)絡(luò)建模為時(shí)序圖GT(V,E,F)，GT邊上的權(quán)重fe(t)∈F與時(shí)間信息相關(guān)聯(lián)，是以出發(fā)時(shí)間t為自變量的函數(shù)，表示出發(fā)時(shí)間為t時(shí)通過邊e∈E所需的時(shí)間。文獻(xiàn)[6]已經(jīng)證明了時(shí)序最短路徑查詢問題在具有先進(jìn)先出屬性的時(shí)序圖上是多項(xiàng)式可解的。其中FIFO 屬性是指：對(duì)于任意出發(fā)時(shí)間t1＜t2，有t1+fe(t1)＜t2+fe(t2)，即如果汽車A與B都需要行駛過道路L，并且A先于B進(jìn)入L，那么一定也是A先于B離開L。本文假設(shè)時(shí)序圖中每條邊上的權(quán)重函數(shù)都具有FIFO屬性。

道路網(wǎng)絡(luò)的規(guī)模很大，每一個(gè)節(jié)點(diǎn)都只能通過它的入邊鄰居到達(dá)[7]。建模為時(shí)序圖后，邊上的權(quán)值從常數(shù)變?yōu)榱藭r(shí)間函數(shù)，相比靜態(tài)圖，時(shí)序圖的結(jié)構(gòu)要復(fù)雜、龐大得多。因此，如果源節(jié)點(diǎn)與目的節(jié)點(diǎn)間的距離很遠(yuǎn)，使用非索引方法進(jìn)行時(shí)序最短路徑查詢時(shí)，通常需要幾十秒才能得出查詢結(jié)果，并不能在實(shí)際生活中應(yīng)用。為提高查詢效率，本文基于樹分解[8]的概念構(gòu)建了TD-H2H（time dependent-hierarchical 2-hop）索引。樹分解是一種將圖轉(zhuǎn)變?yōu)闃浣Y(jié)構(gòu)的操作，也可用于表示分解操作后得到的樹結(jié)構(gòu)TG。基于圖的樹分解思想，可以將規(guī)模大且難解的問題轉(zhuǎn)化為規(guī)模小且易解的子問題。樹寬是樹分解的重要性質(zhì)之一，如果圖的樹寬被常數(shù)限制，那么圖上許多棘手的問題都可以在多項(xiàng)式時(shí)間甚至線性時(shí)間內(nèi)解決[9]。給定圖G，節(jié)點(diǎn)u和v在G內(nèi)的點(diǎn)割集是指u和v間所有路徑一定經(jīng)過的節(jié)點(diǎn)的集合。任意兩個(gè)節(jié)點(diǎn)間的點(diǎn)割集都不是唯一的，且索引的大小與點(diǎn)割集內(nèi)的節(jié)點(diǎn)數(shù)量成正比，查詢時(shí)間的長短與索引的大小成正比。確定的點(diǎn)割集越小，索引就越小，查詢速度越快。基于樹分解TG可以為G確定任意一對(duì)節(jié)點(diǎn)間的點(diǎn)割集，且每個(gè)點(diǎn)割集的大小都以TG的樹寬為界。又因?yàn)榈缆肪W(wǎng)絡(luò)可以分解為低樹寬的樹分解[10]，所以基于樹分解可以為圖中的節(jié)點(diǎn)對(duì)確定較小的點(diǎn)割集。綜上所述，為了加速求解時(shí)序道路網(wǎng)絡(luò)上的最短路徑查詢問題，本文設(shè)計(jì)了時(shí)序樹分解算法，通過該算法可以獲得具有較小樹寬的樹分解TGt，根據(jù)TGt獲得以樹寬為界的點(diǎn)割集C，根據(jù)C來創(chuàng)建TD-H2H索引以加速查詢，最后基于TD-H2H設(shè)計(jì)了高效的最短路徑查詢算法TD-OAI（time dependentout edge and in edge）。

本文的主要貢獻(xiàn)如下：

（1）基于傳統(tǒng)的樹分解方法提出了時(shí)序樹分解算法。時(shí)序樹分解中，使用時(shí)序節(jié)點(diǎn)消除操作構(gòu)造樹節(jié)點(diǎn)，每個(gè)樹節(jié)點(diǎn)都由多個(gè)圖節(jié)點(diǎn)組成（第3章）。

（2）基于時(shí)序樹分解提出了索引TD-H2H，TDH2H由兩類最短旅行時(shí)間函數(shù)表組成，即out旅行時(shí)間表與in旅行時(shí)間表。使用樹分解能夠加速索引的構(gòu)建過程，文中給出了詳細(xì)的構(gòu)建算法（第4章）。

（3）基于TD-H2H設(shè)計(jì)了高效的最短路徑查詢算法TD-OAI，TD-OAI 根據(jù)樹分解中的節(jié)點(diǎn)訪問最短旅行時(shí)間函數(shù)表中的元素，可以很大程度地提高最短路徑查詢速度（第5章）。

（4）在真實(shí)數(shù)據(jù)集上進(jìn)行了對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果證明了本文算法的有效性，且在查詢效率方面優(yōu)于現(xiàn)有的算法（第6章）。

1 相關(guān)工作

樹分解最初由文獻(xiàn)[8]提出，給定圖G,樹分解是指對(duì)G中的節(jié)點(diǎn)集進(jìn)行劃分后生成的一棵分解樹TG，TG中的節(jié)點(diǎn)與G中的節(jié)點(diǎn)子集一一對(duì)應(yīng)。通過研究樹分解的結(jié)構(gòu)信息可以加快圖中某些問題的計(jì)算速度。基于圖G可以生成多個(gè)樹寬不同的樹分解，每個(gè)樹分解的樹寬等于樹分解中包含最多圖節(jié)點(diǎn)的樹節(jié)點(diǎn)中圖節(jié)點(diǎn)的數(shù)量減1，其中具有最小樹寬的樹分解為G的最優(yōu)樹分解。圖的樹寬和樹分解的引入給算法的分析和設(shè)計(jì)帶來了一些新的思路。某些NP問題，若將其限定在有限樹寬的圖中，則其求解是可行的[11]。現(xiàn)有計(jì)算最優(yōu)樹分解的技術(shù)只能用于處理小圖（節(jié)點(diǎn)數(shù)量小于1 000的圖）[12]。此外，現(xiàn)有的樹分解算法均用于計(jì)算靜態(tài)圖無向圖的樹分解，無法直接處理時(shí)序有向圖。由于最優(yōu)樹分解的計(jì)算難度大，本文通過改進(jìn)對(duì)靜態(tài)無向圖進(jìn)行樹分解的次優(yōu)方法[13]來計(jì)算時(shí)序有向圖的樹分解，該算法不保證以有界近似比計(jì)算樹寬。本文的索引構(gòu)建和查詢算法的時(shí)間復(fù)雜度都是樹寬的多項(xiàng)式且道路網(wǎng)絡(luò)可以分解為具有低樹寬的樹分解[10]，因此，次優(yōu)的樹分解算法適用于現(xiàn)實(shí)中大型道路網(wǎng)絡(luò)中的路徑規(guī)劃問題。

靜態(tài)圖上的最短路徑查詢方法可以分為非索引方法與索引方法兩類，其中經(jīng)典的非索引方法有Dijkstra方法、A*方法以及Floyd方法。Dijkstra[14]是經(jīng)典的單源最短路徑查詢算法，查詢過程中需要進(jìn)行多次迭代運(yùn)算，每次迭代從候選集中選擇與源節(jié)點(diǎn)距離最短的節(jié)點(diǎn)作為訪問節(jié)點(diǎn)，直至候選集為空或候選集內(nèi)不存在需要計(jì)算最短路徑的節(jié)點(diǎn)。Dijkstra的缺點(diǎn)為查詢效率低下，因?yàn)樵摲椒ú恢滥繕?biāo)節(jié)點(diǎn)的位置，只能向所有可能的方向擴(kuò)展節(jié)點(diǎn)，直到發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)為止。為了克服Dijkstra算法效率低的缺點(diǎn)，文獻(xiàn)[15]提出了A*算法，A*算法[15]是改進(jìn)版的Dijkstra 算法，在Dijkstra 的基礎(chǔ)上，使用啟發(fā)式方法估計(jì)最短路徑的距離，在保證最優(yōu)性的同時(shí)，加入了目標(biāo)節(jié)點(diǎn)的信息，提高了搜索效率。Floyd 算法[16]是經(jīng)典的多源最短路徑查詢算法，可用于計(jì)算圖中所有節(jié)點(diǎn)對(duì)間的最短距離。道路網(wǎng)絡(luò)的規(guī)模很大，上述三種非索引算法通常需要數(shù)十秒才能回答大型道路網(wǎng)絡(luò)上的查詢，查詢速度不能滿足實(shí)際應(yīng)用。因此，為了提高查詢速度，產(chǎn)生了許多基于索引的查詢方法，CH（contraction hierarchies）[17]是基于層次的索引方法，通過為圖中每個(gè)節(jié)點(diǎn)分配等級(jí)確定節(jié)點(diǎn)的層次，基于層次預(yù)先計(jì)算節(jié)點(diǎn)與子集中節(jié)點(diǎn)間的最短距離，查詢時(shí)直接訪問以加快查詢速度。HL（hierarchical hub labelings）[18]是基于跳的索引方法，為每個(gè)節(jié)點(diǎn)分配2跳標(biāo)簽，查詢時(shí)只需要訪問源節(jié)點(diǎn)與目的節(jié)點(diǎn)標(biāo)簽內(nèi)的公共節(jié)點(diǎn)。H2H（hierarchical 2-hop）[10]是最新的基于索引的最短路徑查詢方法，彌補(bǔ)了上述兩種索引算法的缺點(diǎn)，能夠根據(jù)節(jié)點(diǎn)的層次選擇該節(jié)點(diǎn)的局部標(biāo)簽進(jìn)行最短距離查詢，進(jìn)一步加快了查詢速度。

時(shí)序道路網(wǎng)絡(luò)由文獻(xiàn)[19]第一次提出，時(shí)序道路網(wǎng)絡(luò)即將道路網(wǎng)絡(luò)建模為時(shí)序圖，與邊上權(quán)值是固定的靜態(tài)圖相比，時(shí)序圖邊上的權(quán)值是動(dòng)態(tài)的，會(huì)根據(jù)時(shí)間屬性產(chǎn)生相應(yīng)的變化。道路網(wǎng)絡(luò)是最典型的時(shí)序網(wǎng)絡(luò)，考慮到早晚高峰、交通堵塞等情況，在不同時(shí)間，通過同一條道路所需的旅行時(shí)間也是不同的。文獻(xiàn)[6]證明了時(shí)序道路網(wǎng)絡(luò)上的最短路徑查詢?cè)贔IFO網(wǎng)絡(luò)中是多項(xiàng)式可解的。文獻(xiàn)[20]證明了不具有先進(jìn)先出屬性的時(shí)序圖上的最短路徑查詢問題是NP難的。文獻(xiàn)[21]將Dijkstra推廣到具有隱式先進(jìn)先出屬性的時(shí)序圖中。A*算法[15]被擴(kuò)展為A*-like[22]后可用于時(shí)序路網(wǎng)上最短路徑查詢。CH[17]是靜態(tài)道路網(wǎng)絡(luò)中的層次加速技術(shù)，TCH（time dependent contraction hierarchies）[23]為CH 的改進(jìn)版，可以用于時(shí)序路網(wǎng)中最短路徑的查詢。高度平衡的樹結(jié)構(gòu)索引TD-G-tree[24]是最新回答時(shí)序道路網(wǎng)絡(luò)上最短路徑查詢的索引方法，雖然與TCH[23]相比TD-G-tree[24]的索引需要占據(jù)更多內(nèi)存，索引構(gòu)建時(shí)間也更長，但在查詢速度方面有了很大的提升。本文基于樹分解的概念，提出了可應(yīng)用于時(shí)序圖的時(shí)序樹分解算法，并在此基礎(chǔ)上提出了時(shí)序索引TD-H2H，該索引可以加快時(shí)序道路網(wǎng)絡(luò)上的最短路徑查詢，實(shí)驗(yàn)部分表明了其查詢效率優(yōu)于索引TD-G-tree[24]。

2 問題定義

一般來說，道路網(wǎng)絡(luò)上的通行速度和出發(fā)時(shí)間有關(guān)，在不同的時(shí)間通過同一條道路，需要的時(shí)間可能也是不同的。因此，為了更準(zhǔn)確地回答道路網(wǎng)絡(luò)上的最短路徑問題，本文將道路網(wǎng)絡(luò)建模為有向時(shí)序圖GT(V,E,F)，如圖1 所示，使用n=|V|以及m=|E|表示GT內(nèi)的節(jié)點(diǎn)數(shù)和邊數(shù)。對(duì)于GT內(nèi)的每個(gè)節(jié)點(diǎn)v∈V，使用dout(v)表示節(jié)點(diǎn)v的出度，din(v)表示節(jié)點(diǎn)v的入度。GT邊上的權(quán)重由函數(shù)表示，該函數(shù)使用時(shí)間變量t作為自變量，稱為時(shí)間函數(shù)。給定邊e=＜u,v>∈E，其對(duì)應(yīng)的時(shí)間函數(shù)fe(t)∈F表示在時(shí)刻t從節(jié)點(diǎn)u∈V出發(fā)，通過邊e=＜u,v>到達(dá)節(jié)點(diǎn)v∈V所需的時(shí)間是fe(t)。本文使用分段線性函數(shù)表示時(shí)間函數(shù)，S表示時(shí)間函數(shù)的段數(shù)，I表示插值點(diǎn)數(shù)。段數(shù)為S的時(shí)間函數(shù)需要I=S+1 個(gè)插值點(diǎn)來表示，如圖2所示，兩個(gè)段數(shù)S=2 的時(shí)間函數(shù)，需要使用I=3 個(gè)插值點(diǎn)來表示，分別為{(0,10),(30,20),(60,20)} 與{(0,15),(35,25),(60,40)}。后文中將通過時(shí)序圖中的邊以及路徑所需要的時(shí)間統(tǒng)稱為旅行時(shí)間。

圖1 時(shí)序圖GTFig.1 Time-dependent graph GT

在遍歷時(shí)序圖GT時(shí)，每個(gè)被訪問的節(jié)點(diǎn)v都存在一到達(dá)時(shí)間Arr(v) 與出發(fā)時(shí)間Dep(v) 。給定邊e=＜u,v>，有Arr(v)=Dep(u)+fe(Dep(u))，Dep(v)=Arr(v)，即節(jié)點(diǎn)v的到達(dá)時(shí)間等于節(jié)點(diǎn)u的出發(fā)時(shí)間與通過邊e=＜u,v>所需的旅行時(shí)間的和，v的出發(fā)時(shí)間等于其到達(dá)時(shí)間?；诠?jié)點(diǎn)的到達(dá)時(shí)間與出發(fā)時(shí)間可以對(duì)時(shí)序圖中路徑的旅行時(shí)間函數(shù)與最短旅行時(shí)間函數(shù)進(jìn)行定義，具體定義如下：

定義1（路徑的旅行時(shí)間函數(shù)）給定時(shí)序圖GT，邊e=＜u,v>。令出發(fā)時(shí)間為t，即Dep(u)=t。則e的到達(dá)時(shí)間函數(shù)為Arre(t)=Arr(v)=t+fe(t)；路徑P=＜e1,e2,…,eh-1,eh>的到達(dá)時(shí)間函數(shù)Arrp(t)為Arrp(t)=Arreh(Arreh-1(…(Arre1(t))…))；進(jìn)而，路徑p的旅行時(shí)間函數(shù)為Trvp(t)=Arrp(t)-t。

例1圖1為時(shí)序圖GT，圖2為GT中邊＜2,1>與邊＜1,6>上的時(shí)間函數(shù)圖。取Dep(2)=10，根據(jù)定義1，節(jié)點(diǎn)1 的到達(dá)時(shí)間以及出發(fā)時(shí)間分別為Arr(1)=Dep(1)=Dep(2)+f＜2,1>(Dep(2))，邊＜2,1>的到達(dá)時(shí)間Arr＜2,1>(10)=10+f＜2,1>(10)=Arr(1) 。對(duì)于路徑p={2,1,6}，給定Dep(2)=0，p的旅行時(shí)間為Trvp(0)=Arr＜1,6>(Arr＜2,1>(0))=Arr＜1,6>(10)。

圖2 時(shí)間函數(shù)Fig.2 Time functions

定義2（最短旅行時(shí)間函數(shù)）給定時(shí)序圖GT。出發(fā)時(shí)間為t時(shí)，從源節(jié)點(diǎn)s∈V到目的節(jié)點(diǎn)d∈V的最短旅行時(shí)間函數(shù)記為Trv*(s,d,t)，表示在t時(shí)刻從u出發(fā)到達(dá)v所需的最短時(shí)間。

時(shí)序圖中將節(jié)點(diǎn)間旅行時(shí)間最短的路徑定義為最短路徑。時(shí)序最短路徑查詢的定義如下：

定義3（時(shí)序最短路徑查詢）給定時(shí)序圖GT(V,E,F)，源節(jié)點(diǎn)s，目的節(jié)點(diǎn)d，以及出發(fā)時(shí)間t，時(shí)序最短路徑查詢表示為q(s,d,t)，返回出發(fā)時(shí)間為t時(shí)具有最短旅行時(shí)間Trv*(s,d,t)的路徑ps,d*。

例2如圖1 所示，GT中節(jié)點(diǎn)4、6 之間的路徑有{4,7,6}、{4,5,6}以及{4,8,5,6}。給定查詢q(4,6,10)，時(shí)序最短路徑查詢將返回在10 時(shí)刻出發(fā)時(shí)，節(jié)點(diǎn)4與節(jié)點(diǎn)6間具有最短旅行時(shí)間的最短路徑。

3 時(shí)序樹分解

樹分解[8]將圖分解為樹形結(jié)構(gòu)，通過研究樹分解的結(jié)構(gòu)信息可以加快圖中某些問題計(jì)算的速度。因此，本章在靜態(tài)圖上的樹分解方法的基礎(chǔ)上，提出了時(shí)序樹分解算法。

3.1 時(shí)序樹分解定義

時(shí)序樹分解的定義如下：

定義4（時(shí)序樹分解）時(shí)序圖GT(V,E,F)的時(shí)序樹分解表示為有根樹，其中每個(gè)節(jié)點(diǎn)X∈V()是集合V的子集（即X?V），使用X(r)表示TGt的根，滿足如下條件：

（1）GT的每個(gè)節(jié)點(diǎn)至少出現(xiàn)在的一個(gè)包內(nèi)；

（2）對(duì)于E中的每條邊e,e上的兩個(gè)節(jié)點(diǎn)至少同時(shí)出現(xiàn)在中的一個(gè)包內(nèi)；

（3）?v∈V，{X|v∈X}組成內(nèi)一個(gè)連接子樹T(v)，X(v)表示T(v)在內(nèi)的根，將v稱為X(v)的包頭節(jié)點(diǎn)，X(v)內(nèi)除v以外的節(jié)點(diǎn)稱為包內(nèi)節(jié)點(diǎn)。

（4）?v∈V，根據(jù)時(shí)序圖GT的結(jié)構(gòu)在X(v)內(nèi)保存包頭節(jié)點(diǎn)v與包內(nèi)節(jié)點(diǎn)u間的邊以及邊上的時(shí)間函數(shù)。

為了便于表述，后續(xù)將使用“節(jié)點(diǎn)”表示時(shí)序圖GT中的節(jié)點(diǎn)，使用“包”表示時(shí)序樹分解中的節(jié)點(diǎn)。

樹分解有兩個(gè)屬性，分別是樹寬和樹高：樹寬=max{|X||X∈}-1；樹高h(yuǎn)(TGt)=max{h(X)|X∈}，其中h(X)是指包X在內(nèi)的高度，即X到TG的根X(r)的距離。給定圖GT，根據(jù)定義4可以獲得多個(gè)樹寬不同的時(shí)序樹分解。假設(shè)具有最小樹寬的樹分解為Tmin，則有GT的樹寬w(GT)=w(Tmin)。將GT具有最小樹寬的樹分解Tmin定義為GT的最優(yōu)樹分解。判斷GT的樹寬是否大于給定值的問題是NP完全的[9]?，F(xiàn)有計(jì)算最優(yōu)樹分解的技術(shù)只能用于處理小圖（節(jié)點(diǎn)數(shù)量小于1 000圖）[12]。因此，為了能對(duì)時(shí)序圖進(jìn)行樹分解操作，且獲得較小的樹寬，本文將改進(jìn)文獻(xiàn)[13]提出的對(duì)靜態(tài)圖進(jìn)行樹分解的次優(yōu)方法。3.2節(jié)將給出算法細(xì)節(jié)以及詳細(xì)的算法說明。

3.2 時(shí)序樹分解構(gòu)建

現(xiàn)有的樹分解算法均用于計(jì)算靜態(tài)無向圖的樹分解，無法直接對(duì)時(shí)序有向圖進(jìn)行處理。時(shí)序樹分解需要計(jì)算并保存時(shí)序圖邊上的權(quán)值（時(shí)間函數(shù)），在給出時(shí)序樹分解的算法之前，首先介紹兩個(gè)處理時(shí)間函數(shù)方法，Com()方法[24]與Min()方法[24]，給定兩個(gè)時(shí)間函數(shù)fuw和fwv，兩個(gè)函數(shù)的插值點(diǎn)個(gè)數(shù)分別為Iuw與Iwv，Com()方法返回將這兩個(gè)函數(shù)復(fù)合后得到的新的時(shí)間函數(shù)fuv，即fuv=Com(fuw,fwv)，Com()方法的時(shí)間復(fù)雜度為α=O(Iuw+Iwv)；與作用于三個(gè)節(jié)點(diǎn)間的兩個(gè)時(shí)間函數(shù)上的Com()方法不同，Min()方法作用于同一對(duì)節(jié)點(diǎn)間的兩個(gè)時(shí)間函數(shù)上，給定時(shí)間函數(shù)fuv和,fuv的插值點(diǎn)個(gè)數(shù)為Iuv,的插值點(diǎn)個(gè)數(shù)為，且兩個(gè)函數(shù)的交叉點(diǎn)個(gè)數(shù)為C，Min()方法返回在所有出發(fā)時(shí)間t下旅行時(shí)間都較小的新的時(shí)間函數(shù)，即=Min(fuv,)，Min()方法的時(shí)間復(fù)雜度為β=O(Iuv++C)。

構(gòu)建時(shí)序樹分解的方法包括兩個(gè)步驟：第一步是創(chuàng)建包，給定時(shí)序圖GT并運(yùn)行|V(G)|次迭代，為了生成樹寬盡可能小的樹分解，每次迭代又由兩個(gè)小步驟組成。步驟1是每次迭代都選擇GT中度數(shù)最小的節(jié)點(diǎn)u，并且使用u和u在GT中的所有鄰居N(u,G) 創(chuàng)建包X(u)，其中u為X(u) 的包頭節(jié)點(diǎn)，N(u,G)內(nèi)的節(jié)點(diǎn)均為X(u)的包內(nèi)節(jié)點(diǎn)。步驟2為在u的每對(duì)未連接的鄰居節(jié)點(diǎn)對(duì)間加入邊，并從G中刪除節(jié)點(diǎn)u以及所有與u相連的邊。步驟2 又可以被稱為時(shí)序節(jié)點(diǎn)消除操作，具體過程如算法1所示。

算法1時(shí)序節(jié)點(diǎn)消除算法

輸入：GT(V,E,F)，v∈V。

輸出：GT?v。

給定時(shí)序圖GT以及節(jié)點(diǎn)v，算法1訪問所有與v相連的邊，如果v在GT內(nèi)有邊＜u,v>和＜v,w>（1行），使用Com()方法構(gòu)建u和w間以v為中轉(zhuǎn)節(jié)點(diǎn)的邊＜u,w>以及時(shí)間函數(shù)=Com(fuv,fvw)（2 行），如果GT中u和w間沒有邊（3行），插入邊＜u,w>并將邊權(quán)重賦值為（4行），反之，如果u和w間有邊使用Min()方法更新邊權(quán)重（5～6 行），從H中刪除節(jié)點(diǎn)v以及所有與v相連的邊（8 行），最后返回完成時(shí)序節(jié)點(diǎn)消除操作的圖GT?v（9行）。

算法1 的時(shí)間復(fù)雜度為O(dout(v)×din(v)×(α+β))，即O(w2×(α+β))，其中dout(v)與din(v)分別為節(jié)點(diǎn)v在圖GT內(nèi)的出度和入度，α與β分別為Com()與Min()方法的時(shí)間復(fù)雜度，w為樹寬。

根據(jù)上述的算法過程可以得出一個(gè)結(jié)論，給定時(shí)序圖GT(V,E,F) 以及GT?v=(Vd,Ed,Fd)，那么Vd?V，并且對(duì)于Vd中任意一對(duì)節(jié)點(diǎn)u和v，這對(duì)節(jié)點(diǎn)間的最短旅行時(shí)間等于V中u和v間的最短旅行時(shí)間，本文中將具有這種特性的圖叫作派生子圖，即是GT的派生子圖。

創(chuàng)建的第二步是連接包。連接過程所遵行的準(zhǔn)則是：若節(jié)點(diǎn)v是節(jié)點(diǎn)u第一個(gè)被移除的鄰居，則將X(v)設(shè)置為X(u)在TG內(nèi)的父包。與靜態(tài)樹分解相同，時(shí)序樹分解也有創(chuàng)建與連接包兩個(gè)過程。不同的是使用算法1 來創(chuàng)建包，且的每個(gè)包X(v)中不僅保存節(jié)點(diǎn)，如果存在邊＜v,u>，還需要保存＜v,u>以及時(shí)間函數(shù)fvu(t)。時(shí)序樹分解的具體過程如算法2所示。

算法2時(shí)序樹分解算法

輸入：GT(V,E,F)。

輸出：。

給定時(shí)序圖GT。算法2 首先將賦值為空（1行）。接著進(jìn)行創(chuàng)建包的操作（2～14行），每次選擇GT中度數(shù)最小的節(jié)點(diǎn)v（3 行），將節(jié)點(diǎn)v設(shè)置為包X(v)的包頭節(jié)點(diǎn)（4 行），遍歷v在GT中的每個(gè)鄰居u（5行），如果GT中存在邊＜v,u>（6 行），將節(jié)點(diǎn)u加入到包X(v)的out鄰居集合中并且保存邊＜v,u>上的時(shí)序函數(shù)（7～8行）。同理，如果GT中存在邊＜u,v>，將節(jié)點(diǎn)u加入到包X(v)的in鄰居集合中并且保存邊＜u,v>上的時(shí)序函數(shù)（9～11）行。使用算法1從GT中消除v（12 行），之后記錄包X(v)的創(chuàng)建次序i（13行）。所有的包都創(chuàng)建完畢后，將已創(chuàng)建的包連接起來以形成樹結(jié)構(gòu)（15～19 行）。最后返回生成的時(shí)序樹分解（20行）。

算法2的時(shí)間復(fù)雜度為O(n×(w+w2))=O(n×w2)，其中O(w2)為時(shí)序節(jié)點(diǎn)消除操作的時(shí)間復(fù)雜度。內(nèi)的樹節(jié)點(diǎn)數(shù)等于GT內(nèi)的圖節(jié)點(diǎn)數(shù)n，每個(gè)樹節(jié)點(diǎn)內(nèi)包含的邊數(shù)上限為2(w-1)。因此，算法2 的空間復(fù)雜度為O(n×2(w-1)×I)=O(n×w×I)，其中I為時(shí)序圖GT中時(shí)間函數(shù)的平均插值點(diǎn)數(shù)。

例3圖3 展示了圖1 中時(shí)序圖GT的時(shí)序樹分解，中每個(gè)包內(nèi)陰影里的節(jié)點(diǎn)是包頭節(jié)點(diǎn)，其余節(jié)點(diǎn)是包內(nèi)節(jié)點(diǎn)，每個(gè)包內(nèi)的箭頭表明了包內(nèi)節(jié)點(diǎn)與包頭節(jié)點(diǎn)的關(guān)系。在構(gòu)建時(shí)，首先選擇GT中度數(shù)最小的節(jié)點(diǎn)1，1的鄰居集為{2,6}，其中節(jié)點(diǎn)2為節(jié)點(diǎn)1的in鄰居，將節(jié)點(diǎn)2添加到節(jié)點(diǎn)1的in鄰居集合中，保存時(shí)序函數(shù)f21，同理將節(jié)點(diǎn)6添加到節(jié)點(diǎn)1的out鄰居集合中并且保存時(shí)間函數(shù)f16。GT中存在邊＜2,1>與＜1,6>，從節(jié)點(diǎn)2 出發(fā)可以通過節(jié)點(diǎn)1 到達(dá)節(jié)點(diǎn)6，因此對(duì)節(jié)點(diǎn)1進(jìn)行時(shí)序節(jié)點(diǎn)消除時(shí)，需要在GT中插入邊＜2,6>，邊上的時(shí)間函數(shù)通過Com()操作得到f26=Com(f21,f16)。表1 展示了中所有包的鄰居集，除了樹分解的根X(8)的兩個(gè)鄰居集都為空之外，其余的包至少有一個(gè)in鄰居集或out鄰居集。

圖3 時(shí)序樹分解TGtFig.3 Time-dependent tree decomposition TGt

表1 的鄰居集Table 1 Neighbor sets of

表1 的鄰居集Table 1 Neighbor sets of

4 時(shí)序索引

4.1 TD-H2H

現(xiàn)實(shí)生活中，道路網(wǎng)絡(luò)的規(guī)模很大，建模為時(shí)序圖后其結(jié)構(gòu)也更為復(fù)雜，直接求解大規(guī)模時(shí)序圖上的最短路徑問題難度很高，且其效率不足以支持實(shí)際的應(yīng)用。因此，索引是必須的。為了理解TD-H2H索引的原理，首先需要明確點(diǎn)割集的概念。

定義5（點(diǎn)割集）給定時(shí)序圖GT(V,E,F)，節(jié)點(diǎn)集C?V，從圖G中刪除C會(huì)將圖GT劃分為多個(gè)連接子圖，如果節(jié)點(diǎn)u和v存在于不同的子圖中，那么C被稱為u和v的點(diǎn)割集。

給定源節(jié)點(diǎn)s和目的節(jié)點(diǎn)d間的點(diǎn)割集C，s與d間的所有路徑都至少會(huì)通過C中的一個(gè)節(jié)點(diǎn)c[10]。s與d間的點(diǎn)割集并不是唯一的，因此，如果能夠提前確定s和d間一個(gè)較小的點(diǎn)割集C，并且預(yù)計(jì)算并保存從s到c的最短旅行時(shí)間函數(shù)，以及由c到d的最短旅行時(shí)間函數(shù)，查詢時(shí)直接調(diào)用已保存的時(shí)間函數(shù)可以大大提高時(shí)序最短路徑的查詢效率?，F(xiàn)在需要考慮的問題是，給定節(jié)點(diǎn)u和v后，如何確定節(jié)點(diǎn)間的點(diǎn)割集，并且保證這個(gè)點(diǎn)割集的大小是可以接受的。文獻(xiàn)[25]給出的樹分解的點(diǎn)割集性質(zhì)可以回答此問題。

性質(zhì)1[25]給定時(shí)序圖GT(V,E,F)的時(shí)序樹分解，以及V中任意兩個(gè)節(jié)點(diǎn)u和v，假設(shè)X(u)不是X(v)在內(nèi)的祖先或后代，并且令X是X(u)和X(v)在內(nèi)的最小公共祖先，則X內(nèi)的節(jié)點(diǎn)是u和v在GT內(nèi)的一個(gè)點(diǎn)割集。

首先，算法2可以將路網(wǎng)轉(zhuǎn)換為具有低樹寬的樹分解[10]，由性質(zhì)1 可知將圖轉(zhuǎn)換為樹分解結(jié)構(gòu)后，根據(jù)該樹結(jié)構(gòu)可以確定節(jié)點(diǎn)間的點(diǎn)割集并且所有點(diǎn)割集的大小都小于等于樹寬?；诖?，本文將道路網(wǎng)絡(luò)建模為時(shí)序圖后，生成該圖的時(shí)序樹分解，并在該樹分解的基礎(chǔ)上構(gòu)建TD-H2H索引。

祖先數(shù)組可以加快索引的構(gòu)建過程，是構(gòu)建TDH2H索引的基石。給定時(shí)序圖GT(V,E,F)的時(shí)序樹分解TGt，對(duì)于中的每個(gè)包X(v)，都存在從根節(jié)點(diǎn)X(r)到節(jié)點(diǎn)X(v)的路徑{X(w1),X(w2),…,X(wl)}，其中X(w1)是X(r),X(wl)是X(v)。使用X(v).anc表示X(v)的祖先數(shù)組，即X(v).anc={w1,w2,…,wl}，X(v).anc[i]表示數(shù)組中的第i個(gè)元素(1 ≤i≤l)。祖先數(shù)組中各個(gè)元素必須按包頭節(jié)點(diǎn)在樹分解中由上至下的順序存放，保證排在前面的元素是后面元素在內(nèi)的祖先。根節(jié)點(diǎn)X(r)的祖先數(shù)組只有r一個(gè)元素，其他包的祖先數(shù)組至少有兩個(gè)元素，即r和v。

給定時(shí)序樹分解以及每個(gè)包X(v)∈V()在內(nèi)的祖先數(shù)組X(v).anc，本文會(huì)為每個(gè)X(v)計(jì)算并保存旅行時(shí)間函數(shù)表X(v).trv作為TD-H2H 索引，該索引使用哈希表來存儲(chǔ)。根據(jù)算法2，?X(v)∈V()中都有兩類邊，分別是out邊與in邊。相應(yīng)的，X(v)的旅行時(shí)間函數(shù)表X(v).trv也分為兩類，分別是X(v).trvout與X(v).trvin表。如果GT內(nèi)存在從包頭節(jié)點(diǎn)v到X(v).anc中節(jié)點(diǎn)w的路徑，則X(v).trvout中保存從節(jié)點(diǎn)v到節(jié)點(diǎn)w的最短旅行時(shí)間函數(shù)X(v).trvout[w]=Trvvw*(t)。如果GT內(nèi)存在從X(v).anc中節(jié)點(diǎn)w到包頭節(jié)點(diǎn)v的路徑，那么在X(v).trvin中保存從節(jié)點(diǎn)w到節(jié)點(diǎn)v的最短旅行時(shí)間函數(shù)X(v).trvin[w]=Trvwv*(t)。給定時(shí)序樹分解以及每個(gè)包X(v)∈V()在內(nèi)的祖先數(shù)組，在為X(v)計(jì)算旅行時(shí)間表之前，需要為X(v)計(jì)算并保存位置數(shù)組X(v).pos。與旅行時(shí)間函數(shù)表相同，位置數(shù)組也分為兩類，分別為X(v).posout和X(v).posin數(shù)組。位置數(shù)組顧名思義是由包X(v)的包內(nèi)節(jié)點(diǎn)在X(v).anc中的位置組成的數(shù)組，X(v).posout中保存X(v)的out鄰居集中的節(jié)點(diǎn)在X(v).anc中的位置，X(v).posin中保存X(v)的in鄰居集中的節(jié)點(diǎn)在X(v).anc中的位置。TD-H2H的具體構(gòu)建過程將在4.2節(jié)中詳述。在構(gòu)建的位置數(shù)組時(shí)默認(rèn)使用了樹分解的一個(gè)性質(zhì)，即對(duì)于內(nèi)的每個(gè)包X(v)來說，若u為X(v)的包內(nèi)節(jié)點(diǎn)，那么X(u)是X(v)在內(nèi)的祖先，具體內(nèi)容如下：

性質(zhì)2[10]給定時(shí)序圖GT(V,E,F)，其樹分解以及任意包X(u)∈，對(duì)于任意節(jié)點(diǎn)v∈X(u)/u，X(v)是X(u)在內(nèi)的祖先。

除祖先數(shù)組的構(gòu)建需要性質(zhì)2的支持外，旅行時(shí)間函數(shù)表的構(gòu)建也與性質(zhì)2 有關(guān)，前文已經(jīng)說明了TD-H2H 需要提前存儲(chǔ)源節(jié)點(diǎn)s與點(diǎn)割集C中節(jié)點(diǎn)以及點(diǎn)割集C中節(jié)點(diǎn)與目的節(jié)點(diǎn)d間的最短旅行時(shí)間函數(shù)。根據(jù)性質(zhì)1，X(s)與X(d)的在內(nèi)最小公共祖先X中的節(jié)點(diǎn)就是s與d間的點(diǎn)割集。由此可以得出：對(duì)GT中任一節(jié)點(diǎn)u與其他節(jié)點(diǎn)v，如果X(u)不是X(v)在內(nèi)的祖先或后代，那么u與v間的點(diǎn)割集一定是X(u)的祖先，且根據(jù)性質(zhì)2，以X(u)的包內(nèi)節(jié)點(diǎn)v為包頭節(jié)點(diǎn)的X(v)一定是X(u)的祖先。因此，只要提前保存好X(u) 的兩個(gè)旅行時(shí)間函數(shù)表X(u).trvout與X(u).trvin，就已經(jīng)保存了節(jié)點(diǎn)u與點(diǎn)割集C中每個(gè)節(jié)點(diǎn)c間的最短旅行時(shí)間函數(shù)。如果X(u)是X(v)在內(nèi)的祖先或后代，不需要計(jì)算u和v間的點(diǎn)割集，根據(jù)已保存的旅行時(shí)間函數(shù)表可以直接進(jìn)行最短旅行時(shí)間的計(jì)算。因?yàn)槿绻鸛(u)是X(v)的祖先，那么從u到v的最短旅行時(shí)間函數(shù)已經(jīng)提前保存在節(jié)點(diǎn)v的in旅行時(shí)間表中，即X(v).trvin[u]；如果X(v)是X(u)的祖先，那么從u到v的最短旅行時(shí)間函數(shù)已經(jīng)提前保存在節(jié)點(diǎn)u的out旅行時(shí)間表中，X(u).trvout[v]。綜上所述，計(jì)算節(jié)點(diǎn)u到v的最短路徑時(shí)只需要訪問已經(jīng)提前存儲(chǔ)的u的out旅行時(shí)間表與v的in旅行時(shí)間表，又因?yàn)槁眯袝r(shí)間表的大小一定小于等于樹寬，并且道路網(wǎng)絡(luò)可以分解為具有低樹寬的樹分解[10]，所以，基于時(shí)序樹分解構(gòu)建的索引TDH2H可以大大加快時(shí)序圖上的最短路徑查詢速度。

例4如圖3 所示，X(3)與X(5)的最小公共祖先是X(4)={8,7,6,4}，且在圖1的GT中，C={8,7,6,4}是節(jié)點(diǎn)3 與5 間的點(diǎn)割集。X(9)={4,2,9}，而且X(4)和X(2)均為X(9)在的祖先。表2展示了圖3中的祖先數(shù)組與位置數(shù)組。X(3)={4,2,9,3}的祖先數(shù)組為X(3).anc={8,7,6,4,2,9,3}，節(jié)點(diǎn)8是X(3).anc中其他所有節(jié)點(diǎn)在中的祖先，節(jié)點(diǎn)7是X(3).anc中除了節(jié)點(diǎn)8 外所有節(jié)點(diǎn)在中的祖先，且X(3)?X(3).anc。X(3).posin={4,6}，說明X(3)的in鄰居集中的第一個(gè)元素4在X(3).anc中的第4 個(gè)位置，in鄰居集中的第2個(gè)元素9在X(3).anc中的第6 個(gè)位置；同理可得X(3).posout={5}說明X(3)的out鄰居集中的唯一一個(gè)元素2在X(3).anc中的第5 個(gè)位置。如表1 所示，X(4)的out鄰居集為空，因此，在表2中X(4).posout中的元素也為空。表3展示了圖3中的旅行時(shí)間表，對(duì)于中的任意節(jié)點(diǎn)X(v)，X(v)的in和out旅行時(shí)間表中至少會(huì)保存到自身包頭節(jié)點(diǎn)v的旅行時(shí)間函數(shù)，本文中將到自身包頭節(jié)點(diǎn)的旅行時(shí)間函數(shù)值設(shè)置為0。如圖1 中的GT所示，X(9).anc={8,7,6,4,2,9}中除了節(jié)點(diǎn)9外，其余節(jié)點(diǎn)在GT都不存在到達(dá)節(jié)點(diǎn)9的路徑，但是從節(jié)點(diǎn)9 出發(fā)可以到達(dá)X(9).anc中的每個(gè)節(jié)點(diǎn)。因此，在X(9)的in旅行時(shí)間函數(shù)表中僅保存了到自身的旅行時(shí)間函數(shù)，out旅行時(shí)間函數(shù)表中保存9 到所有祖先節(jié)點(diǎn)的最短旅行時(shí)間函數(shù)。因?yàn)閄(8)為的根，所以其in和out旅行時(shí)間表中都只保存了到自身的旅行時(shí)間函數(shù)。

表2 的祖先數(shù)組與位置數(shù)組Table 2 Ancestor and position arrays of

表2 的祖先數(shù)組與位置數(shù)組Table 2 Ancestor and position arrays of

表3 的旅行時(shí)間表Table 3 Travel time tables of

表3 的旅行時(shí)間表Table 3 Travel time tables of

4.2 索引構(gòu)建

本節(jié)給出索引TD-H2H的構(gòu)建細(xì)節(jié)，并詳細(xì)說明如何基于時(shí)序樹分解的性質(zhì)以及位置數(shù)組設(shè)計(jì)高效的索引構(gòu)建算法。

給定時(shí)序圖GT(V,E,F)，在構(gòu)建時(shí)序樹分解時(shí)使用算法1 進(jìn)行時(shí)序節(jié)點(diǎn)消除，且在內(nèi)會(huì)保存包頭節(jié)點(diǎn)與包內(nèi)節(jié)點(diǎn)的時(shí)間函數(shù)。因此，對(duì)于V中每個(gè)節(jié)點(diǎn)v，X(v).anc={w1,w2,w3} 中的節(jié)點(diǎn)和X(w1)、X(w2)以及X(w3)內(nèi)的邊組成的圖G(v)T(Vd,Ed,Fd)是GT的派生子圖，即Vd?V，并且對(duì)于Vd中任意一對(duì)節(jié)點(diǎn)u和w，這對(duì)節(jié)點(diǎn)間的最短旅行時(shí)間等于V中u和w間的最短旅行時(shí)間。如果X(u)是X(v)在內(nèi)的祖先，那么G(u)T是G(v)T的子圖。

例5根據(jù)圖3 的時(shí)序樹分解，可以得到圖4中的兩個(gè)派生子圖G(1)與G(2)。其中，G(2)中的節(jié)點(diǎn)與X(2).anc中的節(jié)點(diǎn)一致，G(2) 中的邊與包X(2)、X(4)、X(6)以及X(7)中的邊一致。因?yàn)閄(2)是X(1)的祖先，相對(duì)的G(2)是G(1)的子圖。

圖4 派生子圖G(v)Fig.4 Derive subgraph G(v)

基于時(shí)序樹分解的派生子圖性質(zhì)有如下結(jié)論：

給定時(shí)序樹分解以及內(nèi)包X(v)，對(duì)于任意1 ≤i＜|X(v).anc|，1 ≤j≤|X(v).outN|，1 ≤k≤|X(v).inN|(X(v).outN為包頭節(jié)點(diǎn)v在包X(v)內(nèi)的out鄰居集，X(v).inN為in鄰居集）有：

上述結(jié)論說明在求解X(v)的out旅行時(shí)間表時(shí)，需要逐一訪問X(v).anc中的節(jié)點(diǎn)w。如果X(v)的out鄰居集中有能到達(dá)w的節(jié)點(diǎn)u，則通過Com()方法計(jì)算出v與w間的旅行時(shí)間函數(shù)Trvv,w(t)。如果存在不只一個(gè)節(jié)點(diǎn)v可以到達(dá)w，需要使用Com()方法計(jì)算出所有v與w間的旅行時(shí)間函數(shù)Trvv,w(t)。將計(jì)算出的時(shí)間函數(shù)Trvv,w(t)依次帶入到Min()方法中，得到從v到w的最短旅行時(shí)間函數(shù)Trvv,w(t)*。同理可得X(v)的in旅行時(shí)間表。相關(guān)證明如下：

證明因?yàn)镚T(v)是包含X(v).anc中全部節(jié)點(diǎn)的圖，且GT(v)是GT的派生子圖，所以GT中從v到X(v).anc[i]的最短旅行時(shí)間函數(shù)等于GT(v)中從v到X(v).anc[i]的最短旅行時(shí)間函數(shù)。又因?yàn)閄(v)/v是節(jié)點(diǎn)v在GT(v)中鄰居的集合，從節(jié)點(diǎn)v到X(v).anc中的任何一個(gè)節(jié)點(diǎn)間的路徑都至少會(huì)經(jīng)過v的一個(gè)鄰居。因此，基于樹分解中每個(gè)包內(nèi)保存的圖節(jié)點(diǎn)以及時(shí)間函數(shù)可以計(jì)算出正確的旅行時(shí)間函數(shù)表。

綜上所述，給定時(shí)序圖GT以及其樹分解，對(duì)于內(nèi)的每個(gè)包X(v)，計(jì)算旅行時(shí)間表時(shí)都隱式構(gòu)建了圖G(v)T，進(jìn)而在G(v)T上計(jì)算旅行時(shí)間表。當(dāng)X(u)是X(v)在內(nèi)的祖先時(shí)，G(u)T是G(v)T的子圖。因此，如果在構(gòu)建中每個(gè)包的旅行時(shí)間表時(shí)采用由上至下的遍歷方式，在創(chuàng)建X(v)的旅行時(shí)間表時(shí)可以重用已計(jì)算完成的X(u)的索引信息。

對(duì)于任意1 ≤i＜|X(v).anc|以及1 ≤j≤|X(v).outN|，如果通過X(v).outN[j] 可以到達(dá)X(v).anc[i]，計(jì)算X(v).trvout[X(v).anc[i]]時(shí)，需要已知Trv*(X(v).outN[j],X(v).anc[i])的值，考慮如下情況：

（1）X(v).posout[j]>i，即X(v).outN[j]在X(v).anc中排在X(v).anc[i]的后面，在這種情況下，X(X(v).anc[i])是X(X(v).outN[j])在內(nèi)的祖先，有：

（2）X(v).posout[j]≤i，即X(v).outN[j]在X(v).anc中排在X(v).anc[i]的前面，在這種情況下，X(X(v).outN[j])是X(X(v).anc[i])在內(nèi)的祖先，有：

X(X(v).outN[j])與X(X(v).anc[i])都是X(v) 的祖先并且采用由上至下的方式計(jì)算內(nèi)每個(gè)包的旅行時(shí)間表，因此，在計(jì)算X(v) 的旅行時(shí)間表時(shí)，X(X(v).outN[j])與X(X(v).anc[i])的旅行時(shí)間表都已經(jīng)計(jì)算完成，計(jì)算X(v).trvout時(shí)可以直接調(diào)用以加速索引的構(gòu)建過程。同理可得，對(duì)于任意1 ≤i＜|X(v).anc|以及1 ≤k≤|X(v).inN|，如果X(v).anc[i]可以到達(dá)X(v).inN[k]，計(jì)算X(v).trvin[X(v).anc[i]]時(shí)，需要已知Trv*(X(v).anc[i]，X(v).inN[k])的值，考慮如下兩種情況：

（1）X(v).posin[k]>i，即X(v).inN[k]在X(v).anc中排在X(v).anc[i]的后面，在這種情況下，X(X(v).anc[i])是X(X(v).inN[k])在內(nèi)的祖先，有：

（2）X(v).posin[k]≤i，即X(v).inN[k]在X(v).anc中排在X(v).anc[i]的前面，在這種情況下，X(X(v).inN[k])是X(X(v).anc[i])在內(nèi)的祖先，有：

TD-H2H索引的構(gòu)建原理與方式如上文所述，下文分別給出創(chuàng)建out旅行時(shí)間表的算法GetOutTrv與創(chuàng)建TD-H2H 索引的算法，創(chuàng)建in旅行時(shí)間表的算法GetInTrv與GetOutTrv相似，不再具體說明。

算法3GetOutTrv

輸入:、v。

輸出:X(v).trvout。

算法3 生成X(v)的trvout旅行時(shí)間表。依次遍歷祖先數(shù)組X(v).anc中的每個(gè)節(jié)點(diǎn)（1 行），將每個(gè)X(v).trvout[X(v).anc[i]]的初值賦值為任何時(shí)間出發(fā)旅行時(shí)間都為無窮大的fmax函數(shù)（2 行），訪問X(v)在out鄰居集中的元素X(v).outN[j]，依次計(jì)算X(v).trvout[X(v).anc[i]]（3～13行）。將節(jié)點(diǎn)到本身的旅行時(shí)間函數(shù)設(shè)置為旅行時(shí)間為0的fmin函數(shù)（15 行），最后返回節(jié)點(diǎn)v的trvout表（17行）。

算法3 在3～14 行的時(shí)間復(fù)雜度為O(w×(α+β))，且總的循環(huán)次數(shù)以的樹高h(yuǎn)為上界。因此，算法3的時(shí)間復(fù)雜度為O(h×w×(α+β))。

算法4創(chuàng)建TD-H2H索引

輸入：GT(V,E,F)。

輸出：TD-H2H。

算法4 首先調(diào)用算法1 構(gòu)建時(shí)序樹分解（1行），接著由上至下逐一訪問中的包X(v)（2～11行）。分別計(jì)算X(v)的位置數(shù)組X(v).posout（3～5行）與X(v).posin（6～8 行）。接著調(diào)用算法3GetOutTrv()與算法GetInTrv()計(jì)算X(v)的trv旅行時(shí)間表（9～10行），最后返回每個(gè)節(jié)點(diǎn)v的trvout和trvin表，即TD-H2H索引（12行）。TD-H2H索引的大小是以的樹寬與樹高為界的，道路網(wǎng)絡(luò)可以分解為低樹高與低樹寬的樹分解[10]，因此，對(duì)于現(xiàn)實(shí)世界中的大型道路網(wǎng)絡(luò)來說，TD-H2H是可行的。

構(gòu)建時(shí)序樹分解的時(shí)間復(fù)雜度為O(n×w2)，計(jì)算位置數(shù)組的時(shí)間復(fù)雜度為O(w×h)。因此，算法4時(shí)間復(fù)雜度為O(n×(w2+h×w×(α+β)))=O(n×h×w×(α+β)) 。算法4的空間復(fù)雜度為O(n×h×I)。

5 時(shí)序最短路徑查詢

本章說明如何基于TD-H2H 索引設(shè)計(jì)高效的進(jìn)行時(shí)序最短路徑查詢的TD-OAI算法。

由上文可知，給定時(shí)序圖GT(V,E,F) 的樹分解、TD-H2H 索引以及查詢q(s,d,t)，首先基于性質(zhì)1獲得s與d之間的點(diǎn)割集X，X為X(s)與X(d)在內(nèi)的最小公共祖先。接著因?yàn)閄(s).trvout中已經(jīng)保存了所有從s到X(s).anc中可達(dá)節(jié)點(diǎn)的最短旅行時(shí)間函數(shù)，X(d).trvin中保存了X(d).anc中可以到達(dá)d的節(jié)點(diǎn)到d的最短旅行時(shí)間函數(shù)，根據(jù)性質(zhì)2 可得X?X(s).anc且X?X(d).anc，即假設(shè)x為X中的節(jié)點(diǎn)，如果存在這樣的x:X(s).trvout中保存了從s到x的最短旅行時(shí)間函數(shù)，且X(d).trvin中保存了從x到d的最短旅行時(shí)間函數(shù)。說明GT中有從s到d的路徑，使用X(s).trvout[x]和X(d).trvin[x]可以計(jì)算出從s出發(fā)經(jīng)過節(jié)點(diǎn)x到達(dá)d需要的最短時(shí)間Trvs,d(t)。如果X中存在不只一個(gè)滿足上述條件的x，則需要分別計(jì)算對(duì)應(yīng)的Trvs,d(t)，其中最小的Trvs,d(t)即為從s到d在時(shí)間t出發(fā)需要的最短旅行時(shí)間，所對(duì)應(yīng)的路徑為最短路徑。具體過程如算法5所示。

算法5TD-OAI

輸入：、TD-H2H、q(s,d,t)。

輸出：。

給定查詢q(s,d,t)，算法5 首先確定X(s)與X(d)在內(nèi)的最小公共祖先X（1 行），將最小旅行時(shí)間minTrv的初值賦值為最大值。然后根據(jù)X內(nèi)的元素訪問X(s)的out旅行時(shí)間函數(shù)表X(s).trvout與X(d)的in旅行時(shí)間函數(shù)表X(d).trvin來回答查詢q（3～10行），迭代次數(shù)等于X中元素?cái)?shù)量。迭代前判斷X[i]是否是s與d間的中轉(zhuǎn)節(jié)點(diǎn)（5 行），是則計(jì)算新的旅行時(shí)間（6～7行），若新的旅行時(shí)間小于已獲得的最短旅行時(shí)間（8行），則進(jìn)行最短旅行時(shí)間的更新（9行），最后返回minTrv（11 行）。注意，算法5 只給出了最小公共祖先X既不是X(s)也不是X(d)的情況，當(dāng)最小公共祖先為X(s)或X(d)時(shí)，s與d間的最短旅行時(shí)間函數(shù)已經(jīng)保存為X(s).trvout[d]或X(d).trvin[s]，不再需要中轉(zhuǎn)節(jié)點(diǎn)，直接調(diào)用函數(shù)就可以計(jì)算出s與d之間的最短旅行時(shí)間。

算法5 的時(shí)間復(fù)雜度為O(w×lbS)，其中S為時(shí)間函數(shù)的平均段數(shù)，O(lbS)為使用二分法在段數(shù)為S的時(shí)間函數(shù)內(nèi)查找指定出發(fā)時(shí)間t所在函數(shù)段的時(shí)間復(fù)雜度。

例6如圖3 所示，給定時(shí)序圖GT、時(shí)序樹分解、TD-H2H索引以及查詢q(1,5,0)，首先確定X(1)與X(5)在內(nèi)的最小公共祖先X(4)={8,7,6,4}，根據(jù)X(4)中的元素訪問X(1)的out旅行時(shí)間表與X(5)的in旅行時(shí)間表。如表3所示，X(4)中沒有元素共同存在于X(1).trvout與X(5).trvin中，因此從節(jié)點(diǎn)1 不能到達(dá)節(jié)點(diǎn)5。給定查詢q(9,5,8)，X(9)與X(5)在內(nèi)的最小公共祖先X(4)={8,7,6,4}，X(4)中元素8、7 和4 共同存在于X(9).trvout與X(5).trvin中，分別計(jì)算trv=X(9).trvout[8](8)+X(5).trvin[8](8+X(9).trvout[8](8))，trv=X(9).trvout[7](8)+X(5).trvin[8](8+X(9).trvout[7](8))，trv=X(9).trvout[4](8)+X(5).trvin[8](8+X(9).trvout[4](8))。其中值最小的trv就是查詢q(9,5,10)的結(jié)果，即出發(fā)時(shí)間為8時(shí)，從節(jié)點(diǎn)9出發(fā)到達(dá)節(jié)點(diǎn)5所需要的最短時(shí)間。

6 實(shí)驗(yàn)

6.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)環(huán)境：所有算法都使用C++實(shí)現(xiàn)；操作系統(tǒng)是Linux；CPU為Intel 2.20 GHz；內(nèi)存128 GB。

比較算法：TD-Dijkstra[21]是基于Dijkstra[14]擴(kuò)展而來的非索引算法，可以用于時(shí)序道路網(wǎng)絡(luò)上的最短路徑查詢；TD-G-tree[24]是最新的用于最短路徑查詢的時(shí)序索引。為說明構(gòu)建索引的必要性以及本文算法的有效性，將TD-H2H索引與TD-G-tree相比較，與TD-Dijkstra 以及基于TD-G-tree 構(gòu)建的查詢算法TDSP[24]比較TD-OAI的查詢效率。

實(shí)驗(yàn)數(shù)據(jù)：如表4 所示，本文使用4 個(gè)真實(shí)世界的道路網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。本文基于原始數(shù)據(jù)集上的靜態(tài)權(quán)重生成時(shí)間函數(shù)，獲得時(shí)序圖。實(shí)驗(yàn)時(shí)采用86 400 s的時(shí)間閾值，隨機(jī)從數(shù)據(jù)集中選取1 000對(duì)源節(jié)點(diǎn)與目的節(jié)點(diǎn)，并為其分配10 個(gè)不同的時(shí)間點(diǎn)作為出發(fā)時(shí)間以生成查詢文件。每次實(shí)驗(yàn)都會(huì)進(jìn)行10 000次最短路徑查詢，統(tǒng)計(jì)平均查詢時(shí)間。

表4 數(shù)據(jù)集Table 4 Datasets

6.2 查詢效率評(píng)估

本節(jié)從三方面評(píng)估TD-OAI的查詢效率，查詢結(jié)果與TD-Dijkstra以及TDSP進(jìn)行比較。

（1）有效性測(cè)試：首先測(cè)試TD-OAI的有效性，有效性測(cè)試是指直接在由真實(shí)數(shù)據(jù)集建模得到的4 個(gè)時(shí)序圖上運(yùn)行3 個(gè)查詢算法，進(jìn)行時(shí)序最短路徑查詢，用以判斷查詢算法是否在不同類型的道路網(wǎng)絡(luò)中都能高效地進(jìn)行最短路徑查詢工作。3 個(gè)查詢算法使用同樣的查詢文件，即相同的源節(jié)點(diǎn)、目的節(jié)點(diǎn)與出發(fā)時(shí)間。查詢文件中共10 000條查詢，10 000次查詢后，將平均時(shí)間作為查詢結(jié)果。

如圖5所示，隨著數(shù)據(jù)集規(guī)模的增長，3種查詢算法的查詢時(shí)間均呈現(xiàn)出遞增的趨勢(shì)。4 個(gè)數(shù)據(jù)集上的運(yùn)行結(jié)果都表明，本文算法TD-OAI效率優(yōu)于現(xiàn)有算法，非索引算法TD-Dijkstra 明顯比其他兩個(gè)基于索引的查詢算法需要更長的平均查詢時(shí)間。這是由于TD-Dijkstra 在查詢過程中需要進(jìn)行多次迭代運(yùn)算，每次迭代從候選集中選擇與源節(jié)點(diǎn)距離最短的節(jié)點(diǎn)作為訪問節(jié)點(diǎn)，直至找到目的節(jié)點(diǎn)。TD-Dijkstra不知道目的節(jié)點(diǎn)的位置，只能向所有可能的方向擴(kuò)展節(jié)點(diǎn)，直到發(fā)現(xiàn)目的節(jié)點(diǎn)為止，當(dāng)兩個(gè)節(jié)點(diǎn)距離很遠(yuǎn)時(shí)TD-Dijkstra可能遍歷整個(gè)網(wǎng)絡(luò)。TD-G-tree使用分層圖分區(qū)將道路網(wǎng)絡(luò)劃分為分層分區(qū)，產(chǎn)生平衡樹TD-G-tree，索引邊在分區(qū)過程中被切割的節(jié)點(diǎn)（邊界節(jié)點(diǎn)）間的最短旅行時(shí)間函數(shù)，查詢最短路徑時(shí)，利用TD-G-tree 與邊界節(jié)點(diǎn)的特性，可以減少查詢時(shí)的訪問節(jié)點(diǎn)的數(shù)量。本文基于點(diǎn)割集與樹分解的概念提出的索引TD-H2H，提前存儲(chǔ)好源節(jié)點(diǎn)與目的節(jié)點(diǎn)到點(diǎn)割集中節(jié)點(diǎn)的最短旅行時(shí)間函數(shù)，查詢時(shí)直接訪問即可，訪問次數(shù)以樹分解的寬度w為界，而道路網(wǎng)絡(luò)的樹寬通常較小，因此，TD-OAI的查詢速度更快。

圖5 有效性測(cè)試Fig.5 Effectiveness experiment

（2）節(jié)點(diǎn)數(shù)量對(duì)查詢效率的影響：為了測(cè)試出節(jié)點(diǎn)數(shù)量對(duì)查詢效率的影響，本文在4 個(gè)時(shí)序圖OL、CAL、NA 與BAY 中分別按照0.2、0.4、0.6 與0.8 的節(jié)點(diǎn)數(shù)占比提取出4個(gè)時(shí)序子圖，保證4個(gè)子圖內(nèi)的節(jié)點(diǎn)數(shù)遞增且相對(duì)平均增長，在新得到的16 個(gè)子圖中分別運(yùn)行3個(gè)查詢算法。查詢結(jié)果如圖6～圖9所示，隨著節(jié)點(diǎn)數(shù)的增多，3種算法的查詢時(shí)間均呈現(xiàn)上升趨勢(shì)，TD-Dijkstra持續(xù)上升，TD-OAI與TDSP在開始時(shí)上升，之后趨于平緩，說明節(jié)點(diǎn)數(shù)量對(duì)基于索引的算法的影響遠(yuǎn)小于非索引算法的影響，且TD-OAI的查詢時(shí)間遠(yuǎn)小于其他兩個(gè)算法。隨著圖中節(jié)點(diǎn)數(shù)量的增多，進(jìn)行最短路徑查詢時(shí)需要訪問的節(jié)點(diǎn)數(shù)也會(huì)增多，因此3個(gè)算法的查詢時(shí)間均有所增長?；谒饕牟樵兯惴ㄓ捎谒饕呀?jīng)提前保存了部分關(guān)鍵最短路徑，查詢時(shí)可直接使用，大大減少了需要訪問的節(jié)點(diǎn)數(shù)量，因而節(jié)點(diǎn)數(shù)增長對(duì)于索引方法的影響要小于非索引方法，進(jìn)一步說明了索引的必要性。

圖6 節(jié)點(diǎn)數(shù)測(cè)試（OL）Fig.6 Experiment of number of vertices(OL)

圖7 節(jié)點(diǎn)數(shù)測(cè)試（CAL）Fig.7 Experiment of number of vertices(CAL)

圖8 節(jié)點(diǎn)數(shù)測(cè)試（NA）Fig.8 Experiment of number of vertices(NA)

圖9 節(jié)點(diǎn)數(shù)測(cè)試（BAY）Fig.9 Experiment of number of vertices(BAY)

（3）節(jié)點(diǎn)的旅行時(shí)間長度對(duì)查詢效率的影響：評(píng)估源節(jié)點(diǎn)與目的節(jié)點(diǎn)間的旅行時(shí)間長度對(duì)查詢效率的影響時(shí)，本文以源節(jié)點(diǎn)與目的節(jié)點(diǎn)之間的旅行時(shí)間為標(biāo)準(zhǔn)為4 個(gè)時(shí)序圖分別生成了5 個(gè)查詢文件。每個(gè)查詢文件中包含104個(gè)查詢，每個(gè)查詢由源節(jié)點(diǎn)、目的節(jié)點(diǎn)以及出發(fā)時(shí)間組成，且為保證旅行時(shí)間的遞增和相對(duì)平均增長，5個(gè)文件中源節(jié)點(diǎn)與目的節(jié)點(diǎn)間的旅行時(shí)間都在特定的范圍內(nèi)，分別為[0,1.0×104)、[1.0×104,1.0×105)、[3.0×105,5.0×105)、[8.0×105,1.0×106)以及[1.3×106,1.5×106)，單位為s，用以測(cè)試在同一個(gè)時(shí)序道路網(wǎng)絡(luò)中，節(jié)點(diǎn)間的旅行時(shí)間長度對(duì)查詢效率的影響。使用3 個(gè)查詢算法依次在4 個(gè)時(shí)序圖上對(duì)5個(gè)查詢文件進(jìn)行查詢，其查詢結(jié)果如圖10～圖13所示，3種算法的查詢時(shí)間整體呈上升趨勢(shì)，TD-OAI波動(dòng)的幅度最小，且查詢時(shí)間遠(yuǎn)小于其他兩個(gè)算法。隨著節(jié)點(diǎn)間旅行時(shí)間的增大，TD-Dijkstra 需要遍歷的節(jié)點(diǎn)數(shù)也會(huì)變多，進(jìn)而增大了查詢時(shí)間。而基于索引的查詢算法，在索引的作用下，節(jié)點(diǎn)間的旅行時(shí)間對(duì)查詢時(shí)間的影響較小，因此，TD-Dijkstra上升趨勢(shì)明顯，而另外兩個(gè)算法的趨勢(shì)較平緩。

圖10 旅行時(shí)間測(cè)試（OL）Fig.10 Experiment of travelling time(OL)

圖11 旅行時(shí)間測(cè)試（CAL）Fig.11 Experiment of travelling time(CAL)

圖12 旅行時(shí)間測(cè)試（NA）Fig.12 Experiment of travelling time(NA)

圖13 旅行時(shí)間測(cè)試（BAY）Fig.13 Experiment of travelling time(BAY)

6.3 索引評(píng)估

本節(jié)評(píng)估了構(gòu)建TD-H2H 索引的所需的時(shí)間開銷以及空間開銷，分別與TD-G-tree進(jìn)行比較。圖14說明了索引構(gòu)建時(shí)間，圖15 說明了索引大小。TDH2H 索引包括時(shí)序樹分解結(jié)構(gòu)、樹中每個(gè)包的位置數(shù)組以及旅行時(shí)間函數(shù)表。索引構(gòu)建時(shí)間包括構(gòu)建時(shí)序樹分解的時(shí)間以及計(jì)算位置數(shù)組和旅行時(shí)間函數(shù)表的時(shí)間。如圖14 所示，TD-H2H 的構(gòu)建時(shí)間與TD-G-tree 的構(gòu)建時(shí)間接近，索引大小比TD-G-tree大，因?yàn)橄啾冗吔绻?jié)點(diǎn)，圖中點(diǎn)割集中的節(jié)點(diǎn)更多，根據(jù)點(diǎn)割集構(gòu)造索引，會(huì)有更大的空間開銷。

圖14 構(gòu)建時(shí)間Fig.14 Building time

圖15 索引大小Fig.15 Index size

7 結(jié)論

本文研究了時(shí)序道路網(wǎng)路上的最短路徑查詢問題，基于樹分解的概念提出了TD-H2H索引。為了將樹分解應(yīng)用于時(shí)序圖，提出時(shí)序樹分解算法，該方法生成的樹分解可以加速索引的構(gòu)建。在樹分解結(jié)構(gòu)的基礎(chǔ)上提出了索引TD-H2H 的構(gòu)建算法。最后基于TD-H2H 索引設(shè)計(jì)了最短路徑查詢方法TD-OAI。實(shí)驗(yàn)結(jié)果表明了本文方法可以有效地解決時(shí)序圖上的最短路徑查詢問題。