低冗余計算的可達性查詢保持圖壓縮策略

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

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

0 引言

近年來，隨著計算機技術和網絡技術的發展，現實生活中很多領域產生了越來越多的網絡數據，如語義網［1］、萬維網［2］、道路網［3］、推薦網［4］、社交網［5］以及生物信息網［6］等，并且這些網絡中的數據結構趨于復雜，難以用關系數據模型描述。圖作為一種能夠有效描述事物之間復雜關系的數據結構，在上述領域得到了廣泛的研究和應用。

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

針對圖數據規模增大引發的查詢難問題，主要有以下三種解決方法［15］：1）使用硬盤存儲圖數據，每次載入部分圖數據到內存中，分步查詢，最后整合結果；2）使用分布式系統存儲圖數據，每個節點進行部分查詢，最后整合結果；3）將圖數據進行壓縮表示，全部載入內存中，直接查詢得到結果。

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

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

本文的主要工作如下：

1）針對求解祖先后代集過程設計了一種基于拓撲排序的祖先后代集求解算法（Topological Sorting Based algorithm for solving ancestor and descendant sets，TSB），能有效地減少冗余計算，加快求解速度；還設計了一種基于圖聚合運算的祖先后代集求解算法（AGGregation Based algorithm for solving ancestor and descendant sets，AGGB），對最長路徑長度較小的圖數據有較好效果。

2）針對求解可達性等價類過程設計了一種分段統計剪枝（Piecewise Statistical Pruning，PSP）算法，實現了可達性等價類求解過程的剪枝，減少了冗余匹配，加快了求解速度。

3）應用不同數據集進行實驗，結果表明，本文提出的可達性查詢保持圖壓縮策略是高效、快速的。

1 相關工作

對圖數據進行高效、緊湊的表示與壓縮是當前圖研究的熱點之一，同時也為圖上的其他基本算法和操作提供了強有力的支持，包括存儲空間優化、查詢優化及可視化分析等。

1.1 圖壓縮技術的分類

文獻［15］中將圖壓縮技術分為四類：基于傳統存儲結構的壓縮技術、網頁圖壓縮技術、社交網絡圖壓縮技術和面向特定查詢的圖壓縮技術。文獻［16］中對此作了進一步歸納，將圖壓縮技術分為三類：基于圖數據外在特點的壓縮技術、基于圖數據內在特點的壓縮技術和面向特定查詢需求的壓縮技術。

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

2）基于圖數據內在特點的壓縮技術。圖數據的內在特點是指由于應用領域的不同，圖數據所具有的不同的內在性質。例如，對社交網絡圖而言，可以利用社交網絡中的社區結構特性對圖數據進行壓縮［21］，具體表現為社區內相關性強，而社區間相關性弱；再如，對網頁圖而言，可以利用其本地性和相似性壓縮圖數據［22-24］；此外，在可視化分析領域，文獻［25-27］中針對數據圖稠密的特性，開發了相應的稠密有向圖壓縮算法。

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

1.2 可達性查詢保持的圖壓縮技術

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

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

2 本文方法

在求解祖先后代集過程和求解可達性等價類過程中，本文分別設計了高效、低冗余的求解算法。

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

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

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

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

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

2.1.1 基于拓撲排序的祖先后代集求解算法TSB

在描述算法前，首先介紹拓撲排序的定義及拓撲序列具有的性質。

定義1拓撲排序是定義在DAG 上的一種排序，其將圖G=(V，E)中所有頂點排成一個線性序列，使得對圖中任意一對頂點u和v，若(u，v)∈E，則u在該線性序列中出現在v之前。

引理1沿拓撲序列順序（逆序）求解各頂點的祖先集（后代集），每個頂點與邊需要且僅需要訪問1次。

證明

以沿拓撲序列順序求解祖先集為例：

因此，求解v的祖先集，僅需訪問v的每個父頂點各1次。

綜上所述，沿拓撲序列順序求解各頂點的祖先集，每個頂點與邊需要且僅需要訪問1 次。類似地，可以證明沿拓撲序列逆序求解各頂點的后代集，每個頂點與邊需要且僅需要訪問1次。

本文提出的基于拓撲排序的祖先后代集求解算法TSB如算法1所示。

首先，將原圖轉化為DAG。在實際應用中，若圖數據不是DAG，則不能進行拓撲排序，因此要對其中的環（也即SCC）進行特殊處理，將圖數據轉化為DAG。Gabow 算法［35］是求解SCC的經典算法，本文使用Gabow算法求解圖中的SCC。

然后將每個SCC 用一個單頂點代替，此時圖數據變為DAG。

接下來應用BFS 方法對DAG 進行拓撲排序，得到拓撲序列。過程簡述如下：取一未訪問過的入度為0 的頂點，該頂點必為DAG 中某一棵樹（連通分量）的根頂點，應用BFS 方法遍歷此樹；重復這一步驟，直到不存在未訪問過的頂點。頂點的遍歷順序即為拓撲序列。

最后，沿拓撲序列順序求解各頂點的祖先集，沿拓撲序列逆序求解各頂點的后代集。

TSB和QPGC算法均使用了BFS方法對圖數據進行遍歷，區別在于：QPGC 算法由每個頂點為初始點，應用BFS 方法遍歷至最底層或最頂層，從而求得其祖先或后代頂點集；而TSB取根節點為初始點，使用一次BFS 遍歷求得DAG 的拓撲序列，沿拓撲序列順序或逆序求解各頂點的祖先后代頂點集，當求解某頂點時，僅需訪問該頂點的鄰接頂點即可完成求解。

算法1 TSB。

輸入 圖G=(V，E)；

輸出 祖先頂點集AG和后代頂點集DG。

1）使用Gabow算法求解SCC；

2）壓縮每個SCC 為一個單頂點，得到與原圖對應的DAG；

3）應用BFS方法對DAG拓撲排序，得到拓撲序列；

4）沿拓撲序列順序（逆序）求解祖先集（后代集）。

例2 考慮圖2（a）所示的例圖，首先使用Gabow 算法求得SCC 為｛5｝，｛6｝，｛1，2，3｝，｛4｝；壓縮SCC 得到DAG 如圖2（b）；應用BFS 方法對DAG 拓撲排序，得到拓撲序列5，6，a，4（不唯一）；沿拓撲序順序求解祖先頂點集，計算5 的祖先集為?，訪問1 次，計算6 的祖先集為?，訪問1 次，計算a 的祖先集為｛5，6，a｝，訪問3 次，計算4 的祖先集為｛5，6，a｝，訪問2 次，共訪問7 次；沿拓撲序逆序求解后代頂點集，計算4 的后代集為?，訪問1 次，計算a 的后代集為｛a，4｝，訪問2 次，計算6 的后代集為｛a，4｝，訪問2 次，計算5 的后代集為｛a，4｝，訪問2次，共訪問7次。

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

2.1.2 基于圖聚合運算的祖先后代集求解算法

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

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

AGGB 的聚合運算次數與圖數據最長路徑長度具有正相關關系，因此適用于最長路徑長度較小的圖數據。

算法2 AGGB。

輸入 圖G=(V，E)；

輸出 祖先頂點集AG和后代頂點集DG。

1）初始化每個頂點的祖先集和后代集為空集；

2）每個頂點向其父頂點和子頂點分別發送其后代集和祖先集；

3）每個頂點接收其父頂點和子頂點發送的后代集和祖先集，更新自身的祖先集和后代集；

4）重復步驟2）、3），直到每個頂點的祖先集和后代集均不再發生變化。

例3 仍考慮圖2（a）所示的例圖。應用AGGB：第1 次聚合運算得到各頂點的祖先集（括號內，下同）為5（?），6（?），2（｛3，5，6｝），1（｛2｝），3（｛1｝），4（｛1，3｝），后代集（括號內，下同）為5（｛2｝），6（｛2｝），2（｛1｝），1（｛3，4｝），3（｛2，4｝），4（?）；第2 次聚合運算得到的祖先集為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次聚合運算得到的祖先集為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 次聚合運算得到的祖先集為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次聚合運算。

2.1.3 算法性能對比分析

1）時間復雜度。

QPGC：對使用鄰接表存儲的圖數據，使用BFS 方法將頂點遍歷一次的時間復雜度為O(|V|+|E|)，而QPGC 算法求解祖先后代集時需對每個頂點分別進行一次向前（向后）的BFS遍歷，從而獲得當前頂點的祖先（后代）集，因此時間復雜度為O(|V|?(|V|+|E|))。

TSB：使用Gabow 算法求解SCC 時，對每個頂點和邊訪問1 次，時間復雜度為O(|V|+|E|)。壓縮SCC 為單頂點的時間復雜度為O(n)，其中n 為SCC 的個數（n ≤|V|）。使用BFS 方法對頂點拓撲排序時，對每個頂點和邊訪問1 次，時間復雜度為O(|V|+|E|)。沿拓撲序列順序求解祖先集時，對每個頂點和邊訪問1 次，求解后代集亦然，時間復雜度為O(|V|+|E|)。因此TSB的時間復雜度為O(|V|+|E|)。

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

2）空間復雜度。

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

TSB：算法使用Gabow算法求解SCC時，需使用兩個棧，此步驟空間復雜度為O(|V|)；算法求得的DAG 需使用鄰接表存儲，此步驟空間復雜度為O(|V|+|E|)；算法使用BFS 方法求拓撲序列，需使用一個隊列，此步驟空間復雜度為O(|V|)；算法存儲拓撲序列需使用一個數組，此步驟空間復雜度為O(|V|)。因此，TSB空間復雜度為O(|V|+|E|)。

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

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

2.2 分段統計剪枝的可達性等價類求解算法

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

算法3 PSP算法。

輸入 祖先集和后代集；

輸出 可達性等價類集。

1）確定分段大小S；

2）遍歷頂點，對每個頂點分別統計其祖先集和后代集在每個分段內的個數；

3）遍歷頂點對，若頂點對的統計值相同，則進一步比較頂點對的祖先集和后代集是否相同，否則無需進一步比較；

4）具有相同祖先集和后代集的頂點構成一個可達性等價類，不存在相同祖先集和后代集的頂點單獨作為一個可達性等價類。

例4 有頂點A、B、…、I，設A 的祖先集為{C，D，E，G，H}，B 的祖先集為{C，D，G，H，I}，為比較A、B 的祖先集，傳統方法需對兩個集合取交集得{C，D，G，H}，其交集元素個數小于原集合元素個數，因此不等價。PSP 算法考慮將頂點進行分段，以分段大小S=3 為例，此時各分段的頂點為{A，B，C}、{D，E，F}、{G，H，I}，對A的祖先集統計結果為［1，2，2］，B的統計結果為［1，1，3］，對A、B的統計結果進行比較，若不同，可以斷言A、B 的祖先集不同，無需進行精細比較；若A 的祖先集不變，B的祖先集改為{C，D，F，G，I}，則B的統計結果變為［1，2，2］，A、B 的統計結果一致，需采用傳統方法進一步進行精細比較。

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

3 實驗結果與分析

3.1 實驗數據集與環境

本文使用了6 組實驗數據集，數據集名稱、大小、來源及在文中的簡稱如表1所示；實驗環境配置如表2所示。

表1 實驗數據集Tab.1 Experimental datasets

表2 實驗環境配置表Tab.2 Configuration of experimental environment

3.2 實驗結果與分析

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

本文方法與QPGC 算法采用相同的壓縮理念，根據可達性等價頂點集具有相同的可達性關系，對其進行壓縮，得到的壓縮圖與原圖是可達性等價的，壓縮圖中可達性查詢的結果就是原圖上的結果。本文提出的壓縮策略與QPGC 算法得到的壓縮結果完全一致，壓縮效果如表3所示。文獻［30］第6章中對不同數據集應用可達性查詢保持圖壓縮算法達到的效果進行了較為詳細的對比和分析，本文不再贅述。

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

3.2.1 祖先后代集求解算法性能對比實驗

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

TSB 和AGGB 間互有優劣。在數據集Y0 上，AGGB 執行速度較TSB 快；在數據集WebC 和WikiV 上，TSB 執行速度較AGGB 略快；在數據集CHT 和CHP 上，AGGB 較TSB 執行速度慢近50%，這是因為這兩個數據集為引文數據集，其數據圖中路徑較長，聚合運算次數較多。

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

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

圖3 三種算法執行時間隨數據集規模變化趨勢Fig.3 Trend of the execution time of three algorithms with increasing dataset

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

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

3.2.2 可達性等價類求解算法性能對比實驗

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

取分段大小S為5、10、50、100、500、1 000、2 000，PSP算法相對QPGC 算法的加速比如圖4 所示。可以看出，不同的S 取值下，PSP 算法較QPGC 算法計算速度均有明顯提升，顯著提高了可達性等價類的計算速度，除Y0 數據集外，加速效果均在70%以上，其中對數據集WebC、CHT 和CHP，加速效果達到了90%以上。

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

接下來，對PSP 算法在不同數據集上較QPGC 算法的加速效果進行分析。

通過分析對比，PSP 算法與QPGC 算法的用時比（用時比與加速比的和為1）與數據集壓縮后得到的等價壓縮圖的點邊比間的關系如圖5 所示，可以看出，兩種算法的用時比與壓縮圖的點邊比呈正相關關系，因此，精細比較的概率p 與壓縮圖的點邊比呈正相關關系。

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

圖5 用時比與數據集壓縮后得到的等價壓縮圖的點邊比間的關系Fig.5 Relationship between time cost ratio and point-edge ratio of equivalent compression graph obtained after data set compression

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

另一方面，分段統計帶來了額外的存儲開銷，且空間占用與S 的大小有關，如表6 所示。可以看出，當S 取值較小時，存儲空間占用較大，且隨著數據集的增大，存儲空間也在增大。當S 取1 000 時，CHT 和CHP 數據集上存儲空間占用不足1 MB，是當前硬件條件下可以接受的。

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

綜上所述，S 取值過小，存儲空間占用會顯著增大，S 取值過大，精細比較的概率p隨之增大，因此，分段大小S取值應適中，并結合具體應用環境進行分析，達成時間和空間的協調。例如，在應用中，若存儲空間較為充足，則可適當的減小S，以空間換時間，否則應適當增大S。

接下來，對兩個階段的執行時間占比進行統計分析。以Y0 和WikiV 數據集為例，取分段大小S=100，求解祖先后代集階段（第1 階段）和求解可達性等價類階段（第2 階段）的占比如圖7 所示。從圖中可以看出，第2 階段用時所占比重更大。

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

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

表7 總體用時對比Tab.7 Total time cost comparison

4 結語

本文提出了一種低冗余計算的可達性查詢保持圖壓縮策略。其中：TSB 通過拓撲排序確定祖先后代集求解順序，避免了重復計算；AGGB 可在不超過最長路徑長度次數的聚合運算內完成求解，對最長路徑長度較小的數據圖有較好的效果；PSP 算法預分段統計BFS 結果集，利用統計值對匹配過程剪枝，剪除了大量的不必要匹配。實驗結果表明，本文提出的可達性查詢保持圖壓縮策略，較現有方法顯著減少了冗余計算，在不同的數據集上均取得了較好的加速效果。因此，本文策略提高了壓縮速度，冗余計算少，是可行且高效的。

下一步，我們將研究大規模圖數據可達性查詢的應答策略，從查詢求解的角度減少應答時間，提高應答速度。