成夢(mèng)佳，杜 明，周軍鋒

(東華大學(xué)，上海 松江 200000)

0 引言

互聯(lián)網(wǎng)技術(shù)的發(fā)展與應(yīng)用，催生出了海量的數(shù)據(jù)[1-2]。圖作為一種常見的數(shù)據(jù)結(jié)構(gòu)，能夠較好地抽象描述數(shù)據(jù)之間的關(guān)聯(lián)性。因此，圖被廣泛應(yīng)用在各個(gè)領(lǐng)域中，如通信網(wǎng)絡(luò)、生物信息網(wǎng)絡(luò)、道路網(wǎng)絡(luò)等[3-5]。

傳統(tǒng)的可達(dá)性查詢[6-11]用來回答給定的源點(diǎn)和終點(diǎn)之間是否存在可達(dá)的路徑。但是實(shí)際網(wǎng)絡(luò)中，頂點(diǎn)和邊往往都會(huì)包含權(quán)值，例如通信網(wǎng)絡(luò)中站點(diǎn)間的通訊交流就是通過帶寬約束，保證多媒體流端到端的服務(wù)質(zhì)量。因此，在回答可達(dá)性查詢時(shí)考慮權(quán)值約束更貼合實(shí)際，有較高的研究?jī)r(jià)值。

現(xiàn)有的基于權(quán)值約束的可達(dá)性查詢相關(guān)是Edge_Index[12]，它的主要思想是通過邊上的權(quán)值構(gòu)建索引樹，預(yù)先存儲(chǔ)先序遍歷索引樹得到的序列，盡管該算法的查詢效率很高，但是構(gòu)建的索引占用的空間內(nèi)存過大，無法在內(nèi)存有限的環(huán)境下處理頂點(diǎn)規(guī)模大的數(shù)據(jù)圖。

針對(duì)以上問題，本文提出一種基于權(quán)值約束的 2-hop索引算法。該算法基于頂點(diǎn)的度來確定頂點(diǎn)的處理順序，然后基于該順序來構(gòu)建加權(quán)圖的 2-hop索引。其基本思想是將加權(quán)圖上的權(quán)值約束可達(dá)查詢轉(zhuǎn)換為基于頂點(diǎn)標(biāo)簽的集合交集操作，從而減小構(gòu)建索引的時(shí)間和空間代價(jià)。實(shí)驗(yàn)結(jié)果表明，本文提出的方法能有效地降低索引規(guī)模，提高回答查詢的響應(yīng)速度。

1 問題定義和相關(guān)工作

1.1 相關(guān)概念和問題定義

本文基于無向加權(quán)圖處理權(quán)值約束可達(dá)性查詢的問題。給定無向加權(quán)圖G=(V,E,∑,w)，其中，V表示圖G中的頂點(diǎn)集合，E表示G中無向邊的集合，∑表示G中權(quán)值的集合，w表示每條邊上的權(quán)值。下文中，用e=(u,v)∈E表示從頂點(diǎn)u到頂點(diǎn) v的一條邊；P(u,v)表示 u到 v的路徑；Label(v)={(v1,w1),…,(vi,wi)}表示頂點(diǎn)v的標(biāo)簽集，其中 wi表示 v到 vi的路徑上的權(quán)值；規(guī)定查詢q=(u,v,C)，其中u、v∈V表示兩個(gè)查詢的頂點(diǎn)，C是隨機(jī)值表示邊上權(quán)值約束，可以為≤y、≥x或者[x,y]三種形式。

問題定義 給定一個(gè)無向帶權(quán)圖G和一個(gè)權(quán)值約束查詢q，如果從頂點(diǎn)u到頂點(diǎn)v存在一條路徑，路徑上每條邊的權(quán)值都滿足約束 C，則說明u可達(dá)v，否則不可達(dá)。

1.2 相關(guān)工作

1.2.1 傳統(tǒng)可達(dá)性查詢

可達(dá)性查詢的相關(guān)算法研究可以根據(jù)頂點(diǎn)的覆蓋情況分為兩類：全覆蓋索引（Label-only）和部分索引覆蓋（Label-G）[13]。

Label-only的主要思想是給圖上的每個(gè)頂點(diǎn)都構(gòu)建索引，索引中包含相關(guān)的可達(dá)信息。處理查詢時(shí)，通過判斷索引中是否存在交集，存在即可達(dá)，否則不可達(dá)。Label-only類的經(jīng)典算法主要有PLL[14]算法、TF[15]算法、Path Hop[10]算法。以PLL[14]算法為例，它的主要思路是利用BFS預(yù)先為圖上每個(gè)頂點(diǎn)分別構(gòu)建 Lin(v)和 Lout(v)標(biāo)簽，Lin(v)表示頂點(diǎn) v可以到達(dá)的其他頂點(diǎn)，Lout(v)表示可以到達(dá)v的所有頂點(diǎn)。通過判斷兩個(gè)頂點(diǎn)的出度標(biāo)簽和入度標(biāo)簽是否有交集，來查詢可達(dá)。PLL方法的索引大小為 O(L×|V|)，索引時(shí)間為 O(L×|V|×(|V|+|E|))，查詢時(shí)間為 O(L)，其中L表示標(biāo)簽元素個(gè)數(shù)。

Label-G方法則通過在部分頂點(diǎn)上構(gòu)建索引，以減少遍歷全圖的時(shí)間。查詢時(shí)，如果該索引可以回答查詢就直接返回結(jié)果，否則需要在圖上進(jìn)行BFS或DFS遍歷來得到結(jié)果。Label-G類的經(jīng)典算法主要有 GRAIL[16]算法、FELINE[17]算法和IP+[18]算法。以FELINE[17]為例，它的核心思想是利用兩個(gè)拓?fù)渑判?x,y)去給圖上的每個(gè)頂點(diǎn)賦予標(biāo)簽，第一個(gè)拓?fù)渑判蚴强紤]頂點(diǎn)的入度得到 x的拓?fù)漤樞?，第二個(gè)拓?fù)漤樞騽t是基于x的結(jié)果得到y(tǒng)的拓?fù)錁?biāo)簽。只有當(dāng)滿足頂點(diǎn)u的x和y拓?fù)錁?biāo)簽都分別小于頂點(diǎn)v的兩個(gè)相對(duì)應(yīng)的拓?fù)錁?biāo)簽，才能說明頂點(diǎn) u可達(dá)頂點(diǎn) v，否則說明頂點(diǎn)u和頂點(diǎn)v之間不可達(dá)。FELINE方法的索引空間復(fù)雜度為 O(|V|)，索引構(gòu)造時(shí)間復(fù)雜度為O(|E|+|V|×log|V|)，查詢時(shí)間復(fù)雜度為 O(|V|+|E|)。

1.2.2 權(quán)值約束可達(dá)性查詢

權(quán)值約束可達(dá)性查詢用于回答在頂點(diǎn) u和 v之間是否存在一條路徑，它每條實(shí)值邊上的權(quán)值均滿足給定的權(quán)值約束。Miao提出了一種新的構(gòu)建索引的方法 Edge_Index[12]，其主要思想是基于生成樹構(gòu)建一個(gè)索引樹，通過LCA[19]和RMQ方法求解兩個(gè)頂點(diǎn)u、v構(gòu)成區(qū)間的最值，即兩個(gè)頂點(diǎn)的最近公共祖先，得到該祖先結(jié)點(diǎn)的 Label值與給定的權(quán)值約束進(jìn)行比較。若 Label滿足約束，則證明u可達(dá)v，反之不可達(dá)。

Edge_Index算法構(gòu)建索引的時(shí)間復(fù)雜度為O(|∑||E|)，索引的空間復(fù)雜度為O(|∑||V|2)，查詢時(shí)間為O(1)。盡管該方法的查詢響應(yīng)時(shí)間較快，但是它構(gòu)建索引時(shí)需要預(yù)先存儲(chǔ)索引樹上結(jié)點(diǎn)的序號(hào)和標(biāo)簽，當(dāng)圖的頂點(diǎn)規(guī)模足夠大時(shí)，仍然會(huì)超出內(nèi)存。換言之，該方法無法在有限的內(nèi)存環(huán)境下處理大規(guī)模的數(shù)據(jù)圖。

2 基于權(quán)值約束的算法

2.1 權(quán)值約束的索引策略

需要注意的是，實(shí)際應(yīng)用中的權(quán)值約束有多種形式，如半有界區(qū)域≤y、≥x或有界區(qū)間[x,y]。在處理上，由于≤y和≥x是對(duì)稱的，因此本文預(yù)先假設(shè)查詢 q=(u,v,C)中的約束 C的形式為≤y，后文中將會(huì)證明本文提出的方法可以很容易地?cái)U(kuò)展到有界區(qū)間[x,y]的處理上。

對(duì)于權(quán)值約束的可達(dá)性查詢q=(u,v,C)，需要找到頂點(diǎn)u和頂點(diǎn)v之間某一條路徑，該路徑上所有邊的權(quán)值都滿足約束 C。不難想到，一種直接的方法就是枚舉出頂點(diǎn)u到頂點(diǎn)v的路徑?？紤]到每條路徑上的權(quán)值與約束之間的關(guān)系是不確定的，所以在列舉 P(u,v)時(shí)需要枚舉出所有存在的路徑，然后判斷每一條路徑是否滿足約束，當(dāng)某條路徑滿足條件時(shí)，就給出回答；當(dāng)遍歷完所有的路徑仍不滿足約束，則給出不可達(dá)的結(jié)論。

如圖1所示，當(dāng)回答查詢 q=(a,g,≤4)時(shí)，可得出 P1(a,g)=(a,f,b,g)、P2(a,g)=(a,f,g)、P3(a,g)=(a,f,d,b,c,g)。然后從多條不同的路徑中，判斷是否存在一條路徑，其每條邊上的權(quán)值都≤4，可知P3滿足，即頂點(diǎn)a、g存在滿足約束條件的路徑，說明在權(quán)值約束下點(diǎn) a可以到達(dá)點(diǎn) g；若每一條路徑都不滿足條件，則說明a不可達(dá)g。

圖1 無向加權(quán)圖GFig.1 Undirected weight graph G

從圖 1中可以發(fā)現(xiàn)，任意給出兩個(gè)頂點(diǎn)時(shí)，可以在給定的無向圖中找到若干條可能的路徑。然而當(dāng)圖的規(guī)模很大時(shí)，枚舉出所有 P(a,g)，并將所有路徑上每條邊的權(quán)值與給定的權(quán)值約束進(jìn)行判斷則會(huì)花費(fèi)大量的時(shí)間和空間代價(jià)。

當(dāng)約束為≤y，直接取出路徑上邊的最大值與約束條件進(jìn)行比較，若最大值滿足約束，則該路徑其余邊上的權(quán)值必然也滿足。如圖 1，給出查詢 q=(a,g,≤4)，對(duì)于 P(a,g)，取 P1(a,g)=(a,f,b,g)，w(e)max=w(b,g)=7，7≤4不成立，故 P1(a,g)不可達(dá)；P2(a,g)=(a,f,g)，w(e)max=w(f,g)=6，6≤4不成立，故 P2(a,g)不可達(dá)；P3(a,g)=(a,f,d,b,c,g)，w(e)max=w(c,g)=4，4≤4成立，故P3(a,g)上每條邊的權(quán)值均滿足約束。此外，上述例子中，枚舉出的P(a,g)有3條路徑，分別將7、6、4依次與約束條件判斷，如果存儲(chǔ)的路徑越多，比較次數(shù)也會(huì)同步增多。但是，如果優(yōu)先處理 Min{7,6,4}=4，4≤4，即P3就可以直接結(jié)束判斷。因此在構(gòu)建2-hop標(biāo)簽時(shí)，只需要存儲(chǔ)一條權(quán)值較小路徑上的最大值，當(dāng)該權(quán)值滿足約束時(shí)，其他邊上的權(quán)值必然也都滿足。構(gòu)建標(biāo)簽的具體過程如下。

在圖1的無向加權(quán)圖G上，按照每個(gè)頂點(diǎn)的度從大到小確定遍歷順序，即 f→g→b→d→c→h→a→e。首先處理頂點(diǎn) f：Label(f)初始值為(f,0)，從 f出發(fā)依次訪問其余頂點(diǎn)，將頂點(diǎn) f與其他每個(gè)頂點(diǎn)之間較小路徑上權(quán)值的最大值存入相應(yīng)頂點(diǎn)的標(biāo)簽中，如P(f,g)，則取路徑f→d→b→c→g上最大的權(quán)值為4，存儲(chǔ)標(biāo)簽為(f,4)。在處理頂點(diǎn)g時(shí)，當(dāng)訪問到頂點(diǎn)a時(shí)，發(fā)現(xiàn)頂點(diǎn)g無論經(jīng)過哪條路徑到a都必須經(jīng)過f，而f已經(jīng)被處理過，因此無需存入P(a,g)，頂點(diǎn)e同理。當(dāng)處理頂點(diǎn)c時(shí)，c有兩個(gè)相鄰頂點(diǎn)b和g，并且點(diǎn)b和g的訪問順序優(yōu)先于 c，即 c無論訪問哪個(gè)頂點(diǎn)都可以通過 b或者 g得到相應(yīng)的標(biāo)簽，所以 Label(c)也無需存入新的標(biāo)簽。根據(jù)以上思路處理完所有頂點(diǎn)得到2-hop索引，見表1。

表1 基于所有頂點(diǎn)的2-hop索引Tab.1 2-hop index based on all vertices

2.2 索引的構(gòu)建

本文提出一種基于權(quán)值約束的 2-hop索引方法（Degree Index）。該方法的基本思想為：首先在原圖上基于頂點(diǎn)的度得到頂點(diǎn)處理的順序；然后按照順序依次進(jìn)行遍歷，結(jié)合剪枝策略，構(gòu)建2-hop標(biāo)簽索引。具體的代碼設(shè)計(jì)如算法1所示。

算法1 D e g r e e_I n d e x=輸出：所有頂點(diǎn)的L a b e l索引1. N o d e o r d e r←S o r t(d e g r e e, D e s c e n d i n g_o r d e r)2. f o r e a c h v∈N o d e o r d e r d o 3. p u s h v i n t o Q 4. p u s h (v,0) i n t o L a b e l(v)5. w h i l e Q i s n o t e m p t y d o 6. p o p u f r o m Q 7. f o r e a c h u∈E d o 8. Q←(u, m a x(w,w’))9. L a b e l(v)←Q輸入： G (V,E,Σ,w)

10. if P(v,w)≤P(u,w) do 11. continue 12. update Label(v)

算法1用來構(gòu)建所有頂點(diǎn)的2-hop索引。首先按照?qǐng)D上頂點(diǎn)的度降序排列得到處理順序（第1行）；將頂點(diǎn)依次執(zhí)行入隊(duì)順序（第2-3行）；標(biāo)簽的初始值為(v,0)（第4行）；當(dāng)隊(duì)列不為空時(shí)，執(zhí)行出隊(duì)操作（第5-6行）；將路徑上邊的最大權(quán)值存入頂點(diǎn)的標(biāo)簽中（第7-9行）；若已有的標(biāo)簽權(quán)值大于路徑上權(quán)值，則不作更新，否則將新的權(quán)值存入對(duì)應(yīng)的標(biāo)簽中（第10-12行）。

算法1的時(shí)間復(fù)雜度為O(|V|2)，空間復(fù)雜度為 O(|V|×L)（L表示所有頂點(diǎn)的 2-hop標(biāo)簽中的最多個(gè)數(shù)）?？雌饋黼m然空間復(fù)雜度較大，但是該算法結(jié)合剪枝優(yōu)化后的hop點(diǎn)個(gè)數(shù)遠(yuǎn)小于圖的頂點(diǎn)個(gè)數(shù)，因此會(huì)減少一定程度的2-hop標(biāo)簽索引。

當(dāng)約束形式為≥x時(shí)，即每條邊的權(quán)值都≥x，故找出權(quán)值的最小值與約束條件進(jìn)行比較判斷即可；當(dāng)約束形式為[x,y]時(shí)，可以將其看做是兩個(gè)約束條件，即同時(shí)滿足≥x和≤y。而對(duì)于≥x情況可以先反向排除所有

2.3 查詢處理

回答查詢時(shí)，將權(quán)值約束的可達(dá)性查詢轉(zhuǎn)換為頂點(diǎn)之間的標(biāo)簽交集操作，即只需要計(jì)算兩個(gè)頂點(diǎn)u、v的對(duì)應(yīng)標(biāo)簽Label(u)和Label(v)的交集，找到公共頂點(diǎn)，取較大的權(quán)值與約束進(jìn)行比較，滿足條件即返回可達(dá)的結(jié)論，否則返回不可達(dá)。設(shè)計(jì)代碼如下。

算法2 Query輸入：q (u,v,C)=輸出：TRUE or FALSE 1. if u=v then 2. return TRUE 3. while Label(u)≠? and Label(v)≠? do 4. node←Label(u)∩Label(v)

5. w←max{(u, node), (v, node)}6. if w≤C then 7. return TRUE 8. break 9. return FALSE

查詢算法中，首先判斷查詢的兩個(gè)頂點(diǎn)是否是同一個(gè)（第1行），如果相同，就返回TRUE（第2行）；否則對(duì)Label(u)和Label(v)作交集操作（第3行）；求得頂點(diǎn)u、v的公共頂點(diǎn)為node以及u和v分別到node路徑上的最大值w（第4-5行）；如果w≤C滿足，則說明頂點(diǎn)u在權(quán)值約束下可達(dá)頂點(diǎn)v，返回TRUE（第6-8行），否則說明兩點(diǎn)之間不可達(dá)，返回FALSE（第9行）。

例如給定查詢 q=(a,g,≤4)，可以根據(jù)表 1，Label(a)∩Label(g)={(b,4)}，而 4滿足≤4，即滿足權(quán)值約束，說明在約束條件下，頂點(diǎn)a可達(dá)頂點(diǎn)g。

其他兩種約束形式的查詢同理，這里不再贅述。

查詢過程主要通過遍歷兩個(gè)標(biāo)簽的個(gè)數(shù)求解交集，最差情況下，兩個(gè)頂點(diǎn)的標(biāo)簽都遍歷到最后一個(gè)標(biāo)簽元組才能回答查詢，時(shí)間復(fù)雜度為O(m+n)（m、n分別為兩個(gè)被查詢頂點(diǎn)的標(biāo)簽個(gè)數(shù)）；最好情況下為 O(m)或者 O(n)（取 m、n中的較小值）。

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)環(huán)境

由本文中的算法均采用 C++語言實(shí)現(xiàn)，硬件平臺(tái)是Intel Core i5，主頻是2.4GHz的CPU，RAM為8GB；運(yùn)行環(huán)境為Visual Studio Code。實(shí)驗(yàn)通過索引構(gòu)建時(shí)間、索引規(guī)模大小以及查詢時(shí)間作為主要評(píng)價(jià)指標(biāo)來比較算法的性能。

3.2 數(shù)據(jù)集

實(shí)驗(yàn)中所使用的數(shù)據(jù)由10個(gè)的數(shù)據(jù)集組成，這些數(shù)據(jù)集被廣泛地應(yīng)用在可達(dá)性的相關(guān)查詢研究中，它們的具體信息如表2所示。由表2可知，|V|表示無向加權(quán)圖的頂點(diǎn)數(shù)量，|E|為邊的數(shù)量。此外，對(duì)于每個(gè)數(shù)據(jù)集，又分別對(duì)應(yīng)生成100萬個(gè)查詢集進(jìn)行測(cè)試，因此算法的查詢時(shí)間為查詢100萬個(gè)數(shù)據(jù)的總時(shí)間。

表2 數(shù)據(jù)集統(tǒng)計(jì)信息Tab.2 S tatistics of datasets

3.3 索引大小和時(shí)間

表3和表4分別給出了現(xiàn)有算法Edge_Index和本文提出的索引構(gòu)建方法（Degree Index）在所有數(shù)據(jù)集上的索引規(guī)模大小和構(gòu)建索引時(shí)間。

表3 索引大小（MB）Tab.3 Inde x size (MB)

如表3所示，Degree Index方法構(gòu)建的索引大小明顯要小于 Edge_Index方法，在數(shù)據(jù)集uniprot100m上，前者的索引大小比后者小7.2倍。因?yàn)镈egree Index方法需要存儲(chǔ)的標(biāo)簽個(gè)數(shù)經(jīng)剪枝后明顯減少，而Edge_Index方法在構(gòu)建索引時(shí)需要存儲(chǔ)索引樹上所有的結(jié)點(diǎn)，要花費(fèi)|V|2的空間代價(jià)，而且對(duì)于存儲(chǔ)的所有頂點(diǎn)都沒有任何剪枝優(yōu)化效果，所以當(dāng)數(shù)據(jù)集的頂點(diǎn)不斷擴(kuò)大，其占用的內(nèi)存空間也越大，甚至在最后三個(gè)數(shù)據(jù)集上已經(jīng)超出有限的內(nèi)存。

由表4可知，Edge_Index方法構(gòu)建索引的時(shí)間要快于 Degree Index，因?yàn)榍罢邔?duì)索引樹只做一次遍歷得到最終的序列，而后者需要基于頂點(diǎn)多次訪問其余頂點(diǎn)。

表4 索引構(gòu)建時(shí)間（ms）Tab.4 Index time (ms)

3.4 查詢時(shí)間

本節(jié)將通過 100萬個(gè)隨機(jī)查詢上的查詢響應(yīng)時(shí)間對(duì)比本文提出的Degree Index方法與Edge_Index方法，具體實(shí)驗(yàn)結(jié)果見表5。

表5 查詢時(shí)間（ms）Tab.5 Query time (ms)

實(shí)結(jié)果表明，Edge_Index方法回答查詢的效率較快。因?yàn)镈egree Index方法查詢時(shí)需要求解兩個(gè)頂點(diǎn)標(biāo)簽的交集，在最差情況下需要遍歷到最后一個(gè)標(biāo)簽才能給出回答，會(huì)消耗一定的時(shí)間代價(jià)，但是總體查詢時(shí)間相差不大。

4 總結(jié)

針對(duì)現(xiàn)有方法解決權(quán)值約束可達(dá)性查詢存在索引規(guī)模大、擴(kuò)展性差的問題，本文基于加權(quán)圖提出一種優(yōu)化的 2-hop索引算法。該算法按照頂點(diǎn)的度來確定頂點(diǎn)的處理順序，然后基于該順序來構(gòu)建 2-hop索引；查詢處理時(shí)，將加權(quán)圖上的權(quán)值約束可達(dá)查詢轉(zhuǎn)換為基于頂點(diǎn)標(biāo)簽的集合交集操作。實(shí)驗(yàn)結(jié)果表明，本文提出的方法能有效地降低索引規(guī)模，并且在有限內(nèi)存的環(huán)境下高效處理大規(guī)模數(shù)據(jù)圖。