成夢佳,杜 明,周軍鋒
(東華大學(xué),上海 松江 200000)
互聯(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)速度。
本文基于無向加權(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.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ù)圖。
需要注意的是,實際應(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
本文提出一種基于權(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情況可以先反向排除所有 回答查詢時,將權(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中的較小值)。 由本文中的算法均采用 C++語言實現(xiàn),硬件平臺是Intel Core i5,主頻是2.4GHz的CPU,RAM為8GB;運行環(huán)境為Visual Studio Code。實驗通過索引構(gòu)建時間、索引規(guī)模大小以及查詢時間作為主要評價指標來比較算法的性能。 實驗中所使用的數(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和表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) 本節(jié)將通過 100萬個隨機查詢上的查詢響應(yīng)時間對比本文提出的Degree Index方法與Edge_Index方法,具體實驗結(jié)果見表5。 表5 查詢時間(ms)Tab.5 Query time (ms) 實結(jié)果表明,Edge_Index方法回答查詢的效率較快。因為Degree Index方法查詢時需要求解兩個頂點標簽的交集,在最差情況下需要遍歷到最后一個標簽才能給出回答,會消耗一定的時間代價,但是總體查詢時間相差不大。 針對現(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ù)圖。2.3 查詢處理
3 實驗與分析
3.1 實驗環(huán)境
3.2 數(shù)據(jù)集
3.3 索引大小和時間
3.4 查詢時間
4 總結(jié)