李文華 李盛恩

(山東建筑大學(xué)計算機科學(xué)與技術(shù)學(xué)院 山東 濟南 250100)

0 引 言

隨著移動智能終端和移動互聯(lián)網(wǎng)的普及,越來越多的業(yè)務(wù)和互聯(lián)網(wǎng)緊密結(jié)合起來。從社交網(wǎng)絡(luò)到智慧政務(wù),從餐飲娛樂到智能交通,人們在享受互聯(lián)網(wǎng)+帶來的無限便利的同時,每天也產(chǎn)生了海量的數(shù)據(jù)。這些數(shù)據(jù)具有以下特點:(1) 數(shù)據(jù)量大,存儲單位從過去的GB、TB級到現(xiàn)在的PB乃至EB級別。(2) 數(shù)據(jù)結(jié)構(gòu)多樣,大量數(shù)據(jù)為無結(jié)構(gòu)化數(shù)據(jù)、半結(jié)構(gòu)數(shù)據(jù)。(3) 數(shù)據(jù)產(chǎn)生速度快,對網(wǎng)絡(luò)傳輸?shù)男阅芤蟾?有些數(shù)據(jù)需要實時處理,對服務(wù)器的計算處理能力要求高。(4) 數(shù)據(jù)價值密度低[1]。

面對這些數(shù)據(jù),傳統(tǒng)的關(guān)系型數(shù)據(jù)庫在處理時顯得力不從心。為了更好地存儲和管理這些數(shù)據(jù),各種新型數(shù)據(jù)庫應(yīng)時而生。以Neo4J為代表的圖數(shù)據(jù)庫就是其中的一類,它以屬性圖作為邏輯存儲模型,憑借圖的獨特構(gòu)造,在存儲和管理如社交網(wǎng)絡(luò)、生物信息網(wǎng)絡(luò)、智能交通網(wǎng)絡(luò)等數(shù)據(jù)時發(fā)揮了重要作用。

在數(shù)據(jù)庫系統(tǒng)中,快速準(zhǔn)確地進行查詢是用戶的一項基本需求,為了滿足用戶的這一需求,傳統(tǒng)數(shù)據(jù)庫的設(shè)計和開發(fā)者為數(shù)據(jù)建立了各式各樣的索引,極大提高了查詢效率,現(xiàn)在已經(jīng)非常成熟。而圖數(shù)據(jù)中的查詢種類眾多,包括可達性查詢、最短路徑查詢、關(guān)鍵字查詢、匹配查詢等,近年來,針對這些查詢的研究得到了更多學(xué)者的關(guān)注。

可達性查詢研究的是圖中兩個頂點之間是否存在可達路徑,作為圖數(shù)據(jù)管理中使用最頻繁的操作,可達性查詢在子圖匹配查詢、生物信息學(xué)、社交網(wǎng)絡(luò)等領(lǐng)域中應(yīng)用廣泛[2-3]。但是對于一些現(xiàn)實中的問題,僅僅進行可達查詢并不能滿足用戶的需求,如在無線傳感器網(wǎng)絡(luò)、互聯(lián)網(wǎng)、電信網(wǎng)以及社交網(wǎng)絡(luò)中,頂點u對頂點v的影響力受制于從u到v的路徑長度(例如無線傳感器網(wǎng)絡(luò)的廣播消息可能在傳輸過程中的任何一步丟失,其他頂點接收到的概率會隨著路徑長度的增加以指數(shù)級速度衰減)[4],因此針對K步可達性查詢的研究逐漸增多。K步可達性查詢是在可達性查詢的基礎(chǔ)上,對兩頂點間的路徑長度限制至K,即回到兩點間是否存在一條長度不超過K的路徑。K步可達性查詢相比可達性查詢,不僅能反映頂點間是否存在影響,還能反映頂點間的影響程度,可以提供更多有用信息,在無線傳感器網(wǎng)絡(luò)、互聯(lián)網(wǎng)、電信網(wǎng)以及社交網(wǎng)絡(luò)等實際應(yīng)用中應(yīng)用廣泛,具有較高的實用價值。

近年來,隨著研究的深入,已有多個K步可達性查詢算法先后被提出,但是這些算法的研究對象均為無權(quán)圖。而在一些現(xiàn)實問題中,我們要處理的往往是帶權(quán)重的圖數(shù)據(jù),如前文提到的傳感器網(wǎng)絡(luò)、社交網(wǎng)絡(luò)、交通網(wǎng)絡(luò)等,在這些網(wǎng)絡(luò)中,權(quán)重可以表示傳感器間的距離、功率損耗,社交網(wǎng)絡(luò)中人與人之間的親密程度,交通網(wǎng)絡(luò)中兩城市間的距離、油耗等。此外,有些算法的研究對象限定為有向無環(huán)圖,如果圖數(shù)據(jù)中存在環(huán),則通過壓縮強連通分量構(gòu)造為有向無環(huán)圖,這在K步可達性查詢中并不合理;有些算法在構(gòu)建索引時需提前指定查詢步數(shù)K,且針對每個K構(gòu)建的索引只適合K步以內(nèi)的查詢,在查詢時不能靈活地更改查詢步數(shù)K。

針對以上問題,本文提出了一種針對帶權(quán)有向圖的K步可達性查詢算法,能在常數(shù)時間內(nèi)完成大部分K步可達性查詢。具體來說,本文的貢獻如下:(1) 根據(jù)現(xiàn)實問題,提出了帶權(quán)有向圖上的K步可達性查詢,以雙向最短路徑索引和K-Reach索引為基礎(chǔ)設(shè)計了高效索引,能在常數(shù)時間完成大部分K步可達性查詢。(2) 研究對象不再局限于有向無環(huán)圖,對于帶環(huán)圖也可以正常處理;構(gòu)建索引時,不需要提前指定查詢步數(shù)K,并且在查詢時可以靈活改變查詢步數(shù)K。(3) 基于多個真實圖數(shù)據(jù)進行測試,通過與無權(quán)圖上的K步可達性查詢算法對比,實驗結(jié)果表明本文算法高效可行。

1 背景知識和相關(guān)工作

1.1 背景知識

本文的研究對象為帶權(quán)有向圖G=(V,E),其中V是G的頂點集合,V中的頂點用u、v等小寫英文字母表示,E是G的有向邊集,E中的有向邊用(〈u,v〉,w)表示,其含義是從u到v的一條有向邊,w為邊上權(quán)重。IN(u)表示指向頂點u的頂點集,OUT(u)表示頂點u指向的頂點集,wpath(u,v)表示從u到v的路徑長度,即從u到v所經(jīng)過邊的權(quán)重之和。

本文要處理K步可達性查詢,即查詢給定的圖G中的兩個頂點u和v,是否存在一條從u到v且長度不超過K的路徑,若存在,則稱uK步可達v,用u→kv表示。若不存在,則稱uK步不可達v,用u→/kv表示。

1.2 相關(guān)工作

根據(jù)索引類型進行分類,可將目前已有的K步可達性查詢算法分為兩類。第一類是基于可達性的K步可達性查詢算法,該類方法的基本思想是以可達性查詢結(jié)果作為否定剪枝條件,如果通過可達性查詢判斷出兩頂點u和v不可達,則兩頂點一定K步不可達;如果可達性查詢結(jié)果為可達,則結(jié)合輔助索引做進一步判斷。第二類基于頂點覆蓋集的K步索引方法,其基本思想是首先求出原圖的一個頂點覆蓋集,然后根據(jù)原圖中的可達性,在頂點覆蓋集上建立K步可達索引。在查詢時,根據(jù)頂點u和v是否屬于頂點覆蓋集,將查詢分為四種情況,再利用建立的索引實現(xiàn)快速查詢。

1.2.1基于可達性的K步可達性查詢算法

基于可達性的K步可達性查詢算法以可達性查詢?yōu)榛A(chǔ),在構(gòu)建索引時,首先通過壓縮強連通分支,將原圖轉(zhuǎn)換為有向無環(huán)圖,然后在有向無環(huán)圖上構(gòu)建可達性查詢索引和一些輔助索引。在查詢時,該類方法以可達性查詢結(jié)果作為否定剪枝條件,首先通過可達性查詢判斷出兩頂點u和v是否可達,如果不可達,則兩頂點一定K步不可達;若可達,則利用輔助索引進一步判斷,若通過輔助索引的查詢結(jié)果為不可達,則兩頂點一定K步不可達,若輔助索引的結(jié)論果仍為可達,則依次判斷以頂點u的為弧尾的相鄰頂點集中的點是否K-2步內(nèi)可達以頂點v為弧首的相鄰頂點集中的點,若是,則u可以K步可達v,否則u不可K步可達v。該類方法的典型代表有BiRch算法[4-5]、kRH算法[6]、BFSI算法[7]、RE-GRAIL算法[8]。

BiRch算法以著名的可達性算法GRAIL[9,10]為基礎(chǔ),其基本思想是:首先對有向無環(huán)圖分別進行從左到右和從右到左的后根遍歷,每個頂點兩次后根遍歷的次序分別作為其兩個區(qū)間的上界post,而區(qū)間的下界為其子節(jié)點區(qū)間的下界的最小值min,若該頂點為葉子節(jié)點,則其區(qū)間下界和上界相等,這樣就構(gòu)建起單向雙區(qū)間的可達性索引。為了加速查詢,該算法索引中還包含了每個頂點的雙向廣度層數(shù)和雙向拓撲層數(shù)。在查詢時,首先根據(jù)可達性查詢判斷兩點是否可達,如果不可達,則得出結(jié)論,兩點K步不可達,否則,利用雙向廣度層數(shù)和雙向拓撲層數(shù)進行判斷,若仍不能判斷出結(jié)果,則遞歸地從兩頂點出度或入度較小的一側(cè)向另一側(cè)查找,遞歸結(jié)束的條件是遞歸次數(shù)達到K或查到另一個頂點。

kRH算法以PLL算法[11-13]為基礎(chǔ),其基本思想是為部分度大的頂點構(gòu)建雙向最短路徑索引。首先選取部分度大的頂點(這些點稱為HOP點),根據(jù)實驗,當(dāng)一幅圖中選擇的度大的節(jié)點數(shù)達到32個時,要么這些節(jié)點維護的可達性信息已經(jīng)足夠多,要么再增加節(jié)點也不會顯著增加可達性信息。然后利用廣度優(yōu)先遍歷為這些HOP頂點分別建立兩個標(biāo)簽LIN和LOUT(u),前者存儲圖中可達u的頂點及其到u的路徑長度,后者存儲u可達的頂點及其路徑長度。為了快速判斷不可達,本文在索引中為非HOP點添加了正反互逆拓撲號。在查詢時,對于給定的點u和v,如果至少有一個為HOP點,則直接查找其與另一個點的路徑長度,判斷路徑長度是否小于或等于K,若是則兩點K步可達,否則K步不可達;若兩點均不為HOP點,則利用正反互逆拓撲號進行判斷,若判斷結(jié)果為不可達,則說明兩點K步不可達,否則借助原圖遞歸地從兩頂點出度或入度較小的一側(cè)向另一側(cè)查找,直到遞歸次數(shù)達到K或查到另一個頂點。

BFSI算法以GRIPP[14]和FELINE[15]算法為基礎(chǔ),首先利用可達性算法構(gòu)建FELINE索引,然后將原圖生成廣度優(yōu)先森林,對廣度優(yōu)先森林中的每一個棵樹進行后根遍歷,構(gòu)建min-post間隔標(biāo)簽索引,最后對每棵樹進行廣度優(yōu)先遍歷,得到每一個頂點的全局廣度層數(shù)。在查詢時,對給定的兩點u和v,步長K,先利用FELINE索引進行可達性查詢,如果查詢結(jié)果為兩點不可達,則得到兩點一定K步不可達,否則利用min-post索引的包含關(guān)系進行判斷;如果點u的min-post間隔標(biāo)簽包含點v的標(biāo)簽,則判斷u的全局廣度層數(shù)減點v得到的值是否小于步長K,如果是,則兩點K步可達,否則不可達;如果點u的min-post間隔標(biāo)簽不包含點v的標(biāo)簽,則從點u的出度和點v的入度兩者中小的一側(cè)進行遞歸的搜索,直到得出結(jié)論。

RE-GRAIL算法同樣以可達性算法GRAIL[9-10]為基礎(chǔ),結(jié)合文獻[16]中的算法。在構(gòu)建索引時,首先對有向無環(huán)圖進行從左到右的后根遍歷,為每個頂點構(gòu)建一個區(qū)間,然后將有向無環(huán)圖反向再進行一次從左到右的后根遍歷,為每個頂點再構(gòu)建一個區(qū)間,這樣就構(gòu)建起了雙向雙區(qū)間標(biāo)簽索引。在查詢時,對于給定的兩點u和v,仍然是先根據(jù)可達性查詢判斷兩點是否可達,如果不可達,則一定K步不可達,否則遞歸地判斷u的子節(jié)點是否K-1步可達v直到得到結(jié)果。

基于可達性的K步可達性查詢算法,充分利用可達性查詢,巧妙地結(jié)合一些剪枝策略,算法簡明清晰,然而在實際中,頂點之間或多或少存在某種聯(lián)系,可達性查詢大多會返回肯定的結(jié)果[17],因此剪枝效果并不理想。并且其研究對象為有向無環(huán)圖,這并不符合實際應(yīng)用情況,在可達性查詢中,因為強連通分支內(nèi)頂點都是相互可達的,可以通過壓縮強連通分量,將普通有向圖轉(zhuǎn)為有向無環(huán)圖,但在K步可達性查詢中,壓縮強連通分支變得不合理,比如在K步可達性查詢中重要應(yīng)用交通路網(wǎng)中,如果假設(shè)路網(wǎng)為有向無環(huán)圖,那么意味著從一個城市出發(fā)即再也無法回到該城市,這顯然不符合常理。

1.2.2基于頂點覆蓋集的K步索引方法

文獻[18-19]提出了基于頂點覆蓋集的K步索引方法K-Reach,該方法的基本依據(jù)是一條邊的兩個頂點,至少有一個在頂點覆蓋集中。在構(gòu)建索引時,該方法首先要確定查詢步數(shù)K,然后對給定的圖G求近似最小頂點覆蓋集S,求出頂點覆蓋集S中頂點在原圖中的所有路徑及長度,將路徑長度不超過K的路徑和路徑長度作為帶權(quán)有向邊,保存為索引,此外索引中還包含近似最小頂點覆蓋集S,所以該方法的索引由頂點集S和帶權(quán)有向邊集構(gòu)成。在查詢時,對于給定的兩個頂點u和v是否在頂點覆蓋集S中,將查詢分為四種情況,當(dāng)u和v均屬于頂點覆蓋集S時,直接查詢〈u,v〉的路徑長度并與K值進行大小比較,若路徑長度小于或等于K值,則u可以K步可達v,否則u不可K步可達v;當(dāng)u屬于頂點覆蓋集S,但v不屬于S時,依次取IN(v)中的頂點t,因為v不屬于S,所以t一定屬于頂點覆蓋集S,所以直接查詢〈u,t〉的路徑長度并與K-1進行大小比較,若路徑長度小于或等于K-1,則u可以K步可達v,否則u不可K步可達v;當(dāng)u不屬于頂點覆蓋集S,但v屬于S時,依次取OUT(u)中的頂點s,因為u不屬于S,所以s一定屬于頂點覆蓋集S,所以直接查詢〈s,v〉的路徑長度并與K-1進行大小比較,若路徑長度小于或等于K-1,則u可以K步可達v,否則u不可K步可達v;當(dāng)u和v均不屬于頂點覆蓋集S時,依次取OUT(u)中的頂點s和IN(v)中的頂點t,查詢〈s,t〉的路徑長度并與K-2進行大小比較,若路徑長度小于或等于K-2,則u可以K步可達v,否則u不可K步可達v。

K-Reach方法的研究對象不再局限于有向無環(huán)圖,利用指定K值構(gòu)造出來的索引,也能提供較好的查詢效率,但是其仍不能解決帶權(quán)圖上的K步可達性查詢,同時構(gòu)造索引時需要提前指定K值,查詢時K值不能靈活更改等問題使得該算法難以在實踐中應(yīng)用。

2 基本思想和算法描述

2.1 索引構(gòu)建算法

本文提出的針對帶權(quán)有向圖的K步可達性查詢算法,首先求解給定圖的近似最小頂點覆蓋集,然后基于頂點覆蓋集構(gòu)建索引,類似于文獻[15]提出的算法,與之不同的是,本文的研究對象由簡單有向圖變?yōu)閹?quán)有向圖,在構(gòu)建索引時也不需要提前指定K值。除了頂點覆蓋集上的索引外,為了避免在查詢過程中的I/O操作,提高查詢效率,本文還構(gòu)建了頂點覆蓋集外的雙向最短路徑索引。

2.1.1求解近似最小頂點覆蓋集

根據(jù)文獻[20]的證明,最小頂點覆蓋問題屬于NPC類問題,通常一個問題若被證明為NPC類,人們認為該問題不能在多項式時間內(nèi)解答。雖然無法準(zhǔn)確求解圖的最小頂點覆蓋集,但是可以在多項時間內(nèi)求解圖的近似最小頂點覆蓋集。文獻[15]給出了一個求解近似最小頂點覆蓋集的樸素算法,即從邊集中任選一邊〈u,v〉,將該邊的兩頂點u、v依次加入到頂點覆蓋集S中,然后將頂點u或v能覆蓋到的邊從邊集中全部刪除,重復(fù)上述過程,直到邊集為空,這樣就得到了一個頂點覆蓋集。該算法簡單易懂,但得到的頂點覆蓋集往往規(guī)模偏大。本文采用貪心算法來求解近似最小頂點覆蓋集,首先計算圖中各頂點的度,選出度最大的頂點,然后將該頂點加入到頂點覆蓋集中,并將該頂點覆蓋到的邊從邊集中全部刪除,在刪除過程中,對相關(guān)頂點的度進行調(diào)整,重復(fù)上述過程,直到邊集為空。具體如算法1所示。

算法1近似最小頂點覆蓋集算法

輸入:帶權(quán)有向圖G=(V,E)

輸出:近似最小頂點覆蓋集S

1. /*初始化各頂點的度*/

2. for each nodeuinVdo

3. Array[u]←getdegree(u)

4. /*求近似最小頂點覆蓋集*/

5. WhileEis not empty do

6. findvwhich has biggest degree

7. addvintoS

8. for each nodesin OUT(v) or IN (v) do

9. delete( or )

10. Array[s]—

需要說明的是,在求解近似最小頂點覆蓋集的過程中,因為邊的方向和權(quán)重不起作用,我們可以將其暫時忽略。如圖1所示,最小頂點覆蓋集由灰色頂點構(gòu)成。

圖1 帶權(quán)有向圖G(灰色點構(gòu)成頂點覆蓋集S)

本文采用的求解近似最小的頂點覆蓋集的貪心算法的時間復(fù)雜度為O(mn),不如文獻[15]給出的樸素算法時間復(fù)雜度O(m+n),但該算法求解的頂點覆蓋集更小,有利于保證接下來的索引構(gòu)建過程的時間和空間效率。

2.1.2構(gòu)建索引

基于上一節(jié)得到的近似最小頂點覆蓋集,進行索引構(gòu)建,具體如算法2所示。最終構(gòu)建的索引由三部分構(gòu)成,分別是近似最小頂點覆蓋集S、S內(nèi)索引和S外索引。其中近似最小頂點覆蓋集S已經(jīng)求出,可直接加入到索引中。

算法2索引構(gòu)建算法

輸入:帶權(quán)有向圖G=(V,E)。

輸出:Index=(S,Es,Eout)。

1./*求近似最小頂點覆蓋集*/

2.Compute the approximate min vertex coverS

3.*求S內(nèi)頂點間的最短路徑*/

4.for each nodeuinSdo

5.ComputeEs={(,w)|v∈S,w=wpath(u,v)}

through BFS(u,G)

6./*求S外的索引*/

7.for each nodeunot inSdo

8.for each nodevinOUTI(u) do

9.u.outadd(v,w)

10.for each nodevinINI(u) do

11.u.inadd((v,w)

表1 頂點覆蓋集S內(nèi)索引

S外索引類似于kRH算法中的雙向最短路徑索引,具體構(gòu)建過程如下,對S外的每一個頂點u,依次訪問OUT(u)或IN(u)內(nèi)頂點v,因為u不屬于S,所以v一定屬于S,將(v,w)加入到S外索引的OUTI(node,weight)或INI(node,weight)中。最終構(gòu)建的S外索引如表2所示。S外是該索引的重要組成部分,借助該部分,本算法可以實現(xiàn)在不訪問原圖的情況下,完成K步可達查詢操作。雖然該部分索引在一定程度上增大了索引的規(guī)模,但是有效避免了I/O操作,大幅提高了查詢效率。通過分析易知,其時間復(fù)雜度為|V-S|max{|OUT(u)|,|IN(u)|}。

表2 頂點覆蓋集S外索引

2.2 查詢處理

對于給定的兩頂點u、v和路徑長度K,根據(jù)u和v是否屬于近似最小頂點覆蓋集S,將查詢分為四種情況:(1) 若u和v均屬于S,則直接查詢S內(nèi)索引得到wpath(u,v),若wpath(u,v)≤K,則uK步可達v,否則uK步不可達v。(2) 若u屬于近似最小頂點覆蓋集S,而v不屬于S,則首先判斷S外索引中的v的入邊頂點集INI(v)是否為空,若INI(v)為空,則uK步不可達v,否則依次遍歷頂點v的入邊頂點集INI(v)中的點t,判斷是否存在t使得wpath(u,t)+get(t)≤K,若存在這樣的點t,則uK步可達v,否則uK步不可達v。(3) 若u不屬于近似最小頂點覆蓋集S,而v屬于S,同樣首先判斷S外索引中的u的出邊頂點集OUTI(u)是否為空,若OUTI(u)為空,則uK步不可達v,否則依次遍歷頂點u的出邊頂點集OUTI(u)中的點s,判斷是否存在s使得wpath(u,s)+get(s)≤K,若存在這樣的點s,則uK步可達v,否則uK步不可達v。(4) 若u和v均不屬于頂點覆蓋集S,則首先判斷S外索引中的u的出邊頂點集OUTI(u)或v的入邊頂點集INI(v)是否為空,若二者任意一個為空,則uK步不可達v,否則依次遍歷頂點u的出邊頂點集OUTI(u)中的點s和頂點v的入邊頂點集INI(v)中的點t,判斷是否存在點s和點t使得get(u)+wpath(s,t)+get(v)≤K,若存在這樣的點s和t,則uK步可達v,否則uK步不可達v。具體如算法3所示。

算法3查詢算法

輸入:Index=(S,Es,Eout);頂點u和v,步長K。

輸出:True of False。

1./*頂點uv均屬于S*/

2.if (u∈Sandv∈S)

3.d=getwpath(u,v)

4.if (d<=K) return true

5.else return flase

6./*頂點u屬于S,v不屬于*/

7.if (u∈Sandv?S)

8.ifINI(v) is empty return false

9.for (tinINI(v))

10.d=getwpath(u,t)+get(t)

11.if (d<=K) return true

12.else return false

13./*頂點u不屬于S,v屬于*/

14.if (u?Sandv∈S)

15.ifOUTI(u) is empty return false

16.for (sinOUTI(u))

17.d=getwpath(u,s)+get(s)

18.if (d<=K) return true

19.else return false

20./*頂點u和v均不屬于S*/

21.if (u?Sandv?S)

22.ifOUTI(u) orINI(v) is empty

return false

23.for (sinOUTI(u))

24.for (tinINI(v))

25.d=get(s)+getwpath(s,t)

+get(t)

26.if (d<=K) return true

27.else return false

例如要查詢圖1中的頂點2和5是否3步內(nèi)可達,因為頂點3不在頂點覆蓋集中,而頂點5在,所以首先判斷頂點3的出邊頂點集是否為空,發(fā)現(xiàn)頂點3的出邊頂點集不為空且由頂點4構(gòu)成,所以根據(jù)S外索引得到get(4)=1,根據(jù)S內(nèi)索引得到wpath(4,5)=2,兩者求和得到的路徑長度為3,與給定的步長相等,所以頂點2,3步可達頂點5。

3 實 驗

3.1 實驗環(huán)境和實驗數(shù)據(jù)

本實驗所用的計算機配置為Pentium(R) Dual-Core CPU E6600處理器,主頻3.06 GHz,8 GB內(nèi)存,500 GB機械硬盤,Windows 10教育版操作系統(tǒng)。本實驗所用算法均由Java語言實現(xiàn),JDK版本為1.8.0_181。

本文選取了K步可達性查詢中常用的10個數(shù)據(jù)集,用于性能測試,包括FAA、FIGEYS、OpenFlights、DBLP、Linux、Google Plus、CornCitation、Ego_Twitter、USAirport、MorenoHealth,這些數(shù)據(jù)全部來自科布倫茨網(wǎng)絡(luò)數(shù)據(jù)集(http://konect.uni-koblenz.de/),其中FAA、OpenFlights、USAirport是航空路網(wǎng),DBLP、CornCitation、Linux是引用網(wǎng)絡(luò),Google Plus、Ego_Twitter、MorenoHealth是社交網(wǎng)絡(luò),FIGEYS是人類蛋白質(zhì)網(wǎng)絡(luò)。FAA、DBLP、Linux網(wǎng)絡(luò)中存在回路。OpenFlights、Linux、USAirport、MorenoHealth為平均度超過10的稠密圖。USAirport和MorenoHealth網(wǎng)絡(luò)中自帶權(quán)重信息,其他網(wǎng)絡(luò)中權(quán)重由本文利用隨機函數(shù)添加。各數(shù)據(jù)集的統(tǒng)計信息如表3所示,其中|V|代表圖中頂點數(shù),|E|代表邊數(shù),Average Degree為各頂點的平均度數(shù)。

表3 數(shù)據(jù)集統(tǒng)計信息

因為目前還沒有針對帶權(quán)有向圖上的K步可達性查詢算法,同時考慮到大部分已有算法的處理對象為有向無環(huán)圖,可比性不強,本文選擇與可以處理帶環(huán)有向圖的K-Reach算法進行比較,其中參數(shù)K設(shè)為10,通過索引構(gòu)建時間、索引規(guī)模、查詢時間三個指標(biāo)進行性能評價。本文所列出的所有數(shù)據(jù)均為算法執(zhí)行10次的平均值并通過四舍五入保留到小數(shù)點后兩位,表中KRAWG為本文中提出的算法。

3.2 索引構(gòu)建時間和規(guī)模

表4給出了兩種算法所求的頂點覆蓋集規(guī)模,通過比較發(fā)現(xiàn),采用優(yōu)先選擇度大頂點的貪心算法求解得到的頂點覆蓋集規(guī)模明顯小于樸素算法得到的頂點覆蓋集規(guī)模,平均降低約35%。

表4 頂點覆蓋集規(guī)模

表5給出了兩種算法的索引構(gòu)建時間,從索引構(gòu)建時間可以發(fā)現(xiàn),在稀疏圖上,KRAWG算法與K-Reach的相比略占上風(fēng),但差別不大。但在稠密圖上,KRAWG算法的優(yōu)勢比較明顯,索引構(gòu)建時間平均降低約50%。這主要得益于KRAWG算法在求解近似最小頂點覆蓋集時采用了優(yōu)先選擇度大頂點加入頂點覆蓋集的貪心算法,有效降低了頂點覆蓋集中頂點數(shù)量,從而減少了構(gòu)造比較費時的頂點覆蓋集內(nèi)索引規(guī)模,提高了索引構(gòu)建效率。

表5 索引構(gòu)建時間 單位:ms

表6給出了兩種算法構(gòu)造的索引規(guī)模,從索引規(guī)模來看,兩種算法不相上下,KRAWG算法整體具有一定優(yōu)勢,主要是因為隨著頂點覆蓋集內(nèi)索引規(guī)模的減少,頂點覆蓋集外索引規(guī)模逐漸上升,所以索引總規(guī)模保持相對穩(wěn)定。

表6 索引規(guī)模

3.3 查詢時間

表7給出了兩種算法在步長K=10時,隨機生成1萬個頂點對進行查詢的結(jié)果,表中數(shù)據(jù)為1萬次查詢時間之和。可以發(fā)現(xiàn),在查詢時間方面,兩種算法效率相當(dāng),雖然KRAWG算法在查詢過程中需要計算路徑長度,但有限次的簡單算術(shù)計算并不影響算法整體查詢效率。

表7 查詢時間 單位:ms

表8給出了KRAWG算法在K值分別為5、10、15時的查詢時間,可以發(fā)現(xiàn)K值的變化對于算法的查詢時間影響不大,這是因為KRAWG算法在頂點覆蓋集上構(gòu)建的索引與K值無關(guān),不論K值如何變化,查詢操作不會變化。

表8 不同K值的查詢時間 單位:ms

4 結(jié) 語

本文針對K步可達性查詢在實際應(yīng)用中存在的問題,吸收已有K步可達性查詢算法——K-Reach算法和KRH算法的優(yōu)勢,提出了帶權(quán)有向圖上的K步可達性查詢算法KRAWG,并通過實驗驗證了算法的高效性。帶權(quán)有向圖上的K步可達性查詢因為涉及到權(quán)重,需要額外空間進行存儲,索引規(guī)模相對較大,如何在保證查詢效率的前提下,盡可能壓縮索引空間,值得進一步研究。