低冗余計(jì)算的可達(dá)性查詢保持圖壓縮策略

趙丹楓，林俊辰，宋 巍，王 建，黃冬梅

（1.上海海洋大學(xué)信息學(xué)院，上海201306；2.上海電力大學(xué)，上海200090）

0 引言

近年來，隨著計(jì)算機(jī)技術(shù)和網(wǎng)絡(luò)技術(shù)的發(fā)展，現(xiàn)實(shí)生活中很多領(lǐng)域產(chǎn)生了越來越多的網(wǎng)絡(luò)數(shù)據(jù)，如語義網(wǎng)［1］、萬維網(wǎng)［2］、道路網(wǎng)［3］、推薦網(wǎng)［4］、社交網(wǎng)［5］以及生物信息網(wǎng)［6］等，并且這些網(wǎng)絡(luò)中的數(shù)據(jù)結(jié)構(gòu)趨于復(fù)雜，難以用關(guān)系數(shù)據(jù)模型描述。圖作為一種能夠有效描述事物之間復(fù)雜關(guān)系的數(shù)據(jù)結(jié)構(gòu)，在上述領(lǐng)域得到了廣泛的研究和應(yīng)用。

可達(dá)性查詢是圖問題研究中一種基本的查詢方法，很多復(fù)雜的圖查詢問題通常建立在可達(dá)性查詢的基礎(chǔ)上，可達(dá)性查詢一直是數(shù)據(jù)庫領(lǐng)域研究的熱點(diǎn)，與其相關(guān)的研究已經(jīng)進(jìn)行了二十多年［7-11］。隨著大數(shù)據(jù)時(shí)代［12-13］的到來，圖數(shù)據(jù)的規(guī)模不斷擴(kuò)大，對(duì)可達(dá)性查詢的求解提出了新的挑戰(zhàn)。以微信數(shù)據(jù)［14］為例，據(jù)騰訊官方統(tǒng)計(jì)，截至2018 年9 月，全球微信用戶已超過10 億8 千萬，用戶平均好友數(shù)超過130 個(gè)。若采用鄰接表來存儲(chǔ)由微信用戶形成的社交網(wǎng)絡(luò)，需要超過1 TB 的存儲(chǔ)空間，在研究中難以滿足這樣的內(nèi)存需求，因而不能將鄰接表全部載入內(nèi)存后對(duì)可達(dá)性查詢求解。

針對(duì)圖數(shù)據(jù)規(guī)模增大引發(fā)的查詢難問題，主要有以下三種解決方法［15］：1）使用硬盤存儲(chǔ)圖數(shù)據(jù)，每次載入部分圖數(shù)據(jù)到內(nèi)存中，分步查詢，最后整合結(jié)果；2）使用分布式系統(tǒng)存儲(chǔ)圖數(shù)據(jù)，每個(gè)節(jié)點(diǎn)進(jìn)行部分查詢，最后整合結(jié)果；3）將圖數(shù)據(jù)進(jìn)行壓縮表示，全部載入內(nèi)存中，直接查詢得到結(jié)果。

以上三種解決方法各有優(yōu)劣。第一種方法適用于訪問局部性較好的圖數(shù)據(jù)，若圖數(shù)據(jù)訪問局部性較差，則在查詢時(shí)I/O 次數(shù)會(huì)顯著增多，從而導(dǎo)致查詢代價(jià)增大；第二種方法適用于耦合性較低的圖數(shù)據(jù)，若圖數(shù)據(jù)耦合性較高，則會(huì)造成數(shù)據(jù)難以分割，且分割后各子圖相關(guān)性較大及通信次數(shù)顯著增多等問題，從而導(dǎo)致查詢代價(jià)增大；第三種方法并不能解決所有的問題，對(duì)于某些規(guī)模特別大的圖數(shù)據(jù)來說，壓縮后依然不能全部載入內(nèi)存中進(jìn)行計(jì)算，但是，它可以和前兩種方法有機(jī)結(jié)合，進(jìn)一步改善前兩種方法的性能。針對(duì)第一種方法，若在保持訪問局部性的前提下先對(duì)圖數(shù)據(jù)進(jìn)行壓縮，可以減少I/O次數(shù)，從而提高訪問速度；針對(duì)第二種方法，若先對(duì)圖數(shù)據(jù)進(jìn)行壓縮，則分布式系統(tǒng)可以利用更少的節(jié)點(diǎn)完成相同的任務(wù)，并且可以減少節(jié)點(diǎn)間的通信次數(shù)。因此，可達(dá)性查詢保持圖壓縮是解決大規(guī)模圖數(shù)據(jù)上可達(dá)性查詢難問題的有效途徑。

但現(xiàn)有的可達(dá)性查詢保持圖壓縮方法存在冗余計(jì)算，因而計(jì)算效率較低，隨著數(shù)據(jù)量的增大，時(shí)間消耗變得難以接受，所以有必要研究新的壓縮策略，提高壓縮速度。

本文的主要工作如下：

1）針對(duì)求解祖先后代集過程設(shè)計(jì)了一種基于拓?fù)渑判虻淖嫦群蟠蠼馑惴ǎ═opological Sorting Based algorithm for solving ancestor and descendant sets，TSB），能有效地減少冗余計(jì)算，加快求解速度；還設(shè)計(jì)了一種基于圖聚合運(yùn)算的祖先后代集求解算法（AGGregation Based algorithm for solving ancestor and descendant sets，AGGB），對(duì)最長(zhǎng)路徑長(zhǎng)度較小的圖數(shù)據(jù)有較好效果。

2）針對(duì)求解可達(dá)性等價(jià)類過程設(shè)計(jì)了一種分段統(tǒng)計(jì)剪枝（Piecewise Statistical Pruning，PSP）算法，實(shí)現(xiàn)了可達(dá)性等價(jià)類求解過程的剪枝，減少了冗余匹配，加快了求解速度。

3）應(yīng)用不同數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，結(jié)果表明，本文提出的可達(dá)性查詢保持圖壓縮策略是高效、快速的。

1 相關(guān)工作

對(duì)圖數(shù)據(jù)進(jìn)行高效、緊湊的表示與壓縮是當(dāng)前圖研究的熱點(diǎn)之一，同時(shí)也為圖上的其他基本算法和操作提供了強(qiáng)有力的支持，包括存儲(chǔ)空間優(yōu)化、查詢優(yōu)化及可視化分析等。

1.1 圖壓縮技術(shù)的分類

文獻(xiàn)［15］中將圖壓縮技術(shù)分為四類：基于傳統(tǒng)存儲(chǔ)結(jié)構(gòu)的壓縮技術(shù)、網(wǎng)頁圖壓縮技術(shù)、社交網(wǎng)絡(luò)圖壓縮技術(shù)和面向特定查詢的圖壓縮技術(shù)。文獻(xiàn)［16］中對(duì)此作了進(jìn)一步歸納，將圖壓縮技術(shù)分為三類：基于圖數(shù)據(jù)外在特點(diǎn)的壓縮技術(shù)、基于圖數(shù)據(jù)內(nèi)在特點(diǎn)的壓縮技術(shù)和面向特定查詢需求的壓縮技術(shù)。

1）基于圖數(shù)據(jù)外在特點(diǎn)的壓縮技術(shù)。圖數(shù)據(jù)的外在特點(diǎn)是指圖的表示形式或圖的存儲(chǔ)結(jié)構(gòu)。傳統(tǒng)的圖數(shù)據(jù)表現(xiàn)形式和存儲(chǔ)結(jié)構(gòu)主要包括鄰接矩陣、鄰接鏈表、鄰接多重表、十字鏈表等。文獻(xiàn)［17-19］中針對(duì)圖數(shù)據(jù)鄰接矩陣的稀疏性對(duì)其進(jìn)行壓縮，文獻(xiàn)［20］中則通過壓縮處理圖數(shù)據(jù)的鄰接鏈表中存儲(chǔ)的冗余信息來實(shí)現(xiàn)圖壓縮；但是上述這幾種壓縮方法均改變了圖數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，通常不利于查詢。

2）基于圖數(shù)據(jù)內(nèi)在特點(diǎn)的壓縮技術(shù)。圖數(shù)據(jù)的內(nèi)在特點(diǎn)是指由于應(yīng)用領(lǐng)域的不同，圖數(shù)據(jù)所具有的不同的內(nèi)在性質(zhì)。例如，對(duì)社交網(wǎng)絡(luò)圖而言，可以利用社交網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)特性對(duì)圖數(shù)據(jù)進(jìn)行壓縮［21］，具體表現(xiàn)為社區(qū)內(nèi)相關(guān)性強(qiáng)，而社區(qū)間相關(guān)性弱；再如，對(duì)網(wǎng)頁圖而言，可以利用其本地性和相似性壓縮圖數(shù)據(jù)［22-24］；此外，在可視化分析領(lǐng)域，文獻(xiàn)［25-27］中針對(duì)數(shù)據(jù)圖稠密的特性，開發(fā)了相應(yīng)的稠密有向圖壓縮算法。

3）面向特定查詢需求的壓縮技術(shù)。查詢是圖數(shù)據(jù)研究中的基本操作，一直是圖領(lǐng)域中的研究熱點(diǎn)。常用的圖上查詢有可達(dá)性查詢、內(nèi)外鄰居查詢和圖模式匹配等。為了達(dá)到更低的壓縮比［28］，將不可避免地引起一些信息損失。因此，對(duì)面向特定查詢的壓縮圖來說，壓縮圖與原圖是一種基于特定查詢的等價(jià)圖［29］。

1.2 可達(dá)性查詢保持的圖壓縮技術(shù)

可達(dá)性查詢保持的圖壓縮是Fan 等［30］提出的概念，是一種面向可達(dá)性查詢的壓縮技術(shù)，這種壓縮技術(shù)追求極低的壓縮比，與此同時(shí)，保證了壓縮圖對(duì)可達(dá)性查詢保持結(jié)果不變，即其壓縮圖與原圖針對(duì)可達(dá)性查詢是等價(jià)的。文獻(xiàn)［30］提出的可達(dá)性查詢保持圖壓縮（Query Preserving Graph Compression，QPGC）算法，使用廣度優(yōu)先遍歷（Breadth-First Search，BFS）［31］的方法計(jì)算原圖中每個(gè)頂點(diǎn)的祖先頂點(diǎn)集和后代頂點(diǎn)集，由于具有相同祖先和后代的頂點(diǎn)關(guān)于可達(dá)性查詢是等價(jià)的，因此遍歷各頂點(diǎn)可確定可達(dá)性等價(jià)關(guān)系。文獻(xiàn)［30］同時(shí)提出了一種優(yōu)化策略：先計(jì)算原圖中的強(qiáng)連通分量，將其壓縮為一個(gè)虛擬頂點(diǎn)，得到一個(gè)有向無環(huán)圖（Directed Acyclic Graph，DAG）［32］，將此DAG 作為算法的輸入，最終獲得可達(dá)性查詢保持圖。該算法隨著圖數(shù)據(jù)規(guī)模的增大，表現(xiàn)逐漸不佳，耗時(shí)顯著增大。因?yàn)镼PGC 算法通過BFS 方法計(jì)算各頂點(diǎn)的祖先頂點(diǎn)集和后代頂點(diǎn)集的過程中存在冗余計(jì)算，而且BFS結(jié)果集比較龐大，導(dǎo)致可達(dá)性等價(jià)類的計(jì)算存在一定局限性。文獻(xiàn)［16］在QPGC 算法的基礎(chǔ)上，結(jié)合MapReduce［33］的思想，提出了適合于MapReduce 的可達(dá)性查詢保持圖計(jì)算方法，但是并沒有提高計(jì)算速度。文獻(xiàn)［34］中提出了一種基于BFS 結(jié)果集的可達(dá)性保持圖并行計(jì)算方法，但是該方法的主體為基于BFS 結(jié)果集的SCC 查找算法，僅考慮壓縮原圖中存在的強(qiáng)連通分量（Strongly Connected Components，SCC），不能達(dá)到QPGC算法的壓縮比。

在本文提出的低冗余計(jì)算低的可達(dá)性查詢保持圖壓縮策略的壓縮過程中，著重考慮避免進(jìn)行冗余計(jì)算，提高計(jì)算效率，以實(shí)現(xiàn)求解過程的加速，顯著提高壓縮速度。

2 本文方法

在求解祖先后代集過程和求解可達(dá)性等價(jià)類過程中，本文分別設(shè)計(jì)了高效、低冗余的求解算法。

2.1 高效的祖先后代集求解方法

在提出本文方法之前，首先對(duì)現(xiàn)有QPGC 算法求解祖先集和后代集過程中存在的問題進(jìn)行分析。

QPGC 算法以每個(gè)頂點(diǎn)為初始頂點(diǎn)，使用向前或向后的BFS 方法，分別求出其祖先頂點(diǎn)集和后代頂點(diǎn)集，要進(jìn)行2|V|次BFS遍歷。事實(shí)上，每個(gè)頂點(diǎn)的祖先（后代）集與其前驅(qū)（后繼）頂點(diǎn)的祖先（后代）集具有一定的聯(lián)系，算法在不同的遍歷順序下執(zhí)行時(shí)間大不相同，下面舉例說明。

例1 考慮圖1 所示的示例，使用BFS 方法求解各頂點(diǎn)的后代集，若遍歷順序?yàn)镋、A、B、C、D，則：在計(jì)算頂點(diǎn)E 的后代時(shí)，進(jìn)行了4 次訪問，后代集為{B，C，D}；計(jì)算頂點(diǎn)A 的后代時(shí)，進(jìn)行了4 次訪問，后代集為{B，C，D}；計(jì)算頂點(diǎn)B 的后代時(shí)，進(jìn)行了3 次訪問，后代集為{C，D}；計(jì)算頂點(diǎn)C 的后代時(shí)，進(jìn)行了2次訪問，后代集為{D}；計(jì)算頂點(diǎn)D的后代時(shí)，進(jìn)行了1 次訪問。共進(jìn)行了14 次訪問。然而，若按D、C、B、E、A 的順序求解，則只需進(jìn)行9 次訪問。這種冗余隨著圖的規(guī)模增大，將會(huì)進(jìn)一步增大。

針對(duì)現(xiàn)有方法由冗余計(jì)算引起的求解祖先后代集速度慢的問題，本文提出了兩種算法TSB 和AGGB，分別適用于一般的圖數(shù)據(jù)和最長(zhǎng)路徑長(zhǎng)度較小的圖數(shù)據(jù)，下面分別說明。

2.1.1 基于拓?fù)渑判虻淖嫦群蟠蠼馑惴═SB

在描述算法前，首先介紹拓?fù)渑判虻亩x及拓?fù)湫蛄芯哂械男再|(zhì)。

定義1拓?fù)渑判蚴嵌x在DAG 上的一種排序，其將圖G=(V，E)中所有頂點(diǎn)排成一個(gè)線性序列，使得對(duì)圖中任意一對(duì)頂點(diǎn)u和v，若(u，v)∈E，則u在該線性序列中出現(xiàn)在v之前。

引理1沿拓?fù)湫蛄许樞颍嫘颍┣蠼飧黜旤c(diǎn)的祖先集（后代集），每個(gè)頂點(diǎn)與邊需要且僅需要訪問1次。

證明

以沿拓?fù)湫蛄许樞蚯蠼庾嫦燃癁槔?/p>

因此，求解v的祖先集，僅需訪問v的每個(gè)父頂點(diǎn)各1次。

綜上所述，沿拓?fù)湫蛄许樞蚯蠼飧黜旤c(diǎn)的祖先集，每個(gè)頂點(diǎn)與邊需要且僅需要訪問1 次。類似地，可以證明沿拓?fù)湫蛄心嫘蚯蠼飧黜旤c(diǎn)的后代集，每個(gè)頂點(diǎn)與邊需要且僅需要訪問1次。

本文提出的基于拓?fù)渑判虻淖嫦群蟠蠼馑惴═SB如算法1所示。

首先，將原圖轉(zhuǎn)化為DAG。在實(shí)際應(yīng)用中，若圖數(shù)據(jù)不是DAG，則不能進(jìn)行拓?fù)渑判?，因此要?duì)其中的環(huán)（也即SCC）進(jìn)行特殊處理，將圖數(shù)據(jù)轉(zhuǎn)化為DAG。Gabow 算法［35］是求解SCC的經(jīng)典算法，本文使用Gabow算法求解圖中的SCC。

然后將每個(gè)SCC 用一個(gè)單頂點(diǎn)代替，此時(shí)圖數(shù)據(jù)變?yōu)镈AG。

接下來應(yīng)用BFS 方法對(duì)DAG 進(jìn)行拓?fù)渑判?，得到拓?fù)湫蛄?。過程簡(jiǎn)述如下：取一未訪問過的入度為0 的頂點(diǎn)，該頂點(diǎn)必為DAG 中某一棵樹（連通分量）的根頂點(diǎn)，應(yīng)用BFS 方法遍歷此樹；重復(fù)這一步驟，直到不存在未訪問過的頂點(diǎn)。頂點(diǎn)的遍歷順序即為拓?fù)湫蛄小?/p>

最后，沿拓?fù)湫蛄许樞蚯蠼飧黜旤c(diǎn)的祖先集，沿拓?fù)湫蛄心嫘蚯蠼飧黜旤c(diǎn)的后代集。

TSB和QPGC算法均使用了BFS方法對(duì)圖數(shù)據(jù)進(jìn)行遍歷，區(qū)別在于：QPGC 算法由每個(gè)頂點(diǎn)為初始點(diǎn)，應(yīng)用BFS 方法遍歷至最底層或最頂層，從而求得其祖先或后代頂點(diǎn)集；而TSB取根節(jié)點(diǎn)為初始點(diǎn)，使用一次BFS 遍歷求得DAG 的拓?fù)湫蛄?，沿拓?fù)湫蛄许樞蚧蚰嫘蚯蠼飧黜旤c(diǎn)的祖先后代頂點(diǎn)集，當(dāng)求解某頂點(diǎn)時(shí)，僅需訪問該頂點(diǎn)的鄰接頂點(diǎn)即可完成求解。

算法1 TSB。

輸入 圖G=(V，E)；

輸出 祖先頂點(diǎn)集AG和后代頂點(diǎn)集DG。

1）使用Gabow算法求解SCC；

2）壓縮每個(gè)SCC 為一個(gè)單頂點(diǎn)，得到與原圖對(duì)應(yīng)的DAG；

3）應(yīng)用BFS方法對(duì)DAG拓?fù)渑判?，得到拓?fù)湫蛄校?/p>

4）沿拓?fù)湫蛄许樞颍嫘颍┣蠼庾嫦燃ê蟠?/p>

例2 考慮圖2（a）所示的例圖，首先使用Gabow 算法求得SCC 為｛5｝，｛6｝，｛1，2，3｝，｛4｝；壓縮SCC 得到DAG 如圖2（b）；應(yīng)用BFS 方法對(duì)DAG 拓?fù)渑判?，得到拓?fù)湫蛄?，6，a，4（不唯一）；沿拓?fù)湫蝽樞蚯蠼庾嫦软旤c(diǎn)集，計(jì)算5 的祖先集為?，訪問1 次，計(jì)算6 的祖先集為?，訪問1 次，計(jì)算a 的祖先集為｛5，6，a｝，訪問3 次，計(jì)算4 的祖先集為｛5，6，a｝，訪問2 次，共訪問7 次；沿拓?fù)湫蚰嫘蚯蠼夂蟠旤c(diǎn)集，計(jì)算4 的后代集為?，訪問1 次，計(jì)算a 的后代集為｛a，4｝，訪問2 次，計(jì)算6 的后代集為｛a，4｝，訪問2 次，計(jì)算5 的后代集為｛a，4｝，訪問2次，共訪問7次。

圖2 TSB例圖Fig.2 Example of TSB algorithm

2.1.2 基于圖聚合運(yùn)算的祖先后代集求解算法

基于圖聚合運(yùn)算的祖先后代集求解算法AGGB 如算法2所示。

首先初始化各個(gè)頂點(diǎn)的祖先集和后代集為空集；接下來每個(gè)頂點(diǎn)分別向其父（子）頂點(diǎn)發(fā)送其后代（祖先）集；每個(gè)頂點(diǎn)接收到消息后，更新其自身的后代（祖先）集為原后代（祖先）集和其接收到的后代（祖先）集以及其子（父）頂點(diǎn)集的并集；重復(fù)發(fā)送—接收—更新的過程，直至所有頂點(diǎn)的后代集和祖先集均不再發(fā)生變化，算法結(jié)束。

AGGB 的聚合運(yùn)算次數(shù)與圖數(shù)據(jù)最長(zhǎng)路徑長(zhǎng)度具有正相關(guān)關(guān)系，因此適用于最長(zhǎng)路徑長(zhǎng)度較小的圖數(shù)據(jù)。

算法2 AGGB。

輸入 圖G=(V，E)；

輸出 祖先頂點(diǎn)集AG和后代頂點(diǎn)集DG。

1）初始化每個(gè)頂點(diǎn)的祖先集和后代集為空集；

2）每個(gè)頂點(diǎn)向其父頂點(diǎn)和子頂點(diǎn)分別發(fā)送其后代集和祖先集；

3）每個(gè)頂點(diǎn)接收其父頂點(diǎn)和子頂點(diǎn)發(fā)送的后代集和祖先集，更新自身的祖先集和后代集；

4）重復(fù)步驟2）、3），直到每個(gè)頂點(diǎn)的祖先集和后代集均不再發(fā)生變化。

例3 仍考慮圖2（a）所示的例圖。應(yīng)用AGGB：第1 次聚合運(yùn)算得到各頂點(diǎn)的祖先集（括號(hào)內(nèi)，下同）為5（?），6（?），2（｛3，5，6｝），1（｛2｝），3（｛1｝），4（｛1，3｝），后代集（括號(hào)內(nèi)，下同）為5（｛2｝），6（｛2｝），2（｛1｝），1（｛3，4｝），3（｛2，4｝），4（?）；第2 次聚合運(yùn)算得到的祖先集為5（?），6（?），2（｛1，3，5，6｝），1（｛2，3，5，6｝），3（｛1，2｝），4（｛1，2，3｝），后代集為5（｛1，2｝），6（｛1，2｝），2（｛1，3，4｝），1（｛2，3，4｝），3（｛1，2，4｝），4（?）；第3次聚合運(yùn)算得到的祖先集為5（?），6（?），2（｛1，2，3，5，6｝），1（｛1，2，3，5，6｝），3（｛1，2，3，5，6｝），4（｛1，2，3，5，6｝），后代集為5（｛1，2，3，4｝），6（｛1，2，3，4｝），2（｛1，2，3，4｝），1（｛1，2，3，4｝），3（｛1，2，3，4｝），4（?）；第4 次聚合運(yùn)算得到的祖先集為5（?），6（?），2（｛1，2，3，5，6｝），1（｛1，2，3，5，6｝），3（1，2，3，5，6），4（｛1，2，3，5，6｝），后代集為5（｛1，2，3，4｝），6（｛1，2，3，4｝），2（｛1，2，3，4｝），1（｛1，2，3，4｝），3（｛1，2，3，4｝），4（?）。祖先頂點(diǎn)集和后代頂點(diǎn)集均不再發(fā)生變化，求解結(jié)束，共進(jìn)行了4次聚合運(yùn)算。

2.1.3 算法性能對(duì)比分析

1）時(shí)間復(fù)雜度。

QPGC：對(duì)使用鄰接表存儲(chǔ)的圖數(shù)據(jù)，使用BFS 方法將頂點(diǎn)遍歷一次的時(shí)間復(fù)雜度為O(|V|+|E|)，而QPGC 算法求解祖先后代集時(shí)需對(duì)每個(gè)頂點(diǎn)分別進(jìn)行一次向前（向后）的BFS遍歷，從而獲得當(dāng)前頂點(diǎn)的祖先（后代）集，因此時(shí)間復(fù)雜度為O(|V|?(|V|+|E|))。

TSB：使用Gabow 算法求解SCC 時(shí)，對(duì)每個(gè)頂點(diǎn)和邊訪問1 次，時(shí)間復(fù)雜度為O(|V|+|E|)。壓縮SCC 為單頂點(diǎn)的時(shí)間復(fù)雜度為O(n)，其中n 為SCC 的個(gè)數(shù)（n ≤|V|）。使用BFS 方法對(duì)頂點(diǎn)拓?fù)渑判驎r(shí)，對(duì)每個(gè)頂點(diǎn)和邊訪問1 次，時(shí)間復(fù)雜度為O(|V|+|E|)。沿拓?fù)湫蛄许樞蚯蠼庾嫦燃瘯r(shí)，對(duì)每個(gè)頂點(diǎn)和邊訪問1 次，求解后代集亦然，時(shí)間復(fù)雜度為O(|V|+|E|)。因此TSB的時(shí)間復(fù)雜度為O(|V|+|E|)。

AGGB：算法需要最多不超過圖數(shù)據(jù)最長(zhǎng)路徑長(zhǎng)度次數(shù)的聚合運(yùn)算，每次聚合運(yùn)算訪問頂點(diǎn)和邊各兩次，時(shí)間復(fù)雜度為O(|V|+|E|)，因此，AGGB的時(shí)間復(fù)雜度為O(|V|+|E|)。

2）空間復(fù)雜度。

QPGC：算法使用BFS 方法遍歷圖數(shù)據(jù)，需要使用一個(gè)隊(duì)列，空間復(fù)雜度為O(|V|)。

TSB：算法使用Gabow算法求解SCC時(shí)，需使用兩個(gè)棧，此步驟空間復(fù)雜度為O(|V|)；算法求得的DAG 需使用鄰接表存儲(chǔ)，此步驟空間復(fù)雜度為O(|V|+|E|)；算法使用BFS 方法求拓?fù)湫蛄校枋褂靡粋€(gè)隊(duì)列，此步驟空間復(fù)雜度為O(|V|)；算法存儲(chǔ)拓?fù)湫蛄行枋褂靡粋€(gè)數(shù)組，此步驟空間復(fù)雜度為O(|V|)。因此，TSB空間復(fù)雜度為O(|V|+|E|)。

AGGB：算法可直接在祖先后代結(jié)果集上進(jìn)行操作，因此空間復(fù)雜度為O(1)。

分析三種算法的時(shí)間復(fù)雜度和空間復(fù)雜度，可以得出以下結(jié)論：與QPGC 算法相比，TSB 和AGGB 均將時(shí)間復(fù)雜度由O(|V|?(|V|+|E|))降至O(|V|+|E|)，其中TSB 以犧牲部分空間為代價(jià)，將空間復(fù)雜度由O(|V|)提高到O(|V|+|E|)，而AGGB 能夠進(jìn)一步將空間復(fù)雜度降至O(1)。AGGB 的特性決定其僅適用于最長(zhǎng)路徑較短的圖數(shù)據(jù)，而TSB的普適性更強(qiáng)。

2.2 分段統(tǒng)計(jì)剪枝的可達(dá)性等價(jià)類求解算法

針對(duì)現(xiàn)有算法由BFS結(jié)果集（即頂點(diǎn)祖先后代結(jié)果集）計(jì)算可達(dá)性等價(jià)類效率低的問題，本文提出了一種分段統(tǒng)計(jì)剪枝（PSP）算法（見算法3），可以有效提高可達(dá)性等價(jià)類的求解速度。首先，確定分段大小S，每S個(gè)頂點(diǎn)劃分為一個(gè)分段；接著對(duì)每一個(gè)頂點(diǎn)，分別統(tǒng)計(jì)其祖先集和后代集落在對(duì)應(yīng)分段內(nèi)的頂點(diǎn)個(gè)數(shù)。這個(gè)過程可以在計(jì)算祖先和后代集的同時(shí)進(jìn)行，每求得當(dāng)前頂點(diǎn)的一個(gè)祖先頂點(diǎn)，就為這一祖先頂點(diǎn)所在的分段的統(tǒng)計(jì)值加1，這一過程每次要計(jì)算一次除法（計(jì)算所在分段）和一次加法。接下來，對(duì)每一個(gè)頂點(diǎn)對(duì)，首先判斷二者的統(tǒng)計(jì)值是否相同，若不相同，則二者祖先集和后代集必然不同，因此不屬于同一可達(dá)性等價(jià)類，無需進(jìn)行精細(xì)比較，從而達(dá)到快速剪枝的效果；若相同，則二者存在祖先集和后代集相同的可能，進(jìn)一步精細(xì)比較二者的祖先集和后代集，若二者具有相同的祖先和后代，則屬于同一可達(dá)性等價(jià)類，否則不屬于同一可達(dá)性等價(jià)類。最后，將所有的可達(dá)性等價(jià)類構(gòu)成的集合輸出。

算法3 PSP算法。

輸入 祖先集和后代集；

輸出 可達(dá)性等價(jià)類集。

1）確定分段大小S；

2）遍歷頂點(diǎn)，對(duì)每個(gè)頂點(diǎn)分別統(tǒng)計(jì)其祖先集和后代集在每個(gè)分段內(nèi)的個(gè)數(shù)；

3）遍歷頂點(diǎn)對(duì)，若頂點(diǎn)對(duì)的統(tǒng)計(jì)值相同，則進(jìn)一步比較頂點(diǎn)對(duì)的祖先集和后代集是否相同，否則無需進(jìn)一步比較；

4）具有相同祖先集和后代集的頂點(diǎn)構(gòu)成一個(gè)可達(dá)性等價(jià)類，不存在相同祖先集和后代集的頂點(diǎn)單獨(dú)作為一個(gè)可達(dá)性等價(jià)類。

例4 有頂點(diǎn)A、B、…、I，設(shè)A 的祖先集為{C，D，E，G，H}，B 的祖先集為{C，D，G，H，I}，為比較A、B 的祖先集，傳統(tǒng)方法需對(duì)兩個(gè)集合取交集得{C，D，G，H}，其交集元素個(gè)數(shù)小于原集合元素個(gè)數(shù)，因此不等價(jià)。PSP 算法考慮將頂點(diǎn)進(jìn)行分段，以分段大小S=3 為例，此時(shí)各分段的頂點(diǎn)為{A，B，C}、{D，E，F(xiàn)}、{G，H，I}，對(duì)A的祖先集統(tǒng)計(jì)結(jié)果為［1，2，2］，B的統(tǒng)計(jì)結(jié)果為［1，1，3］，對(duì)A、B的統(tǒng)計(jì)結(jié)果進(jìn)行比較，若不同，可以斷言A、B 的祖先集不同，無需進(jìn)行精細(xì)比較；若A 的祖先集不變，B的祖先集改為{C，D，F(xiàn)，G，I}，則B的統(tǒng)計(jì)結(jié)果變?yōu)椋?，2，2］，A、B 的統(tǒng)計(jì)結(jié)果一致，需采用傳統(tǒng)方法進(jìn)一步進(jìn)行精細(xì)比較。

在頂點(diǎn)對(duì)的比較過程中，QPGC 算法每次都進(jìn)行精細(xì)比較，設(shè)其用時(shí)為f(|V|)，由于PSP算法先對(duì)長(zhǎng)度為的統(tǒng)計(jì)值進(jìn)行比較，如果統(tǒng)計(jì)值相同，再進(jìn)行精細(xì)比較，因此，其用時(shí)可表示為f(L+p ?|V|)，其中p 為進(jìn)行精細(xì)比較的概率，則PSP 算法與QPGC 算法的用時(shí)比為若f 為線性函數(shù)，則用時(shí)比為

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集與環(huán)境

本文使用了6 組實(shí)驗(yàn)數(shù)據(jù)集，數(shù)據(jù)集名稱、大小、來源及在文中的簡(jiǎn)稱如表1所示；實(shí)驗(yàn)環(huán)境配置如表2所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集Tab.1 Experimental datasets

表2 實(shí)驗(yàn)環(huán)境配置表Tab.2 Configuration of experimental environment

3.2 實(shí)驗(yàn)結(jié)果與分析

進(jìn)行2 組實(shí)驗(yàn)來驗(yàn)證本文提出的可達(dá)性查詢保持圖壓縮策略的可行性和高效性。第1 組實(shí)驗(yàn)對(duì)改進(jìn)的祖先后代集求解算法TSB和AGGB與原始算法QPGC的性能進(jìn)行了對(duì)比；第2 組實(shí)驗(yàn)對(duì)改進(jìn)的可達(dá)性等價(jià)類求解算法PSP 和原始算法QPGC 的性能進(jìn)行了對(duì)比，并對(duì)分段大小S 與PSP 算法性能的關(guān)系進(jìn)行了實(shí)驗(yàn)分析。接下來，實(shí)驗(yàn)分析了PSP 算法由分段統(tǒng)計(jì)引發(fā)的額外存儲(chǔ)空間的消耗。最后，對(duì)比了QPGC 算法和本文算法的整體耗時(shí)。為保證實(shí)驗(yàn)結(jié)果的穩(wěn)定性，本文所有實(shí)驗(yàn)結(jié)果均為5次實(shí)驗(yàn)取平均值。

本文方法與QPGC 算法采用相同的壓縮理念，根據(jù)可達(dá)性等價(jià)頂點(diǎn)集具有相同的可達(dá)性關(guān)系，對(duì)其進(jìn)行壓縮，得到的壓縮圖與原圖是可達(dá)性等價(jià)的，壓縮圖中可達(dá)性查詢的結(jié)果就是原圖上的結(jié)果。本文提出的壓縮策略與QPGC 算法得到的壓縮結(jié)果完全一致，壓縮效果如表3所示。文獻(xiàn)［30］第6章中對(duì)不同數(shù)據(jù)集應(yīng)用可達(dá)性查詢保持圖壓縮算法達(dá)到的效果進(jìn)行了較為詳細(xì)的對(duì)比和分析，本文不再贅述。

表3 本文算法的壓縮率Tab.3 Compression ratio of the proposed algorithm

3.2.1 祖先后代集求解算法性能對(duì)比實(shí)驗(yàn)

本文算法相對(duì)QPGC 算法的加速比如表4 所示。從表中可以看出，與QPGC 算法相比，本文提出的兩種算法執(zhí)行時(shí)間顯著減少，其中TSB 平均加速94.22%，AGGB 平均加速90.00%。

TSB 和AGGB 間互有優(yōu)劣。在數(shù)據(jù)集Y0 上，AGGB 執(zhí)行速度較TSB 快；在數(shù)據(jù)集WebC 和WikiV 上，TSB 執(zhí)行速度較AGGB 略快；在數(shù)據(jù)集CHT 和CHP 上，AGGB 較TSB 執(zhí)行速度慢近50%，這是因?yàn)檫@兩個(gè)數(shù)據(jù)集為引文數(shù)據(jù)集，其數(shù)據(jù)圖中路徑較長(zhǎng)，聚合運(yùn)算次數(shù)較多。

表4 TSB、AGGB與QPGC三種算法的性能對(duì)比Tab.4 Performance comparison of TSB，AGGB and QPGC

TSB、AGGB 和QPGC 算法的執(zhí)行時(shí)間隨數(shù)據(jù)集規(guī)模變化的趨勢(shì)如圖3 所示。從圖中可以看出，隨著數(shù)據(jù)集規(guī)模的擴(kuò)大，三種算法求解祖先集與后代集過程的執(zhí)行時(shí)間均呈現(xiàn)上升趨勢(shì)，其中QPGC 算法受數(shù)據(jù)集規(guī)模影響較大，上升速度較快，TSB和AGGB受數(shù)據(jù)集規(guī)模影響較小，上升速度緩慢。

圖3 三種算法執(zhí)行時(shí)間隨數(shù)據(jù)集規(guī)模變化趨勢(shì)Fig.3 Trend of the execution time of three algorithms with increasing dataset

最后對(duì)TSB、AGGB 和QPGC 算法求解祖先后代集的存儲(chǔ)開銷進(jìn)行對(duì)比。由于3 種算法的輸入輸出一致，僅考慮中間變量的存儲(chǔ)占用情況，如表5 所示。從表中可以看出，與QPGC 算法相比，TSB 中間變量?jī)?nèi)存使用明顯增大，但是其值在可以接受的范圍內(nèi)（KB 級(jí)），而AGGB 僅使用固定的中間變量，內(nèi)存占用較小且不變。因此，本文方法在大數(shù)據(jù)上較QPGC算法有更優(yōu)異的表現(xiàn)。

表5 三種算法中間變量的存儲(chǔ)占用對(duì)比Tab.5 Comparison of memory usage of intermediate variables of three algorithms

3.2.2 可達(dá)性等價(jià)類求解算法性能對(duì)比實(shí)驗(yàn)

首先對(duì)PSP 算法在不同分段大小S 取值下相對(duì)QPGC 算法的加速效果進(jìn)行對(duì)比。

取分段大小S為5、10、50、100、500、1 000、2 000，PSP算法相對(duì)QPGC 算法的加速比如圖4 所示?？梢钥闯觯煌腟 取值下，PSP 算法較QPGC 算法計(jì)算速度均有明顯提升，顯著提高了可達(dá)性等價(jià)類的計(jì)算速度，除Y0 數(shù)據(jù)集外，加速效果均在70%以上，其中對(duì)數(shù)據(jù)集WebC、CHT 和CHP，加速效果達(dá)到了90%以上。

圖4 PSP算法相對(duì)QPGC算法的加速比Fig.4 Speedup of PSP algorithm compared to QPGC algorithm

接下來，對(duì)PSP 算法在不同數(shù)據(jù)集上較QPGC 算法的加速效果進(jìn)行分析。

通過分析對(duì)比，PSP 算法與QPGC 算法的用時(shí)比（用時(shí)比與加速比的和為1）與數(shù)據(jù)集壓縮后得到的等價(jià)壓縮圖的點(diǎn)邊比間的關(guān)系如圖5 所示，可以看出，兩種算法的用時(shí)比與壓縮圖的點(diǎn)邊比呈正相關(guān)關(guān)系，因此，精細(xì)比較的概率p 與壓縮圖的點(diǎn)邊比呈正相關(guān)關(guān)系。

此外，分段大小S 也會(huì)影響p 的取值，隨著S 取值的變化，p 也會(huì)發(fā)生變化，從而導(dǎo)致PSP 算法較QPGC 算法的加速比發(fā)生變化。從圖4 中可以看出，當(dāng)S 取值為100 時(shí)，加速比基本達(dá)到最高值，此后，WikiV 數(shù)據(jù)集上加速比開始下降，其他數(shù)據(jù)集上加速比有極小幅度的上升。鑒于此，本文對(duì)S 取值在［5，200］區(qū)間內(nèi)加速比的變化做了進(jìn)一步研究，結(jié)果如圖6 所示。從圖中可以看出，當(dāng)S取值很小時(shí)，加速比較??；S在［50，100］區(qū)間內(nèi)，加速比基本達(dá)到最高值；此后，加速比有一定的波動(dòng)，并逐漸開始下降。這是因?yàn)?，如果S 取值過小，分段數(shù)將增大，粗粒度比較的計(jì)算成本升高；如果S 取值過大，將有更多的頂點(diǎn)被誤分為備選可達(dá)性等價(jià)頂點(diǎn)集，從而導(dǎo)致精細(xì)比較次數(shù)增多，提高了計(jì)算成本。另外，加速比的變化不是平滑的，具有一定的波動(dòng)性，這與分段統(tǒng)計(jì)過程中，分段大小、編號(hào)順序、祖先后代分布均有一定的關(guān)系。

圖5 用時(shí)比與數(shù)據(jù)集壓縮后得到的等價(jià)壓縮圖的點(diǎn)邊比間的關(guān)系Fig.5 Relationship between time cost ratio and point-edge ratio of equivalent compression graph obtained after data set compression

圖6 PSP算法相對(duì)QPGC算法加速比與分段大小S的關(guān)系Fig.6 Relationship between speedup of PSP algorithm compared to QPGC algorithm and segment size S

另一方面，分段統(tǒng)計(jì)帶來了額外的存儲(chǔ)開銷，且空間占用與S 的大小有關(guān)，如表6 所示?？梢钥闯?，當(dāng)S 取值較小時(shí)，存儲(chǔ)空間占用較大，且隨著數(shù)據(jù)集的增大，存儲(chǔ)空間也在增大。當(dāng)S 取1 000 時(shí)，CHT 和CHP 數(shù)據(jù)集上存儲(chǔ)空間占用不足1 MB，是當(dāng)前硬件條件下可以接受的。

表6 不同分段大小S下的存儲(chǔ)空間占用Tab.6 Memory usage under different segment size S

綜上所述，S 取值過小，存儲(chǔ)空間占用會(huì)顯著增大，S 取值過大，精細(xì)比較的概率p隨之增大，因此，分段大小S取值應(yīng)適中，并結(jié)合具體應(yīng)用環(huán)境進(jìn)行分析，達(dá)成時(shí)間和空間的協(xié)調(diào)。例如，在應(yīng)用中，若存儲(chǔ)空間較為充足，則可適當(dāng)?shù)臏p小S，以空間換時(shí)間，否則應(yīng)適當(dāng)增大S。

接下來，對(duì)兩個(gè)階段的執(zhí)行時(shí)間占比進(jìn)行統(tǒng)計(jì)分析。以Y0 和WikiV 數(shù)據(jù)集為例，取分段大小S=100，求解祖先后代集階段（第1 階段）和求解可達(dá)性等價(jià)類階段（第2 階段）的占比如圖7 所示。從圖中可以看出，第2 階段用時(shí)所占比重更大。

圖7 兩階段執(zhí)行時(shí)間占比Fig.7 Proportion of execution time in two stages

最后，在6 組數(shù)據(jù)集上分別應(yīng)用TSB+S100、AGGB+S100和QPGC 算法，總體用時(shí)對(duì)比如表7 所示。從表中可以看出，本文提出的TSB 和AGGB 配合PSP 算法，時(shí)間性能提升顯著，隨著數(shù)據(jù)量的增大，性能提升近28倍。

表7 總體用時(shí)對(duì)比Tab.7 Total time cost comparison

4 結(jié)語

本文提出了一種低冗余計(jì)算的可達(dá)性查詢保持圖壓縮策略。其中：TSB 通過拓?fù)渑判虼_定祖先后代集求解順序，避免了重復(fù)計(jì)算；AGGB 可在不超過最長(zhǎng)路徑長(zhǎng)度次數(shù)的聚合運(yùn)算內(nèi)完成求解，對(duì)最長(zhǎng)路徑長(zhǎng)度較小的數(shù)據(jù)圖有較好的效果；PSP 算法預(yù)分段統(tǒng)計(jì)BFS 結(jié)果集，利用統(tǒng)計(jì)值對(duì)匹配過程剪枝，剪除了大量的不必要匹配。實(shí)驗(yàn)結(jié)果表明，本文提出的可達(dá)性查詢保持圖壓縮策略，較現(xiàn)有方法顯著減少了冗余計(jì)算，在不同的數(shù)據(jù)集上均取得了較好的加速效果。因此，本文策略提高了壓縮速度，冗余計(jì)算少，是可行且高效的。

下一步，我們將研究大規(guī)模圖數(shù)據(jù)可達(dá)性查詢的應(yīng)答策略，從查詢求解的角度減少應(yīng)答時(shí)間，提高應(yīng)答速度。