基于有向無環(huán)圖的區(qū)間覆蓋率求解算法

杜明　龐建成　周軍鋒

摘 要：給定一個有向無環(huán)圖，回答可達性查詢是圖的基本操作之一。雖然很多方法使用樹區(qū)間來加速可達查詢的處理速度，但并不明確使用多少個區(qū)間比較合適。本文提出一種快速計算區(qū)間覆蓋率的算法，該方法通過使用有效的剪枝策略來支持高效的覆蓋率計算?；谒玫降膮^(qū)間覆蓋率，可針對不同數(shù)據(jù)圖確定合適的區(qū)間個數(shù)，以便在加速查詢處理的同時，降低索引規(guī)模?；诙鄠€真實數(shù)據(jù)集的實驗驗證了本文提出方法的高效性。

關鍵詞：有向無環(huán)圖;可達性查詢處理;區(qū)間覆蓋率

【Abstract】Givenadirectedacyclicgraph，answeringthereachabilityqueryisoneofthebasicoperationsofthegraph.Althoughmanymethodsusetreeintervalstospeeduptheprocessingspeedofreachablequeries，itisnotclearhowmanyintervalsareappropriate.Thispaperproposesanalgorithmtoquicklycalculatethecoverageofmultipleintervals.Thismethodsupportsefficientcoveragecalculationbyusinganeffectivepruningstrategy.Basedontheobtainedintervalcoverage，anappropriatenumberofintervalscanbedeterminedfordifferentdatagraphs，soastoreducetheindexscalewhilespeedingupqueryprocessing.Experimentsbasedonmultiplerealdatasetsverifytheefficiencyofthemethodproposedinthispaper.

【Keywords】directedacyclicgraph;reachabilityqueriesprocessing;intervalcoverage

作者簡介： 杜 明（1975-），男，博士，副教授，主要研究方向：自然語言處理、信息查詢、數(shù)據(jù)分析;龐建成（1995-），男，碩士研究生，主要研究方向：圖的可達查詢覆蓋率研究;周軍鋒（1977-），男，博士，教授，博士生導師，主要研究方向：大圖數(shù)據(jù)的查詢處理技術、推薦系統(tǒng)關鍵技術。

0 引 言

給定有向無環(huán)圖（DirectedAcyclicGraph，DAG），以及圖中任意兩個頂點u、v，可達性查詢u？→v用于回答從頂點u出發(fā)是否存在一條路徑可以到達頂點v。可達性查詢處理是圖數(shù)據(jù)管理與分析的基本操作之一，一直以來都是研究者廣泛關注的熱點問題[1-10]。在實際應用中，可達性查詢被廣泛應用到社交網絡、通信與傳感器網絡、生物網絡、可擴展標記語言數(shù)據(jù)、資源描述框架數(shù)據(jù)等領域，用于檢測兩點間是否存在特定關系。

雖然使用多個區(qū)間可以回答更多的可達性查詢，但是現(xiàn)在的方法并不明確使用多少個區(qū)間比較合適。一方面，使用多個區(qū)間可以擴大覆蓋率，從而增強區(qū)間標簽的剪枝能力;另一方面，使用多個區(qū)間也意味著較大的索引和較長的查詢響應時間。因此使用區(qū)間標簽來加速可達查詢處理時，一個關鍵問題是：應該建立多少個區(qū)間標簽，從而在查詢時間、索引大小以及索引構建時間之間獲得平衡。顯然，該問題的解決依賴于高效獲知區(qū)間標簽的覆蓋率，如此即可根據(jù)系統(tǒng)的硬件環(huán)境限制，選擇合適的區(qū)間個數(shù)，進而加速查詢響應的效率。

然而，覆蓋率的計算并非易事，原因在于不同生成樹區(qū)間所覆蓋的后代頂點有重復，多個區(qū)間覆蓋率并非簡單的累加和，需要在計算過程中去除重復部分。針對該問題，本文首次提出一種快速計算區(qū)間覆蓋率的算法，稱k-DFSIC（k-DepthFirstSearchIntervalCoverage），其中k表示生成樹區(qū)間的個數(shù)。該方法在求解覆蓋率時通過使用有效的剪枝策略來支持高效的覆蓋率計算，基于所得到的區(qū)間覆蓋率，用戶可針對不同數(shù)據(jù)圖確定合適的區(qū)間個數(shù)來獲得最佳的性能體驗。

本文的其余部分安排如下。第1節(jié)介紹相關工作，第2節(jié)提出求區(qū)間覆蓋率的算法，第3節(jié)展示實驗結果，第4節(jié)總結全文。

1 相關工作

1.1 問題定義

雖然可達性查詢針對的是一般有向圖，但是現(xiàn)有方法可以通過壓縮其中的強連通分量將其轉換為有向無環(huán)圖來處理，因此，本文假設輸入的都是有向無環(huán)圖。以下介紹區(qū)間覆蓋率的定義及問題的定義。

定義1 區(qū)間覆蓋率 給定有向無環(huán)圖及其生成樹上的多個區(qū)間，區(qū)間覆蓋率表示僅通過頂點的區(qū)間能回答的可達對個數(shù)占有向無環(huán)圖中所有可達對個數(shù)的比例。

例如圖1（a）中有向無環(huán)圖G的所有可達對的數(shù)目為28，圖1（b）中所用一個生成樹區(qū)間能夠回答的可達對個數(shù)是22個，則使用一個區(qū)間時，其區(qū)間覆蓋率為22/28，圖1（c）中使用2個生成樹區(qū)間能夠回答的可達對個數(shù)是26個，則其區(qū)間覆蓋率為26/28。

問題定義： 給定有向無環(huán)圖及其對應的多個生成樹區(qū)間，返回這些生成樹的區(qū)間覆蓋率。

1.2 相關算法

雖然區(qū)間覆蓋率可用于協(xié)助用戶針對不同圖來確定合適的區(qū)間個數(shù)，但關于區(qū)間覆蓋率的計算問題還未見到任何研究，本文首次對區(qū)間覆蓋率的問題進行研究，提出一種快速計算區(qū)間覆蓋率的算法。這里，研究中僅討論使用區(qū)間的可達性查詢處理算法，包括GRAIL[11]、FERRARI[5]、FELINE[12]三個算法。對此可做闡釋分述如下。

GRAIL算法基于生成樹為每個點附加多個區(qū)間，其中一半區(qū)間是包含所有圖中后代的區(qū)間，用于判斷不可達，另外一半區(qū)間是包含生成樹中后代的區(qū)間，用于判斷可達。由于區(qū)間個數(shù)會影響索引大小及查詢效率，本次研究在進行實驗時，基于數(shù)據(jù)圖的稀疏程度來設定區(qū)間個數(shù)。對于稀疏圖（度小于2），使用2個區(qū)間，其它圖使用5個區(qū)間。該方法是一種基于經驗的直覺，區(qū)間增多時，不一定能增強查詢處理能力。

FELINE用x和y表示頂點的2個拓撲號，用I表示頂點的區(qū)間標記。在判斷頂點u是否可達頂點v的時候，如果頂點的拓撲號滿足xu>xv或者yu>yv，則可知頂點u不可達頂點v;如果xu

FERRARI根據(jù)內存的限制情況來確定區(qū)間個數(shù)，由于區(qū)間之間有重疊，因此即使內存夠大，可支持多個區(qū)間，但卻仍然難以保證查詢效率。

以上方法雖然都使用區(qū)間來加快可達性查詢的處理效率，但是這些方法都不能確定應該使用多少區(qū)間來回答才合適，針對該問題，本文提出一種快速計算區(qū)間覆蓋率的方法，以便針對不同數(shù)據(jù)圖確定合適的區(qū)間個數(shù)，從而提升查詢效率并減小索引規(guī)模。

2 求區(qū)間覆蓋率的算法

2.1 基礎算法

給定有向無環(huán)圖G及其生成樹上的k個區(qū)間，求區(qū)間覆蓋率的基本思想是：首先找到圖G中所有的可達對;然后判斷這些可達對是否能通過區(qū)間回答，能回答說明該可達對能夠通過區(qū)間判斷，不能回答則說明該可達對不能通過區(qū)間判斷;最后求出可以通過區(qū)間回答的可達對個數(shù)占圖G中所有可達對個數(shù)的比例，即可得到使用k個生成樹區(qū)間的覆蓋率。

算法1展示了基礎算法求區(qū)間覆蓋率的偽代碼，具體如下。

算法中，第1行設置2個變量nRch和nUnRch，分別表示可以通過生成樹區(qū)間回答的可達對個數(shù)和不能通過生成樹區(qū)間回答的可達對個數(shù)，并將其初始值設為0;第2～7行針對圖G中所有的可達對，依次判斷其是否能通過給定的k個區(qū)間回答，如果可以回答，nRch++，如果不能回答，則nUnRch++;第8行通過nRch的值除以（nRch+nUnRch）的值求出使用k個生成樹區(qū)間的覆蓋率。

給定有向無環(huán)圖G見圖1（a）。首先找到圖G中所有的可達對，詳見表1，總共有28個;然后判斷這些可達對能否通過給定的區(qū)間回答。研究可知，圖1（b）為圖G中每個節(jié)點給定了一個生成樹區(qū)間，[8，9]（v7的區(qū)間）[7，9]（v4的區(qū)間），說明v4→v7可以通過該區(qū)間回答，則通過一個區(qū)間能回答的可達對個數(shù)nRch++，而[4，5]（v6的區(qū)間）[7，9]（v4的區(qū)間），說明v4→v6不能通過該區(qū)間回答，則不能通過一個區(qū)間回答的可達對個數(shù)nUnRch++，當圖G中所有可達對判斷結束后，可以得到nRch為22，nUnRch為6，故通過計算可得使用一個區(qū)間的覆蓋率是22/（22+6），即22/28。研究中的圖1（c）又為G中每個節(jié)點給定了2個生成樹區(qū)間，[5，5]（v6的第二個區(qū)間）[3，7]（v4的第二個區(qū)間），說明v4→v6可以通過該區(qū)間回答，則通過2個區(qū)間能回答的可達對個數(shù)nRch++，而[6，7]（v7的第二個區(qū)間）[8，8]（v5的第二個區(qū)間），說明v5→v7不能通過該區(qū)間回答，則通過2個區(qū)間不能回答的可達對個數(shù)nUnRch++;當圖G中所有可達對判斷結束之后，可得nRch為26，nUnRch為2，則通過計算可得使用2個區(qū)間的覆蓋率是26/（26+2），即26/28。

基礎算法若要枚舉有向無環(huán)圖G中所有的可達對，需要的時間為O（kn（n+m）），其中n為G的頂點個數(shù)，m為G的邊數(shù)。判斷每個可達對能否通過生成樹區(qū)間回答，可以在O（k）時間內完成，故基礎算法的時間復雜度是O（kn（n+m））。

2.2 k-DFSIC算法

由于基礎算法在計算過程中需要枚舉有向無環(huán)圖中所有的可達對，時間復雜度太大，在實踐中無法處理大圖。針對該問題，本文提出一種快速計算區(qū)間覆蓋率的k-DFSIC算法。給定有向無環(huán)圖G及其k個生成樹區(qū)間，求區(qū)間覆蓋率之前，為圖中每個節(jié)點設定一個計數(shù)器，表示該節(jié)點通過區(qū)間能回答的可達對個數(shù)，初始值為第一個區(qū)間的長度。求區(qū)間覆蓋率的基本思想是：當求解頂點u的第i個區(qū)間新增的可達查詢數(shù)量時，對于第i個區(qū)間中的所有生成樹后代點，即檢視u與其之間的可達性是否可以通過前i-1個區(qū)間來判斷。如果可以，則u的計數(shù)器不變，否則說明該可達對無法通過前i-1個區(qū)間判斷，則u的計數(shù)器加1。當所有頂點處理結束后，將頂點的計數(shù)器累加，即可得到所有節(jié)點通過區(qū)間能回答的可達對個數(shù)。該值除以圖G中所有可達對個數(shù)，就是使用k個區(qū)間的覆蓋率。

算法2展示了k-DFSIC算法求區(qū)間覆蓋率的偽代碼，具體如下。

算法中，第1行設置了一個變量nTC表示有向無環(huán)圖G的傳遞閉包的大小;第2行設置了一個變量nRCH表示圖G中所有節(jié)點通過區(qū)間能回答的可達對個數(shù)，并設其初始值為0;第3行為圖G中每個節(jié)點u給定一個計數(shù)器表示該節(jié)點通過區(qū)間能回答的可達對個數(shù)nRch，其初始值為節(jié)點u的第一個區(qū)間長度;第4～12行在求解節(jié)點u通過i（2≤i≤k）個區(qū)間新增的可達查詢數(shù)量時，對于第i個區(qū)間中的所有生成樹上后代節(jié)點v，設置一個變量flag表示u和v之間的可達性是否可以通過前i-1個區(qū)間來判斷，其初始值設為TRUE，如果u和v之間的可達性可以通過前i-1個區(qū)間來判斷，則flag值為FALSE，判斷后如果flag值為TRUE，說明該可達對無法通過前i-1個區(qū)間判斷，則nRch加1;第13～14行將圖G中每個節(jié)點的計數(shù)器nRch加和即所有節(jié)點通過區(qū)間能回答的可達對個數(shù)nRCH，用nRCH的值除以圖G中所有可達對的個數(shù)nTC，即可得到使用k個區(qū)間的覆蓋率。

例如，圖1（a）所示有向無環(huán)圖G中所有可達對共有28個，參見表1，即圖G的傳遞閉包的大小nTC為28。

由圖1（b）可知，為圖G中每個節(jié)點給定了一個區(qū)間，并為每個節(jié)點給定一個計數(shù)器表示該節(jié)點通過一個區(qū)間能回答的可達對個數(shù)nRch為該節(jié)點的區(qū)間長度，比如說v4的區(qū)間是[7，9]，則v4通過一個區(qū)間能回答的可達對個數(shù)nRch為v4的區(qū)間長度2，將每個節(jié)點的nRch值加和可以得到所有節(jié)點通過一個區(qū)間能回答的可達對個數(shù)nRCH為22，則使用一個區(qū)間的覆蓋率是22/28。

由圖1（c）可知，為圖G中每個節(jié)點給定了2個區(qū)間，并為每個節(jié)點給定一個計數(shù)器表示該節(jié)點通過2個區(qū)間能回答的可達對個數(shù)nRch首先設置為該節(jié)點的第一個區(qū)間的長度，對于生成樹上每個節(jié)點來說，要找到該節(jié)點到其后代節(jié)點的所有可達查詢，參見表2，并檢查這些查詢能否通過前i-1個區(qū)間回答來更新nRch的值，比如v4節(jié)點，v4的第一個區(qū)間是[7，9]，則v4通過2個區(qū)間能回答的可達對個數(shù)nRch首先設置為v4的第一個區(qū)間的長度2，然后依次檢查v4→v6，v4→v7，v4→v8，v4→v9能否通過前i-1個區(qū)間回答來更新nRch的值，可以發(fā)現(xiàn)v4→v6不可以通過第一個區(qū)間回答，但是可以通過第二個區(qū)間回答，則nRch++，同理v4→v8也不可以通過第一個區(qū)間回答，但是可以通過第二個區(qū)間回答，則nRch++，而v4→v7，v4→v9已經可以通過第一個區(qū)間回答了，則nRch值不變，當所有查詢判斷結束之后，可以得到v4通過2個區(qū)間能回答的可達對個數(shù)nRch為4;將每個節(jié)點的nRch值加和可以得到所有節(jié)點通過2個區(qū)間能回答的可達對個數(shù)nRCH為26，則使用2個區(qū)間的覆蓋率是26/28。

k-DFSIC算法需要在有向無環(huán)圖G上找到其生成樹上的每個節(jié)點的后代節(jié)點。和基礎算法不同，基礎算法需要枚舉圖上的后代，而k-DFSIC只需要枚舉樹上的后代，該值等于樹上每個頂點的高度之和。假設頂點的平均高度是h，則求解可達對個數(shù)nRCH的代價是O（k（n+m）+khn），其中n為G的頂點個數(shù)，m為G的邊數(shù);同時，求傳遞閉包的時間代價為O（wm）[13]，這里w是求傳遞閉包大小過程中，處理每個點時平均處理代價。因此，k-DFSIC的時間復雜度是O（k（n+m）+khn+wm）。

3 實驗分析

3.1 實驗環(huán)境

實驗所用的硬件平臺是IntelCorei5-4460主頻為3.20GHz的CPU，4GB的RAM內存，操作系統(tǒng)為Ubuntu8.3.0，并使用gcc8.3.0進行編譯，以上算法均采用C++語言實現(xiàn)。

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

本文中使用的12個數(shù)據(jù)集見表3。這些數(shù)據(jù)集都廣泛地出現(xiàn)在圖的可達查詢研究中[4-5，9，14-16]，這些數(shù)據(jù)集都是有向無環(huán)圖，表3中標注了每個數(shù)據(jù)集的頂點數(shù)|V|以及邊數(shù)|E|。

3.3 索引大小

k-DFSIC算法求區(qū)間覆蓋率使用不同區(qū)間時的索引大小見表4。由表4可以看出隨著區(qū)間個數(shù)的增加，索引大小呈線性增加。

3.4 覆蓋率求解時間

表5比較了基礎算法和k-DFSIC算法求區(qū)間覆蓋率所需的時間。由表5可以發(fā)現(xiàn)k-DFSIC算法與基礎算法相比，在使用相同區(qū)間個數(shù)的情況下，所需的時間要少得多，并且基礎算法在大圖當中運行時間太長，而k-DFSIC算法則只需很少的時間，表5中，“-”表示基礎算法運行時間超過了2h。

3.5 區(qū)間覆蓋率

表6展示了本文實驗所得到的區(qū)間覆蓋率。由表6發(fā)現(xiàn)隨著區(qū)間個數(shù)的不斷增加，覆蓋率雖然也不斷增加，但是有的數(shù)據(jù)集覆蓋率增加值比較小，比如twitter數(shù)據(jù)集;而有的數(shù)據(jù)集覆蓋率增加值比較大，比如xmark數(shù)據(jù)集，使用5個區(qū)間時的覆蓋率是使用1個區(qū)間時覆蓋率的3倍多。

3.6 實驗結論

首先，本文提出的區(qū)間覆蓋率計算算法可高效求解區(qū)間覆蓋率，在實際中需要了解區(qū)間覆蓋率的情況下，可通過使用本文提出的算法進行高效求解;其次，通過本文實驗所得到的區(qū)間覆蓋率，可以發(fā)現(xiàn)有些數(shù)據(jù)集只需要使用2個區(qū)間來回答可達性查詢就比較合適了，比如human數(shù)據(jù)集，而有的數(shù)據(jù)集使用5個區(qū)間比較合適，比如xmark數(shù)據(jù)集。假設內存足夠的情況下，考慮到查詢效率，針對不同數(shù)據(jù)集回答可達性查詢合適的區(qū)間個數(shù)見表7;如果內存不足以使用多個區(qū)間，則需要用戶根據(jù)實際情況確定合適的區(qū)間個數(shù)。

4 結束語

本文針對已有算法回答可達性查詢時使用樹區(qū)間來加快處理速度、但是并不明確使用多少個區(qū)間比較合適的問題，首次提出了一種快速計算區(qū)間覆蓋率的算法。實驗結果表明，本文提出的算法可高效計算區(qū)間覆蓋率?；谒玫降膮^(qū)間覆蓋率，用戶可結合實際應用環(huán)境的限制確定可達查詢處理過程中應該使用的區(qū)間數(shù)量，從而獲得最佳的性能體驗。

參考文獻

[1] AGRAWALR，BORGIDAA，JAGADISHHV，etal.Efficientmanagementoftransitiverelationshipsinlargedataandknowledgebases[J].ACMSIGMODRecord，1989，18（2）：253-262.

[2]CHENGJ，HUANGS，WUH，etal.TF-Label：Atopological-foldinglabelingschemeforreachabilityqueryinginalargegraph[C]//Proceedingsofthe2013ACMSIGMODInternationalConferenceonManagementofData.NewYork，USA：ACM，2013：193-204.

[3] JINR，WANGG.Simple，fast，andscalablereachabilityOracle[J].VeryLargeDataBases，2014，6（14）：1978-1989.

[4]JINRuoming，XIANGYang，RUANNing，etal.Efficientlyansweringreachabilityqueriesonverylargedirectedgraphs[C]//Proceedingsofthe2013ACMSIGMODInternationalConferenceonManagementofData.Vancouver，BC，Canada：ACM，2008：595-608.

[5]YILDIRIMH，CHAOJIV，ZAKIMJ.GRAIL：Ascalableindexforreachabilityqueriesinverylargegraphs[J].TheVLDBJournal，2012，21（4）：509-534.

[6]ZHANGTianming，GAOYunjun，LICongzheng，etal.Distributedreachabilityqueriesonmassivegraphs[M]//LIG，YANGJ，GAMAJ，etal.DatabaseSystemsforAdvancedApplications.DASFAA2019.LectureNotesinComputerScience.Cham：Springer，2019，11448：406-410.

[7]SENGUPTAN，BAGCHIA，RAMANATHM，etal.ARROW：ApproximatingreachabilityusingrandomwalksoverWeb-scalegraphs[C]//InternationalConferenceonDataEngineering.Macao，China：dblp，2019：470-481.

[8]BENDERMA，F(xiàn)INEMANJT，GILBERTS，etal.Anewapproachtoincrementaltopologicalordering[C]//SymposiumonDiscreteAlgorithms.Austin，Texas：dblp，2009：1108-1115.

[9]JAGADISHHV.Acompressiontechniquetomaterializetransitiveclosure[J].ACMTransactionsonDatabaseSystems，1990，15（4）：558-598.

[10] CHENY，CHENY.AnEfficientalgorithmforansweringgraphreachabilityqueries[C]//IEEE24thInternationalConferenceonDataEngineering.Paris，F(xiàn)rance：IEEE，2008：893-902.

[11] YILDIRIMH，CHAOJIV，ZAKIMJ.Grail：Scalablereachabilityindexforlargegraphs[J].ProceedingsoftheVLDBEndowment，2010，3（12）：276-284.

[12] VELOSORR，CERFL，JrMEIRAW，etal.Reachabilityqueriesinverylargegraphs：Afastrefinedonlinesearchapproach[C]//17thInternationalConferenceonExtendingDatabaseTechnology.Athens，Greece：dblp，2014：511-522.

[13] TANGXian，CHENZiyang，LIKai，etal.Efficientcomputationofthetransitiveclosuresize[J].Clust.Comput.，2019，22（Supplement）：6517-6527.

[14] JINR，RUANR，DEYS，etal.SCARAB：Scalingreachabilitycomputationonlargegraphs[C]//Proceedingsofthe2012ACMSIGMODInternationalConferenceonManagementofData.Scottsdale：ACM，2012：169-180.

[15] CHAM，HADDADIH，BENEVENUTOF，etal.MeasuringuserinfluenceinTwitter：Themillionfollowerfallacy[C]//ProceedingsoftheFourthInternationalConferenceonWeblogsandSocialMedia（ICWSM2010）.Washington，DC，USA：dblp，2010：10-17.

[16] VanSCHAIKSJ，DeMOORO.Amemoryefficientreachabilitydatastructurethroughbitvectorcompression[C]//Proceedingsofthe2011ACMSIGMODInternationalConferenceonManagementofData.Athens，Greece：ACM，2011：913-924.