一種高效的權(quán)值約束可達性查詢處理算法

成夢佳，杜 明，周軍鋒

(東華大學(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)用在各個領(lǐng)域中，如通信網(wǎng)絡(luò)、生物信息網(wǎng)絡(luò)、道路網(wǎng)絡(luò)等[3-5]。

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

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

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

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

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

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

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

1.2 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

如圖1所示，當回答查詢 q=(a,g,≤4)時，可得出 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滿足，即頂點a、g存在滿足約束條件的路徑，說明在權(quán)值約束下點 a可以到達點 g；若每一條路徑都不滿足條件，則說明a不可達g。

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

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

當約束為≤y，直接取出路徑上邊的最大值與約束條件進行比較，若最大值滿足約束，則該路徑其余邊上的權(quán)值必然也滿足。如圖 1，給出查詢 q=(a,g,≤4)，對于 P(a,g)，取 P1(a,g)=(a,f,b,g)，w(e)max=w(b,g)=7，7≤4不成立，故 P1(a,g)不可達；P2(a,g)=(a,f,g)，w(e)max=w(f,g)=6，6≤4不成立，故 P2(a,g)不可達；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依次與約束條件判斷，如果存儲的路徑越多，比較次數(shù)也會同步增多。但是，如果優(yōu)先處理 Min{7,6,4}=4，4≤4，即P3就可以直接結(jié)束判斷。因此在構(gòu)建2-hop標簽時，只需要存儲一條權(quán)值較小路徑上的最大值，當該權(quán)值滿足約束時，其他邊上的權(quán)值必然也都滿足。構(gòu)建標簽的具體過程如下。

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

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

2.2 索引的構(gòu)建

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

算法1 D e g r e e_I n d e x=輸出：所有頂點的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)建所有頂點的2-hop索引。首先按照圖上頂點的度降序排列得到處理順序（第1行）；將頂點依次執(zhí)行入隊順序（第2-3行）；標簽的初始值為(v,0)（第4行）；當隊列不為空時，執(zhí)行出隊操作（第5-6行）；將路徑上邊的最大權(quán)值存入頂點的標簽中（第7-9行）；若已有的標簽權(quán)值大于路徑上權(quán)值，則不作更新，否則將新的權(quán)值存入對應(yīng)的標簽中（第10-12行）。

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

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

2.3 查詢處理

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

算法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

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

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

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

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

3 實驗與分析

3.1 實驗環(huán)境

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

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

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

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

3.3 索引大小和時間

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

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

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

由表4可知，Edge_Index方法構(gòu)建索引的時間要快于 Degree Index，因為前者對索引樹只做一次遍歷得到最終的序列，而后者需要基于頂點多次訪問其余頂點。

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

3.4 查詢時間

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

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

實結(jié)果表明，Edge_Index方法回答查詢的效率較快。因為Degree Index方法查詢時需要求解兩個頂點標簽的交集，在最差情況下需要遍歷到最后一個標簽才能給出回答，會消耗一定的時間代價，但是總體查詢時間相差不大。

4 總結(jié)

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