時(shí)態(tài)圖最短路徑查詢方法

張?zhí)烀?徐一恒 蔡鑫偉 范 菁

1(浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 杭州 310023) 2(浙江大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 杭州 310013)

圖，作為一種通用的數(shù)據(jù)結(jié)構(gòu)，用于表示各種對(duì)象之間的復(fù)雜關(guān)聯(lián)關(guān)系.圖上最短路徑計(jì)算作為基礎(chǔ)功能函數(shù)，有著廣泛的應(yīng)用.例如，路徑規(guī)劃、城市交通路線優(yōu)化、社交網(wǎng)絡(luò)分析等.現(xiàn)有的最短路徑算法主要聚焦在普通圖，然而，真實(shí)場(chǎng)景中，圖中常常附有時(shí)態(tài)信息，2個(gè)頂點(diǎn)之間的邊關(guān)聯(lián)的事件在某一時(shí)間點(diǎn)發(fā)生并持續(xù)一段時(shí)間結(jié)束，此種類型的圖稱之為時(shí)態(tài)圖.

Fig. 1 Illustration of bus timetable圖1 公交時(shí)刻圖示例

圖1列舉了時(shí)態(tài)圖應(yīng)用在公交時(shí)刻圖的例子.圖中頂點(diǎn)表示公交站點(diǎn)，時(shí)態(tài)邊上附帶有時(shí)態(tài)區(qū)間，表示公交車從一個(gè)站點(diǎn)到另一個(gè)站點(diǎn)的出發(fā)時(shí)間和到達(dá)時(shí)間.例如，一班89路公交車早上7∶00從浙大玉泉校區(qū)始發(fā)站出發(fā)，7∶15到達(dá)古蕩站點(diǎn)，停靠站1 min，7∶16出發(fā)，經(jīng)府苑新村，蔣村公交站，最終在8∶15到達(dá)三墩終點(diǎn)站.此例中，時(shí)態(tài)圖最短路徑查詢有助于乘客查詢指定時(shí)態(tài)區(qū)間內(nèi)的2個(gè)站點(diǎn)間的最短路徑，從而為乘客智能推薦公交線路.給定時(shí)態(tài)圖

G

=(

V

,

E

)，查詢?cè)袋c(diǎn)

u

，查詢目的點(diǎn)

v

，時(shí)態(tài)區(qū)間

I

，本文研究的時(shí)態(tài)圖最短路徑旨在圖

G

中查詢

u

到

v

在時(shí)態(tài)區(qū)間

I

內(nèi)的最短時(shí)態(tài)路徑距離

.

時(shí)態(tài)圖

G

中的邊除了關(guān)聯(lián)時(shí)態(tài)區(qū)間外，還附加有權(quán)重值，在交通路網(wǎng)中可以表示距離；在公交

/

地鐵

/

航班時(shí)刻圖中可以表示費(fèi)用；在社交網(wǎng)絡(luò)中可以表示用戶之間的親密度

.

與已有的最短路徑查詢問題相比，最短時(shí)態(tài)路徑更具挑戰(zhàn)性

.

首先，計(jì)算最短時(shí)態(tài)路徑時(shí)需要考慮邊與邊的時(shí)序流轉(zhuǎn)特性，否則如果運(yùn)用現(xiàn)有的普通圖最短路徑計(jì)算方法，會(huì)產(chǎn)生錯(cuò)誤的結(jié)果.例如，圖1中，假設(shè)邊上權(quán)值均為1，乘客想要查詢?cè)茥℃?zhèn)站到三墩站在時(shí)態(tài)區(qū)間[7∶00,9∶00]的時(shí)態(tài)最短路徑距離.如果不考慮邊之間的時(shí)序流轉(zhuǎn)特性，則計(jì)算得到的結(jié)果為3，對(duì)應(yīng)的最短時(shí)態(tài)路徑為(云棲小鎮(zhèn)，府苑新村，蔣村公交站，三墩)或(云棲小鎮(zhèn)，府苑新村，董家村，三墩).實(shí)際這2條路徑均不能到達(dá)三墩站.對(duì)于第一條路徑，121路云棲小鎮(zhèn)到府苑新村時(shí)間為8∶20，其不能趕上7∶32從府苑新村出發(fā)經(jīng)由蔣村公交站最終到達(dá)三墩站的89路公交車.對(duì)于第二條路徑，121路換乘70路8∶50到董家村，同樣趕不上8∶26到三墩站的12專線.鑒于此，時(shí)態(tài)最短路徑計(jì)算過程中需要考慮時(shí)序流轉(zhuǎn)特性，此例計(jì)算得到的結(jié)果應(yīng)為4，對(duì)應(yīng)的最短時(shí)態(tài)路徑應(yīng)為(云棲小鎮(zhèn)，翠苑，大關(guān)，董家村，三墩).

其次，最短時(shí)態(tài)路徑并不滿足子路徑最優(yōu)性質(zhì),即頂點(diǎn)

u

到頂點(diǎn)

v

的最短時(shí)態(tài)路徑的子路徑并不一定是最短時(shí)態(tài)路徑.上例中，子路徑(云棲小鎮(zhèn)，翠苑，大關(guān)，董家村)并不是時(shí)態(tài)區(qū)間[7∶00,9∶00]內(nèi)的最短時(shí)態(tài)路徑，云棲小鎮(zhèn)到董家村在時(shí)態(tài)區(qū)間[7∶00,9∶00]內(nèi)最短時(shí)態(tài)路徑應(yīng)為(云棲小鎮(zhèn)，府苑新村，董家村).這導(dǎo)致計(jì)算時(shí)態(tài)最短路徑時(shí)更復(fù)雜，因?yàn)樾枰紤]所有的路徑.

目前，已有一些工作研究時(shí)態(tài)圖最短路徑查詢.然而，它們一般假設(shè)輸入時(shí)態(tài)圖為FIFO(first-in-first-out)時(shí)間依賴圖，F(xiàn)IFO時(shí)間依賴圖是指圖輸入邊上的時(shí)間間隔表示為出發(fā)時(shí)間的函數(shù)，這個(gè)函數(shù)具有FIFO屬性，即若出發(fā)時(shí)間早，則到達(dá)時(shí)間也早.這類問題具有一定的特殊性，實(shí)際交通工具出行時(shí)刻圖或社交接觸網(wǎng)絡(luò)不一定是FIFO時(shí)間依賴圖.與本文工作最相關(guān)的是文獻(xiàn)[6-7]提出的one-pass算法，其將時(shí)態(tài)圖轉(zhuǎn)化為普通圖，而后在普通圖上采用廣度優(yōu)先搜索和Dijkstra算法計(jì)算最短時(shí)態(tài)路徑，但其在較大規(guī)模數(shù)據(jù)集上效率較低.鑒于此，本文研究時(shí)態(tài)圖最短路徑問題并提出了基于層次索引的計(jì)算方法，其主要包含預(yù)處理和在線查詢2個(gè)階段.預(yù)處理階段本文提出了一種無(wú)損壓縮方法和層次索引CTG-tree(compressed transformed graph tree).首先將時(shí)態(tài)圖轉(zhuǎn)化為普通圖，對(duì)普通圖進(jìn)行壓縮以減小規(guī)模，將時(shí)態(tài)圖上最短路徑計(jì)算轉(zhuǎn)化為在壓縮結(jié)果圖上執(zhí)行.而后在壓縮結(jié)果圖上構(gòu)建CTG-tree，它將G-tree的思想擴(kuò)展到壓縮有向圖上，首先采用Metis劃分將壓縮圖層次劃分為若干個(gè)子圖，得到每個(gè)子圖的入邊界點(diǎn)與出邊界點(diǎn)集合.CTG-tree為每個(gè)葉子節(jié)點(diǎn)對(duì)應(yīng)子圖計(jì)算其內(nèi)部頂點(diǎn)與出邊界點(diǎn)的最短路徑、入邊界點(diǎn)到子圖內(nèi)頂點(diǎn)的最短路徑和出邊界點(diǎn)到入邊界點(diǎn)的最短路徑；非葉節(jié)點(diǎn)計(jì)算其對(duì)應(yīng)子圖入邊界點(diǎn)到其所有孩子節(jié)點(diǎn)對(duì)應(yīng)子圖的入邊界點(diǎn)之間的最短路徑距離、所有孩子節(jié)點(diǎn)對(duì)應(yīng)子圖的出邊界點(diǎn)到當(dāng)前非葉節(jié)點(diǎn)對(duì)應(yīng)子圖的出邊界點(diǎn)之間的最短路徑距離、以及所有孩子節(jié)點(diǎn)對(duì)應(yīng)子圖的出邊界點(diǎn)到所有孩子節(jié)點(diǎn)對(duì)應(yīng)子圖的入邊界點(diǎn)之間的最短路徑距離作為索引.查詢階段本文基于層次索引CTG-tree設(shè)計(jì)了高效的最短路徑查詢算法.概括而言，本文的主要貢獻(xiàn)有4個(gè)方面:

1) 提出了一種基于層次索引的兩階段(預(yù)處理階段和查詢階段)方法以高效地計(jì)算時(shí)態(tài)圖最短路徑;

2) 提出了一種無(wú)損壓縮方法和層次索引CTG-tree，將時(shí)態(tài)圖上最短路徑計(jì)算結(jié)果轉(zhuǎn)化為在壓縮結(jié)果圖上執(zhí)行.CTG-tree將G-tree的思想擴(kuò)展到壓縮有向圖上；無(wú)損壓縮在減小圖處理規(guī)模的同時(shí)還保證了壓縮結(jié)果圖上最短路徑計(jì)算的準(zhǔn)確性；

3) 提出了基于CTG-tree索引的查詢算法以高效地支持時(shí)態(tài)圖最短路徑查詢;

4) 基于4個(gè)真實(shí)的時(shí)態(tài)圖數(shù)據(jù)集，進(jìn)行了充分的實(shí)驗(yàn)評(píng)估，驗(yàn)證了本文提出的基于層次索引的最短時(shí)態(tài)路徑算法的高效性.

1 相關(guān)工作

本節(jié)分別概述已有的普通圖和時(shí)態(tài)圖最短路徑查詢算法.

1.1 普通圖最短路徑查詢算法

綜述文獻(xiàn)[1,9]將普通圖最短路徑問題劃分為點(diǎn)到點(diǎn)的最短路徑計(jì)算、單源最短路徑計(jì)算和所有點(diǎn)對(duì)最短路徑計(jì)算3類問題.點(diǎn)到點(diǎn)的最短路徑計(jì)算指定點(diǎn)對(duì)之間的最短路徑；單源最短路徑計(jì)算一個(gè)點(diǎn)到其他所有點(diǎn)的最短路徑距離；所有點(diǎn)對(duì)最短路徑計(jì)算圖中所有點(diǎn)對(duì)之間的最短路徑距離,其可通過單源最短路徑計(jì)算得到.已有的最短路徑查詢算法大多是基于經(jīng)典的Dijkstra方法，文獻(xiàn)[10]從理論角度分析了單源最短路徑基于堆的優(yōu)先級(jí)隊(duì)列算法的時(shí)間復(fù)雜度是

O

(

m

log

n

)；采用斐波那契堆的時(shí)間復(fù)雜度是

O

(

m

+

n

log

n

).文獻(xiàn)[11]提出了基于Dijkstra的變體方法Sky-Dijk.為了縮小搜索空間，雙向搜索算法被提出.由于Dijkstra方法及其變體算法在大圖上運(yùn)行時(shí)間較長(zhǎng)，因此研究人員提出了一系列基于索引的最短路徑算法以提高查詢效率.例如，文獻(xiàn)[14]提出了基于標(biāo)志點(diǎn)(landmark)的算法，其預(yù)先選擇一些頂點(diǎn)作為標(biāo)志點(diǎn)；并且預(yù)先計(jì)算圖中每個(gè)頂點(diǎn)與標(biāo)志點(diǎn)之間的最短路徑距離.圖中任意一對(duì)頂點(diǎn)之間的最短路徑距離上下界可以運(yùn)用預(yù)先計(jì)算好的距離計(jì)算得到；文獻(xiàn)[15]提出了基于剪枝的標(biāo)志點(diǎn)標(biāo)簽，通過剪枝的廣度優(yōu)先搜索預(yù)計(jì)算所有頂點(diǎn)的距離標(biāo)簽，通過距離標(biāo)簽計(jì)算任意點(diǎn)對(duì)的最短路徑距離.文獻(xiàn)[16]提出了收縮層級(jí)結(jié)構(gòu)；將圖中的頂點(diǎn)或者邊按照重要度排序，再根據(jù)排序的結(jié)果迭代，最終生成層級(jí)嵌套索引.文獻(xiàn)[8]提出了G-tree索引，其首先將路網(wǎng)層次劃分為若干個(gè)子圖，再計(jì)算每個(gè)子圖內(nèi)的頂點(diǎn)與邊界點(diǎn)之間的距離，子圖間的邊界點(diǎn)與邊界點(diǎn)之間的距離作為索引，基于G-tree索引提高查詢效率.基于索引的最短路徑算法關(guān)鍵在于平衡查詢時(shí)間、索引時(shí)間、索引空間；為了減小索引空間，文獻(xiàn)[17-18]還提出了索引壓縮方法.針對(duì)動(dòng)態(tài)圖，文獻(xiàn)[19]提出了DCHvcs,其擴(kuò)展收縮層級(jí)結(jié)構(gòu)以支持動(dòng)態(tài)圖.文獻(xiàn)[20]在收縮層級(jí)最短路徑索引的基礎(chǔ)上，構(gòu)建輔助的圖結(jié)構(gòu)以及權(quán)重傳播機(jī)制來(lái)處理流式和批量的路網(wǎng)權(quán)重更新.文獻(xiàn)[21]提出了CRP方法以支持最短路徑索引的動(dòng)態(tài)更新.針對(duì)大規(guī)模輸入圖，文獻(xiàn)[22]基于分布式流處理系統(tǒng)Yahoo S4，提出了2種異步通信算法以支持動(dòng)態(tài)最短路徑；文獻(xiàn)[23]探索了邊受限的最短路徑查詢問題.此外，一些研究人員還致力于近似最短路徑計(jì)算方法研究.文獻(xiàn)[24]提出了距離Oracle數(shù)據(jù)結(jié)構(gòu)，對(duì)于(2

k

-1)-近似能在

O

(

k

)的時(shí)間內(nèi)給出任意節(jié)點(diǎn)對(duì)之間的近似最短路徑.文獻(xiàn)[25]將大圖近似為一個(gè)規(guī)模相對(duì)小的spanner稀疏子圖，而后在子圖上做近似最短路徑計(jì)算.概括而言，上述算法均針對(duì)普通圖，并沒有考慮邊上附帶的時(shí)態(tài)信息，因此不能直接有效地應(yīng)用在時(shí)態(tài)圖上.

1.2 時(shí)態(tài)圖最短路徑查詢算法

綜述文獻(xiàn)[1]總結(jié)了時(shí)間依賴圖的最短路徑查詢算法.時(shí)間依賴圖中邊延遲函數(shù)計(jì)算一條邊中源點(diǎn)到目的點(diǎn)所需時(shí)間，時(shí)間函數(shù)可分為離散或連續(xù)的.

文獻(xiàn)[2,6-7,26]針對(duì)離散時(shí)間下的最短路徑進(jìn)行了研究.文獻(xiàn)[2]提出了TD-G-tree索引以支持時(shí)間依賴路網(wǎng)上最短路徑查詢，但是其與本文研究問題不同，并沒有考慮路徑內(nèi)邊之間的時(shí)序關(guān)系.文獻(xiàn)[26]提出了時(shí)間表標(biāo)簽(time table labelling, TTL)索引；文獻(xiàn)[6-7,27]提出將時(shí)態(tài)圖轉(zhuǎn)化為普通圖，基于此，文獻(xiàn)[27]研究了時(shí)間依賴的可達(dá)性查詢，其提出了TopChain標(biāo)簽索引方法以解決時(shí)態(tài)圖上的可達(dá)性查詢、最早到達(dá)時(shí)間查詢、最小間隔時(shí)間查詢.與其研究的問題不同，本文旨在解決時(shí)態(tài)圖上的最短路徑查詢.文獻(xiàn)[6-7]在轉(zhuǎn)化的普通圖上采用廣度優(yōu)先搜索和Dijkstra算法計(jì)算2點(diǎn)之間給定時(shí)間段內(nèi)的最短路徑.本文基于上述工作，將時(shí)態(tài)圖轉(zhuǎn)化為普通圖后，利用壓縮以及層次索引技術(shù)高效支持最短時(shí)態(tài)路徑查詢.

文獻(xiàn)[3-5]針對(duì)連續(xù)時(shí)間下的最短路徑進(jìn)行了研究.文獻(xiàn)[4]提出了基于Dijkstra算法返回耗時(shí)最少旅行時(shí)間的最優(yōu)出發(fā)時(shí)間；文獻(xiàn)[3]首先定位給定時(shí)態(tài)區(qū)間段內(nèi)子圖，而后在子圖中采用Dijkstra計(jì)算最短路徑.文獻(xiàn)[5]在文獻(xiàn)[4]的基礎(chǔ)上，研究的時(shí)態(tài)圖中邊除了邊延遲函數(shù)外，還添加了權(quán)重代價(jià)函數(shù)，利用這2種函數(shù)的結(jié)構(gòu)屬性設(shè)計(jì)最短路徑算法.這類工作通常假設(shè)輸入時(shí)態(tài)圖為FIFO時(shí)間依賴圖，輸入邊上時(shí)間間隔表示為出發(fā)時(shí)間的函數(shù)，出發(fā)時(shí)間早，則到達(dá)時(shí)間也早，這類問題具有一定的特殊性.而在我們的問題中，輸入邊有出發(fā)時(shí)間和到達(dá)時(shí)間，輸入圖(例如交通工具出行時(shí)刻圖或者社交接觸網(wǎng)絡(luò))不一定是FIFO時(shí)間依賴圖，這導(dǎo)致計(jì)算時(shí)態(tài)最短路徑時(shí)更復(fù)雜，最短路徑計(jì)算不滿足最優(yōu)子結(jié)構(gòu)特征，因?yàn)樾枰紤]邊與邊的時(shí)序流轉(zhuǎn)特性，計(jì)算難度更高.

2 問題定義

本節(jié)主要介紹時(shí)態(tài)圖、時(shí)態(tài)路徑相關(guān)概念，最后給出問題定義.

定義1.

時(shí)態(tài)圖

.

本文定義的時(shí)態(tài)圖是復(fù)雜有向圖，表示為

G

=(

V

,

E

)，其中

V

表示頂點(diǎn)集合；

E

?

V

×

V

是有向邊的集合，具體地，連接頂點(diǎn)

u

∈

V

到

v

∈

V

/

{

u

}的有向邊

e

∈

E

表示為一個(gè)五元組(

u

,

v

,

w

,

s

,

a

)，表示

u

與

v

之間的事件發(fā)生起始時(shí)間是

s

，終止時(shí)間是

a

.

時(shí)間間隔是

I

=(

s

,

a

)，持續(xù)時(shí)間為|

I

|=

a

-

s

，

w

表示每條時(shí)態(tài)邊

e

的非負(fù)權(quán)重值，表示耗費(fèi)時(shí)間或者路程等

.

不同于簡(jiǎn)單圖，時(shí)態(tài)圖中2個(gè)頂點(diǎn)之間可能有多條時(shí)態(tài)邊

.

與普通圖路徑定義不同，時(shí)態(tài)圖中時(shí)態(tài)路徑的定義如下：

給定時(shí)態(tài)圖

G

，源點(diǎn)

s

，目的點(diǎn)

s

′，時(shí)間間隔

I

=[

t

,

t

]，定義函數(shù)

TPSet

(

s

,

s

′,

I

=[

t

,

t

])為從頂點(diǎn)

s

到頂點(diǎn)

s

′的所有滿足

S

≥

t

,

E

≤

t

的

G

中的時(shí)態(tài)路徑

p

構(gòu)成的集合

.

基于此給出定義3

.

3 CTG-Tree構(gòu)建

本文提出了基于層次索引的計(jì)算方法，主要包含預(yù)處理和在線查詢2個(gè)階段.本節(jié)詳細(xì)闡述預(yù)處理階段提出的無(wú)損壓縮方法和層次索引CTG-tree.

3.1 基于轉(zhuǎn)化圖的無(wú)損壓縮

在時(shí)態(tài)圖上計(jì)算最短時(shí)態(tài)路徑的直接方法是進(jìn)行廣度優(yōu)先搜索或者深度優(yōu)先搜索，但是由于時(shí)態(tài)最短路徑不滿足子路徑最優(yōu)性質(zhì)，因此在搜索過程中需要保存計(jì)算遍歷到的所有路徑，此種方法效率較低.因此本文的主要思想是先將時(shí)態(tài)圖轉(zhuǎn)化為普通圖，而后進(jìn)行壓縮，再利用索引加速查詢.具體地，本文利用文獻(xiàn)[6]提出的方法將時(shí)態(tài)圖

G

=(

V

,

E

)轉(zhuǎn)化為普通圖

G

=(

V

,

E

)，其中轉(zhuǎn)化圖

G

已被證明為有向無(wú)環(huán)圖，具體的轉(zhuǎn)化過程如下

.

Fig. 2 Illustrations of temporal graph,transformed graph, and compressed graph圖2 時(shí)態(tài)圖、轉(zhuǎn)化圖和壓縮圖示例

算法1.

基于轉(zhuǎn)化圖的無(wú)損壓縮算法

.

輸入：基于時(shí)態(tài)圖

G

=(

V

,

E

)的轉(zhuǎn)化圖

G

=(

V

,

E

)；輸出：無(wú)損壓縮圖

G

′=(

V

′,

E

′)

.

/

*根據(jù)規(guī)則進(jìn)行壓縮*

/

④ end if

⑤ end for

⑥ 輸出無(wú)損壓縮圖

G

′=(

V

′,

E

′)

.

3.2 CTG-tree索引

基于上述無(wú)損壓縮圖，構(gòu)建層次索引CTG-tree.分為2個(gè)步驟：

1)
圖層次劃分.由于Metis劃分保證每次劃分的子圖頂點(diǎn)數(shù)目相近，交叉邊數(shù)目較少，因此本文采用Metis層次劃分，首先將無(wú)損壓縮圖

G

′劃分為若干子圖

G

，

G

，…，

G

(

l

≥2)，而后在每個(gè)子圖

G

(1≤

i

≤

l

)上進(jìn)行迭代劃分直至劃分的子圖頂點(diǎn)數(shù)目不超過指定的閾值

θ

；最終形成平衡樹CTG-tree

.G

′為CTG-tree的根節(jié)點(diǎn)，第

i

次迭代劃分的子圖為CTG-tree第

i

層節(jié)點(diǎn)，葉子節(jié)點(diǎn)對(duì)應(yīng)子圖的頂點(diǎn)數(shù)目不超過閾值

θ.

Metis劃分屬于邊劃分方法，每次迭代劃分的子圖之間沒有交集(例

G

∪

G

∪…∪

G

=

G

′,

G

∩

G

∩…∩

G

=?)，但是會(huì)產(chǎn)生跨子圖的交叉邊

e

(

u

,

v

),

u

∈

G

,

v

∈

G

.

基于此，本文將子圖內(nèi)頂點(diǎn)分為3類：入邊界點(diǎn)、出邊界點(diǎn)和內(nèi)部頂點(diǎn)

.

令

G

.B

,

G

.B

,

G

.V

分別表示子圖

G

=(

V

,

E

)的入邊界點(diǎn)、出邊界點(diǎn)和內(nèi)部頂點(diǎn)的集合，則①

V

=

G

.B

∪

G

.B

∪

G

.V

；② ?

u

∈

G

.B

，至少存在一條跨分區(qū)的交叉邊

e

=(

u

,

m

),

u

與

m

隸屬不同子圖，即

m

?

G

；③ ?

v

∈

G

.B

，至少存在一條跨分區(qū)的交叉邊

e

=(

s

,

v

),

s

與

v

隸屬不同子圖，即

s

?

G

；④ ?

v

′∈

G

.V

，

v

′的所有入度鄰居

.

出度鄰居都隸屬子圖

G

，即

N

(

v

′)?

V

,

N

(

v

′)?

V

；在圖劃分步驟中，每個(gè)子圖記錄相應(yīng)的入邊界點(diǎn)，出邊界點(diǎn)

.

2) 最短路徑距離矩陣計(jì)算

.

對(duì)于CTG-tree中的葉子節(jié)點(diǎn)對(duì)應(yīng)的子圖

G

，需要計(jì)算3個(gè)最短路徑距離矩陣，即游出距離矩陣

G

.

、游入距離矩陣

G

.

和邊界點(diǎn)距離矩陣

G

.

.

G

.

保存

G

中所有頂點(diǎn)到每個(gè)出邊界點(diǎn)的最短路徑距離；

G

.

保存

G

中每個(gè)入邊界點(diǎn)到所有頂點(diǎn)的最短路徑距離；

G

.

保存

G

中所有出邊界點(diǎn)到入邊界點(diǎn)的最短路徑距離

.

對(duì)于CTG-tree中的非葉子節(jié)點(diǎn)對(duì)應(yīng)的子圖

G

，需要計(jì)算出邊界點(diǎn)游入距離矩陣

G

.

、入邊界點(diǎn)游入距離矩陣

G

.

和邊界點(diǎn)游出距離矩陣

G

.

；

G

.

保存

G

所有孩子節(jié)點(diǎn)對(duì)應(yīng)子圖的出邊界點(diǎn)到

G

所有孩子節(jié)點(diǎn)對(duì)應(yīng)子圖的入邊界點(diǎn)之間的最短路徑距離；

G

.

保存

G

入邊界點(diǎn)到

G

所有孩子節(jié)點(diǎn)對(duì)應(yīng)子圖的入邊界點(diǎn)之間的最短路徑距離；

G

.

保存

G

所有孩子節(jié)點(diǎn)對(duì)應(yīng)子圖的出邊界點(diǎn)到

G

出邊界點(diǎn)之間的最短路徑距離

.

具體的CTG-tree索引構(gòu)建算法偽碼如算法2所示

.

算法2.

CTG-tree索引構(gòu)建算法

.

輸入：無(wú)損壓縮圖

G

′=(

V

′,

E

′)，Metis每層劃分的子圖數(shù)

l

，葉子子圖頂點(diǎn)數(shù)閾值

θ

；

輸出：CTG-tree索引.

① CTG-tree←

Metis

(

G

′,

l

,

θ

)；

② for each layer(自底向上) of CTG-tree

③ if leaf node←

/

*葉子節(jié)點(diǎn)層計(jì)算*

/

④

G

.

,

G

.

,

G

.

←

Dijkstra

(

G

′)；⑤ else

/

*非葉子節(jié)點(diǎn)層計(jì)算*

/

⑥

G

.

←

Dijkstra

(

G

′);

G

.

←

Dijkstra

(

G

′);

G

.

←

Dijkstra

(

G

′)；

⑦ end if

⑧ end for

⑨ 輸出CTG-tree索引.

算法2首先在給定的無(wú)損壓縮圖

G

′上進(jìn)行Metis層次劃分，得到CTG-tree(行①)，需要說明的是，無(wú)損壓縮圖中，邊權(quán)重為0會(huì)影響Metis劃分過程，因此需要適當(dāng)增權(quán)處理.接著，對(duì)CTG-tree自底向上遍歷計(jì)算索引矩陣(行②).對(duì)于葉子節(jié)點(diǎn)，利用Dijkstra算法在圖

G

′上計(jì)算葉子節(jié)點(diǎn)對(duì)應(yīng)子圖

G

的游出距離矩陣

G

.

、游入距離矩陣

G

.

和邊界點(diǎn)距離矩陣

G

.

(行③～④)

.

對(duì)于非葉節(jié)點(diǎn)，利用Dijkstra算法在圖

G

′上計(jì)算對(duì)應(yīng)子圖

G

的出邊界點(diǎn)游入距離矩陣

G

.

、邊界點(diǎn)游出距離矩陣

G

.

和入邊界點(diǎn)游入距離矩陣

G

.

，值得注意的是，此過程可以利用頂點(diǎn)拓?fù)湫蚣铀儆?jì)算過程，由于轉(zhuǎn)化圖是有向無(wú)環(huán)圖，壓縮圖即為有向無(wú)環(huán)圖，因此在運(yùn)用Dijkstra算法前，可先計(jì)算頂點(diǎn)拓?fù)湫?，若在?jì)算頂點(diǎn)

u

到

v

的最短路徑時(shí)，

u

的拓?fù)湫虼笥?p>v

的拓?fù)湫?，則頂點(diǎn)

u

到

v

的最短路徑一定為∞

.

Fig. 3 Metis Partitioning and CTG-tree Construction圖3 Metis劃分以及CTG-tree構(gòu)建過程

隨后，計(jì)算CTG-tree中的葉子節(jié)點(diǎn)對(duì)應(yīng)子圖

G

，

G

，

G

和

G

的游出距離矩陣

G

.

、游入距離矩陣

G

.

和邊界點(diǎn)距離矩陣

G

.

.

而后，自底向上計(jì)算非葉節(jié)點(diǎn)對(duì)應(yīng)子圖

G

，

G

和

G

的出邊界點(diǎn)游入距離矩陣

G

.

、入邊界點(diǎn)游入距離矩陣

G

.

和邊界點(diǎn)游出距離矩陣

G

.

.

Fig.4 Distance Matrix Index in CTG-tree圖4 CTG-tree中的距離矩陣索引

CTG-tree索引保存3部分信息：CTG-tree節(jié)點(diǎn)、邊界點(diǎn)以及距離矩陣.CTG-tree葉子節(jié)點(diǎn)對(duì)應(yīng)子圖的頂點(diǎn)數(shù)目不超過閾值

θ

,每層節(jié)點(diǎn)數(shù)為

l

，所以CTG-tree高度為log(|

V

|

/θ

)+1，CTG-tree節(jié)點(diǎn)總數(shù)為

l

|

V

|

/

(

l

-1)

θ.

CTG-tree邊界點(diǎn)總數(shù)為

CTG-tree距離矩陣大小為

所以CTG-tree索引空間復(fù)雜度為

4 基于CTG-tree索引的最短路徑計(jì)算方法

本節(jié)詳細(xì)闡述在線查詢階段提出的基于層次索引CTG-tree的最短路徑計(jì)算方法.

具體的基于

G

′構(gòu)建的CTG-tree索引的最短路徑查詢算法偽碼如算法3所示

.

算法3.

最短路徑查詢算法

CTGQ

(

T

,

s

,

s

′,

I

=[

t

,

t

])

.

輸入：基于

G

′構(gòu)建的CTG-tree索引

T

，查詢?cè)袋c(diǎn)

s

，目的點(diǎn)

s

′，時(shí)間間隔

I

=[

t

,

t

]；輸出：

s

在時(shí)間間隔

I

內(nèi)到達(dá)

s

′的最短時(shí)態(tài)路徑距離

.

⑦ end if

，

其中

5 實(shí)驗(yàn)分析

本節(jié)在真實(shí)的數(shù)據(jù)集上對(duì)所提出的CTGQ方法進(jìn)行實(shí)驗(yàn)測(cè)試，并與2種流行方法1-pass和TDFS進(jìn)行對(duì)比，以驗(yàn)證CTGQ的效率.

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

本文使用4個(gè)真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)測(cè)試，分別是GTFS數(shù)據(jù)集Transit，以及SNAP公開的數(shù)據(jù)集Bitcoin，Mathoverflow，Askubuntu.Transit數(shù)據(jù)集記錄了美國(guó)科羅拉多州丹佛縣班車數(shù)據(jù)，包括班車號(hào)、班車出發(fā)時(shí)間、到達(dá)時(shí)間，停靠站點(diǎn)等信息.Bitcoin數(shù)據(jù)集是一個(gè)who-trust-whom網(wǎng)絡(luò)，網(wǎng)絡(luò)中的頂點(diǎn)表示在一個(gè)名為比特幣OTC交易平臺(tái)上使用比特幣進(jìn)行交易的用戶；由于比特幣用戶是匿名的，為防止欺詐和風(fēng)險(xiǎn)用戶交易，用戶之間會(huì)進(jìn)行聲譽(yù)評(píng)分，因此網(wǎng)絡(luò)中的邊記錄一個(gè)用戶給另一個(gè)用戶的聲譽(yù)評(píng)分以及評(píng)分時(shí)間.Mathoverflow和Askubuntu數(shù)據(jù)集均為Stack Exchange下的互動(dòng)時(shí)態(tài)網(wǎng)絡(luò)，頂點(diǎn)表示用戶，從用戶

u

到用戶

v

的邊包含3種類型的互動(dòng)關(guān)系:用戶

u

在時(shí)間

t

回答了

v

的問題；用戶

u

在時(shí)間

t

評(píng)論了

v

的問題；用戶

u

在時(shí)間

t

評(píng)論了

v

的回答

.

表1給出了實(shí)驗(yàn)測(cè)試中用到數(shù)據(jù)集的統(tǒng)計(jì)信息

.

其中|

V

|,|

E

|,|

T

(

G

)|分別表示時(shí)態(tài)圖的頂點(diǎn)數(shù)、邊數(shù)和時(shí)態(tài)區(qū)間數(shù)

.

對(duì)于每個(gè)數(shù)據(jù)集，隨機(jī)選取500組查詢，查詢時(shí)間間隔默認(rèn)為

I

=[0,+∞],報(bào)道每個(gè)算法的平均查詢時(shí)間

.

Table 1 Statistics of the Datasets表1 數(shù)據(jù)集統(tǒng)計(jì)信息

本文將CTGQ與1-pass和TDFS進(jìn)行對(duì)比.1-pass算法和和TDFS均無(wú)需構(gòu)建索引，1-pass算法在轉(zhuǎn)化圖上運(yùn)用Dijkstra算法計(jì)算最短時(shí)態(tài)路徑；TDFS算法在原始時(shí)態(tài)圖上進(jìn)行深度優(yōu)先遍歷計(jì)算最短時(shí)態(tài)路徑；實(shí)驗(yàn)測(cè)試過程中，為取得較好的索引性能和查詢性能，4個(gè)數(shù)據(jù)集Transit，Bitcoin，Mathoverflow，Askubuntu默認(rèn)參數(shù)

l

=16;

θ

分別設(shè)置為128，64，256，128.本文所有實(shí)驗(yàn)程序均使用C++語(yǔ)言編寫，實(shí)驗(yàn)測(cè)試環(huán)境為一臺(tái)配置為英特爾至強(qiáng)CPU處理器E5-2650 v4，128 GB內(nèi)存，1 TB硬盤的服務(wù)器.

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

表2給出了原始數(shù)據(jù)集采用3.1節(jié)提出的規(guī)則進(jìn)行轉(zhuǎn)化和壓縮后得到的轉(zhuǎn)化圖和壓縮圖的大小.與表1數(shù)據(jù)進(jìn)行對(duì)比，可以看出轉(zhuǎn)化圖的頂點(diǎn)數(shù)是原始圖頂點(diǎn)數(shù)的4～97倍，轉(zhuǎn)化圖的邊數(shù)是原始圖邊數(shù)的2～4倍.相較于轉(zhuǎn)化圖，壓縮圖頂點(diǎn)數(shù)是轉(zhuǎn)化圖頂點(diǎn)的3～50倍，壓縮圖邊數(shù)是轉(zhuǎn)化圖邊數(shù)的2～3倍，說明了本文提出壓縮規(guī)則的有效性.

Table 2 Statistics of the Transformed Graph and the Compressed Graph

Fig. 5 Effect of Time Interval圖5 時(shí)間區(qū)間的影響

表3給出了CTG-tree索引構(gòu)建時(shí)間和空間代價(jià).可以看出，Transit數(shù)據(jù)集上構(gòu)建CTG-Tree索引需要時(shí)間不足1 s；Askubuntu數(shù)據(jù)集上構(gòu)建CTG-tree索引需要時(shí)間接近8 min.在4個(gè)真實(shí)數(shù)據(jù)集上，CTG-tree索引大小在20 MB到8.2 GB之間.

Table 3 CTG-tree Construction Cost and Space Overhead表3 CTG-tree索引構(gòu)建時(shí)間和空間代價(jià)

表4給出了CTGQ,1-pass和TDFS算法在4個(gè)數(shù)據(jù)集上的平均查詢時(shí)間.由表4可以觀察出，CTGQ查詢時(shí)間比1-pass平均快1個(gè)數(shù)量級(jí)，比TDFS平均快2個(gè)數(shù)量級(jí).這是因?yàn)?-pass算法與TDFS算法均需要在線遍歷搜索，1-pass算法需要在轉(zhuǎn)化圖上運(yùn)用Dijkstra算法計(jì)算2點(diǎn)之間的最短時(shí)態(tài)路徑;TDFS算法在計(jì)算最短時(shí)態(tài)路徑時(shí)，由于最短時(shí)態(tài)路徑的子路徑不滿足最優(yōu)子結(jié)構(gòu)性質(zhì)，所以TDFS需要遍歷的時(shí)態(tài)路徑是指數(shù)級(jí)的，耗時(shí)更長(zhǎng)；而CTGQ利用了CTG-tree索引進(jìn)行查詢，查詢過程中無(wú)需再遍歷壓縮圖，只需要根據(jù)CTG-tree索引矩陣即可得到結(jié)果，因此效率更高.

Table 4 Query Time表4 查詢時(shí)間 ms

本文實(shí)驗(yàn)驗(yàn)證了4個(gè)不同的時(shí)間間隔

I

(1≤

i

≤4)對(duì)最短時(shí)態(tài)路徑查詢時(shí)間的影響

.I

是數(shù)據(jù)集的最大時(shí)間間隔，

I

+1(1≤

i

≤3)是將

I

劃分為2個(gè)相等子區(qū)間后的第一個(gè)子區(qū)間.圖5給出了CTGQ,1-pass和TDFS算法在Transit，Bitcoin，Mathoverflow，Askubuntu數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果.

從圖5可以看到，CTGQ，1-pass和TDFS的查詢時(shí)間隨著時(shí)態(tài)區(qū)間的縮減而降低，TDFS下降趨勢(shì)最為顯著.這是因?yàn)闀r(shí)態(tài)區(qū)間縮減時(shí)，TDFS所需遍歷的時(shí)態(tài)路徑數(shù)目大幅度減少；而1-pass和CTGQ算法在壓縮圖上計(jì)算，時(shí)態(tài)區(qū)間減小時(shí)，1-pass算法遍歷的路徑長(zhǎng)度減小，CTGQ算法遍歷的CTG-tree矩陣索引計(jì)算量減少.

另外，從圖5還可以觀察到不同查詢時(shí)態(tài)區(qū)間下，CTGQ算法的性能始終遠(yuǎn)遠(yuǎn)優(yōu)于1-pass和TDFS算法的性能，這與前述實(shí)驗(yàn)分析結(jié)論一致.

本文考察了葉子子圖頂點(diǎn)數(shù)目閾值

θ

、迭代劃分子圖數(shù)目

l

對(duì)CTG-tree構(gòu)建和CTGQ算法運(yùn)行性能的影響.表5給出了4個(gè)數(shù)據(jù)集Transit，Bitcoin，Mathoverflow，Askubuntu在

θ

值分別設(shè)置為2，4，8，16，

l

值分別設(shè)置為32，64，128，256，512情況下的CTG-tree索引構(gòu)建時(shí)間和CTGQ算法運(yùn)行時(shí)間結(jié)果.

Table 5 Effects of θ and l表5 θ和l的影響 ms

首先由表5可以看到，當(dāng)

l

取固定值時(shí)，CTG-tree索引構(gòu)建時(shí)間隨著

θ

值增加呈減少趨勢(shì)

.

這是因?yàn)?p>θ

值增加，CTG-tree葉子節(jié)點(diǎn)對(duì)應(yīng)子圖的頂點(diǎn)數(shù)目增多，迭代劃分產(chǎn)生的總子圖數(shù)目減少，相應(yīng)的入邊界點(diǎn)、出邊界點(diǎn)總數(shù)減少，索引矩陣計(jì)算量減少，因此CTG-tree索引構(gòu)建時(shí)間降低.其次，由表5可以看出，當(dāng)

θ

取固定值時(shí)，CTG-tree索引構(gòu)建時(shí)間隨著

l

值增大基本呈先降低再升高的趨勢(shì)

.

這是因?yàn)殡S著

l

值的增大，CTG-tree每層節(jié)點(diǎn)數(shù)目增多，入邊界點(diǎn)、出邊界點(diǎn)總數(shù)先減少再增多，導(dǎo)致索引矩陣計(jì)算量先減小后增加.此外，當(dāng)

θ

取固定值時(shí)，CTGQ算法運(yùn)行時(shí)間隨著

l

值增大基本呈降低趨勢(shì)

.

這是因?yàn)椋?p>l

值增大，CTG-tree高度降低，CTGQ算法自底向上，自頂向下遍歷層數(shù)減少.鑒于上述觀察，為取得較好的索引性能和查詢性能，4個(gè)數(shù)據(jù)集默認(rèn)參數(shù)

l

=16;

θ

在數(shù)據(jù)集Transit，Bitcoin，Mathoverflow，Askubuntu上的值分別設(shè)置為128，64，256，128.

6 總 結(jié)

本文研究了時(shí)態(tài)圖最短路徑問題并提出了基于CTG-tree索引的計(jì)算方法，其主要包含預(yù)處理階段和在線查詢階段.在預(yù)處理階段，本文提出了一種無(wú)損壓縮方法和層次索引CTG-tree.其首先將時(shí)態(tài)圖轉(zhuǎn)化為普通圖，對(duì)普通圖進(jìn)行無(wú)損壓縮以減小圖處理規(guī)模，將時(shí)態(tài)圖上最短路徑計(jì)算轉(zhuǎn)化為在壓縮圖上執(zhí)行；而后對(duì)壓縮圖采用Metis劃分將壓縮圖層次劃分為若干個(gè)子圖，得到每個(gè)子圖的入邊界點(diǎn)與出邊界點(diǎn)集合，并基于此構(gòu)建CTG-tree.CTG-tree為每個(gè)葉子節(jié)點(diǎn)對(duì)應(yīng)子圖計(jì)算游入距離矩陣、游出距離矩陣和邊界點(diǎn)距離矩陣；為每個(gè)非葉節(jié)點(diǎn)對(duì)應(yīng)子圖計(jì)算出邊界點(diǎn)游入距離矩陣，入邊界點(diǎn)游入距離矩陣和邊界點(diǎn)游出距離矩陣.查詢階段本文基于CTG-tree索引設(shè)計(jì)了高效的最短路徑查詢算法.最后，在真實(shí)的時(shí)態(tài)圖數(shù)據(jù)集上進(jìn)行了全面的實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果驗(yàn)證了本文所提出的基于CTG-tree索引的算法的效率.此外，設(shè)計(jì)高效的分布式時(shí)態(tài)圖最短路徑方法與增量計(jì)算算法也是一個(gè)重要且值得研究的問題，后續(xù)工作計(jì)劃對(duì)其進(jìn)行深入地探索.

作者貢獻(xiàn)聲明

：張?zhí)烀髫?fù)責(zé)問題定義、方法設(shè)計(jì)、數(shù)據(jù)分析與論文撰寫修改工作；徐一恒負(fù)責(zé)數(shù)據(jù)收集與整理、實(shí)驗(yàn)結(jié)果可視化工作；蔡鑫偉負(fù)責(zé)部分實(shí)驗(yàn)測(cè)試和整理工作；范菁負(fù)責(zé)指導(dǎo)論文寫作并提出修改建議.