杜明　龐建成　周軍鋒

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

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

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

【Keywords】directedacyclicgraph;reachabilityqueriesprocessing;intervalcoverage

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

0 引 言

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

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

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

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

1 相關(guān)工作

1.1 問題定義

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

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

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

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

1.2 相關(guān)算法

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

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

FELINE用x和y表示頂點(diǎn)的2個(gè)拓?fù)涮?，用I表示頂點(diǎn)的區(qū)間標(biāo)記。在判斷頂點(diǎn)u是否可達(dá)頂點(diǎn)v的時(shí)候，如果頂點(diǎn)的拓?fù)涮枬M足xu>xv或者yu>yv，則可知頂點(diǎn)u不可達(dá)頂點(diǎn)v;如果xu

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

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

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

2.1 基礎(chǔ)算法

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

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

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

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

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

2.2 k-DFSIC算法

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

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

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

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

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

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

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

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

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

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

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

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

3.3 索引大小

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

3.4 覆蓋率求解時(shí)間

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

3.5 區(qū)間覆蓋率

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

3.6 實(shí)驗(yàn)結(jié)論

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

4 結(jié)束語

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

參考文獻(xiàn)

[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.