大規模圖數據的k2-MDD表示方法與操作研究

董榮勝 張新凱 劉華東 古天龍

(廣西可信軟件重點實驗室(桂林電子科技大學) 廣西桂林 541004)(ccrsdong@guet.edu.cn)

?

大規模圖數據的k2-MDD表示方法與操作研究

董榮勝 張新凱 劉華東 古天龍

(廣西可信軟件重點實驗室(桂林電子科技大學) 廣西桂林 541004)(ccrsdong@guet.edu.cn)

對包含億萬個頂點和邊的圖數據進行高效、緊湊的表示和操作是大規模圖數據分析處理的基礎.針對該問題提出了基于決策圖的大規模圖數據的一種表示方法——k2-MDD，給出了k2-MDD的構造過程以及圖的邊查詢、外(內)鄰查詢、出(入)度查詢、添加(刪除)邊等基本操作.該表示方法在k2樹的基礎上進行優化與改進，對圖的鄰接矩陣進行k2劃分后，采用多值決策圖進行存儲，從而達到存儲結構更為緊湊的目的.通過對來自米蘭大學LAW實驗室的一系列真實網頁圖和社交網絡圖數據的實驗結果可以看出，k2-MDD結構在節點數上僅為k2樹的2.59%～4.51%，達到了預期效果.通過對隨機圖的實驗結果可以看出，k2-MDD結構不僅適用于稀疏圖，同樣也適用于稠密圖.圖數據的k2-MDD表示，既具有k2樹表示的緊湊型和查詢的高效性，又能實現符號決策圖表示下圖模式的高效操作，從而實現了描述和計算能力的統一.

圖數據；存儲優化；k2-MDD；k2樹；決策圖

隨著移動互聯網、物聯網等技術的發展，眾多新應用以前所未有的方式和速度產生并積累著大量數據.在眾多類型的大數據中，圖數據作為一種有效描述大數據的數據結構，扮演著越來越重要的角色[1-2].由于圖數據的規模日益龐大，如何對圖數據進行高效的存儲以及如何對圖數據進行高效的操作是當前面臨的兩大挑戰.以社交網絡為例，根據GlobalWebIndex統計，Facebook用戶量已經超過11億，平均每個人的好友超過100位，使用鄰接表來存儲所有用戶的關系信息，需要接近1TB的存儲空間[3]；以互聯網為例，根據中國互聯網絡信息中心(CNNIC)發布的《第37次中國互聯網絡發展狀況統計報告》[4]，截至2015年12月中國網頁數量為2 123億個，超鏈接數量據估計超過1013，使用鄰接表來存儲網頁直接的鏈接關系信息需要超過16 TB的存儲空間.同時隨著用戶量和信息量的快速增長，問題也只會變得越來越嚴峻.

為了對圖數據進行緊湊表示，在傳統的鄰接矩陣表示法的基礎上，Brisaboa等人[5]于2009年提出了基于k2樹(k2-tree)的方法，樹中的每一層對應于鄰接矩陣或分塊子矩陣的分塊子矩陣，節點對應于鄰接矩陣的分塊子矩陣，生成的k2樹使用2個位向量T和L來存儲，該方法不僅能夠緊湊表示鄰接矩陣，而且能實現鄰接節點的正向或逆向高效查詢操作[6].施佺等人[7-8]給出了k2樹表示方法的2種優化技術：啟發式深度優先節點重排序和自適應修正k，使得所表示的結構更為緊湊，節點得到明顯的減少.

但是，不論是k2樹還是施佺等人優化過的k2樹，在對大規模圖數據表示時仍具有一定的局限性，具體表現在3個方面：

1) 當圖的規模變大時，圖內部本身就會存在大量的同構子圖.同樣地，當按照k2樹的思想把鄰接矩陣進行劃分后，也存在大量的相同的子矩陣.這就造成了k2樹內也存在大量的同構子樹.

2)k2樹僅對稀疏圖有效，當圖變的稠密時，由于鄰接矩陣內可被壓縮的0節點變少，因此k2樹緊湊性也會變低.

3)k2樹未涉及動態圖(需要添加或刪除頂點、邊以及子圖等的圖)的表示與操作[5].

因此，k2樹對上述圖的結構特性尚缺乏必要的考慮，其在緊湊性上仍有較大的改善空間.針對k2樹目前存在的問題，有必要對其進行進一步的優化與改進，以得到一種更為緊湊并且適用面更廣的圖數據的表示方法.為此，本文提出一種基于決策圖的大規模圖數據的表示方法——k2-MDD，該表示方法采用k2樹的思想對鄰接矩陣進行劃分，然后使用多值決策圖進行存儲，使k2樹中大量的同構子樹所造成的冗余節點得到合并，從而達到存儲結構更為緊湊的目的.該k2-MDD的優點主要有4點：

1) 由于采用決策圖結構來存儲圖數據，因此對于劃分鄰接矩陣時產生相同的子矩陣，即k2樹中的同構子樹就自然地被合并了，最終生成的k2-MDD結構將比k2樹緊湊得多.

2)k2-MDD與k2樹所不同的是，它不論是0值還是1值，只要是同構的，都將被合并掉.因此，在表示稠密圖時，k2-MDD節點數反而會變少，結構變得更為緊湊.

3) 當使用決策圖來存儲圖數據后，圖的相關基本操作就可以轉化為符號決策圖的邏輯操作，這就為動態圖數據的高效操作提供了可能性.另外這也使得基于k2-MDD要比基于k2樹的圖的查詢操作更為簡潔.

4) 由于k2-MDD是基于決策圖的結構，根據其本身結構的特性，該結構將更有利于子圖查詢、圖同構、圖子圖匹配以及多圖匹配等方向的研究.

本文以有向無權圖為例，對k2-MDD的表示與操作進行討論.本文提出的結構也可以拓展用于無向圖以及加權圖的存儲與表示.下面給出k2-MDD的表示形式、定義、性質、構造過程以及對于有向圖的基本操作等.

1 有向圖的k2-MDD表示形式

首先給出k2-MDD的定義：

定義1.k2-MDD：圖的鄰接矩陣可以用一個將原始矩陣進行遞歸的k2等分后構造的多值決策圖(multi-valued decision diagram, MDD)[9]結構來表示，這樣的MDD稱之為k2-MDD.

k2-MDD描述了一個帶有n個變量的離散多值函數，f:D1×D2×…×Di×…×Dn→S，其中：

2)Di代表遞歸到第i層時對(子)矩陣的劃分.Di={1,2,…,k2}為所有變量的有限值域，與每次對(子)矩陣劃分得到的k2個子矩陣一一對應；S為多值函數f的有限值域，即k2-MDD終端節點的取值集合，其可能為布爾值(對應無權圖)、有限整數集合或者有限實數集合(對應加權圖).

3)k2-MDD的節點包括終端節點和非終端節點.

4) 非終端節點用xi表示，包含k2個指向其他節點的指針，這些指針和函數f對應，其形式化描述為

fxi=c=f(x1,x2,…,xi-1,c,xi+1,…,xn).

(1)

k2-MDD的圖形化描述如圖1所示：

Fig. 1 Graphical description of k2-MDD.圖1 k2-MDD的圖形化描述

Fig. 2 Reduction rules.圖2 化簡規則

從圖1可以看出，給定多值變量x1到xn的一組取值，可以得到唯一的終端節點取值.

k2-MDD的化簡規則與MDD相同，可以總結為3條：

規則1. 合并相同終端節點.同一屬性的終端節點只保留一個，并刪除其余相同屬性的終端節點，原來指向這些已刪除的終端節點的指針重定向到保留的終端節點上.

規則2. 合并相同內部節點.同一屬性的內部節點(非終端節點)只保留一個，并刪除其余相同屬性的內部節點，原來指向這些已刪除節點的指針重定向到保留的內部節點上.

規則3. 刪除冗余節點.如果一個節點的所有指針都指向同一節點，那么該節點就是冗余節點，需將其刪除，并將指向該節點的指針指向刪除節點的孩子節點.

上述3條化簡規則實例如圖2所示，其中圖2(a)表示多值函數f=xy，x的取值范圍為x∈{1,2,3}，y的取值范圍為y∈{1,2,3}，函數f的值域為集合{0,1,2}.

由k2-MDD的定義可以看出，圖的鄰接矩陣中任一單元均對應于n個變量的唯一一組取值，根據這組取值可以得到唯一函數值，即終端節點的值，并且該值與原始矩陣中對應單元格的元素值相等.

本文以無權圖進行說明，因此函數f的值域取布爾值.對圖中頂點數量等于k的若干次冪和圖中頂點數量不等于k的若干次冪2種典型情況分別進行舉例說明，其中k=2.

例1. 頂點數量等于k的若干次冪.

對于圖3所示的有向圖，其鄰接矩陣如圖4所示,k2樹如圖5所示.顯然，圖5中存在同構子樹，如圖6所示.

Fig. 3 Graph structure.圖3 圖結構

Fig. 4 Adjacency matrix of example 1.圖4 例1的鄰接矩陣

Fig. 8 k2 tree of example 2.圖8 例2的k2樹

Fig. 5 k2 tree of example 1.圖5 例1的k2樹

Fig. 6 Isomorphic subtrees in k2 tree of example 1.圖6 例1的k2樹中的同構子樹

例2. 頂點數量不等于k的若干次冪.

當圖中頂點數量不等于k的若干次冪時，可以通過增加鄰接矩陣的行數和列數(新增的元素全都標記為0)來滿足條件[3].如圖7中的鄰接矩陣，其原始圖中有11個頂點，原始矩陣是11行乘11列的矩陣，通過增加5行5列0數據來使得矩陣可以被k2等分.從k2樹原理及圖8可以知道，這樣增加全部為0的行列對最終生成的k2樹產生的影響非常小.顯然，圖8的k2樹也存在同構子樹，圖9標出了其中一部分.

Fig.7 Adjacency matrix of example 2.圖7 例2的鄰接矩陣

當圖的規模變大時，k2樹中相同的子樹會變得越來越多，另外還有大量的0節點.這種現象在小規模圖中也有體現，比如上述2個例子.

為了減少k2樹中的節點數量，可以將k2樹中的同構子樹進行合并.而這正好是決策圖[10]的優勢.另外，這種合并的過程與MDD化簡過程恰好吻合.對于無權圖，使用布爾型MDD(終點要么是真要么是假)；對于加權圖，使用整數或者實數型MDD(終點是整數或者實數).本文使用無權圖進行說明，MDD中所有變量的有限值域均為{1,2,…,k2}.

Fig. 9 Isomorphic subtrees in k2 tree of example 2.圖9 例2的k2樹中的同構子樹

將上述2個例子的k2樹轉換為MDD后分別如圖10和圖11所示.圖10、圖11中節點內的數字僅代表該節點的索引號，并沒有其他意義，圖10、圖11中左側的數字為圖中節點的層次序號.

從以上2例可以看出，從k2樹轉換為MDD后同構子樹都被合并了，節點數量大大減少.例1從21個節點減少為6個節點，例2從73個節點減少為16個節點.

Fig. 10 The MDD of example 1.圖10 例1的MDD

Fig. 11 The MDD of example 2.圖11 例2的MDD

2 構造k2-MDD的算法過程

構造k2-MDD的過程分為對圖的頂點進行編碼、對邊進行編碼、根據邊的編碼來構造k2-MDD3個步驟，具體如下：

1) 對圖的頂點編碼

Fig. 12 Coding vertexs and coding edges.圖12 頂點編碼和邊編碼

算法1. 對圖的頂點進行編碼.

輸入: 要進行編碼的頂點的編號nodeID；

輸出: 對應該頂點的編碼數組nodeCode[].

①EncodingNode(nodeCode[],nodeID)*將編號為nodeID的頂點編碼并存到數組nodeCode[]中*

②codeNum←CeilingLog_2(nodeNum);*codeNum為編碼長度，nodeNum為頂點數量*

③low←1;

④high←Pow(2,codeNum);*取不小于nodeNum的2的若干次冪*

⑤i←1;

⑥ While (low≤high) Do*二分編碼*

⑦mid←(low+high)2;

⑧ IfnodeID≤midThen

⑨nodeCode[i]←0;

⑩high←mid-1;

2) 對圖的邊編碼

有向邊可理解為頂點之間的關系，頂點v0到頂點v1的邊可用特征函數E(v0,v1)來描述.當k=2時，設X=(x1,x2,…,xn),Y=(y1,y2,…,yn)是圖中頂點的編碼向量，則頂點X到頂點Y邊的特征函數表示為

E(X,Y):{0,1}n×{0,1}n→{1,2,3,4}n,

即每一位上2個頂點的2種狀態會組合出4種狀態.因此，邊的編碼長度依然是n位，每一位是4種狀態之一(1,2,3或4).邊編碼過程的偽代碼如算法2所示.根據該編碼規則對圖3所示圖的邊編碼后如圖12所示.

算法2. 對圖的邊進行編碼.

輸入: 要進行編碼的邊的起止頂點編號nodeFrom和nodeTo；

輸出: 對應該條邊的編碼數組edgeCode[].

①EncodingEdge(edgeCode[],nodeFrom,nodeTo)*根據邊的起止頂點得到邊的編碼*

②EncodingNode(nodeCodeA[],nodeFrom)*對邊的起始頂點進行編碼*

③EncodingNode(nodeCodeB[],nodeTo)*對邊的終止頂點進行編碼*

④ Fori=1 TocodeNumDo*根據起止頂點的編碼來對這條邊進行編碼*

⑤edgeCode[i]←nodeCodeA[i]×2+nodeCodeB[i]+1;

⑥ EndFor

3) 根據邊編碼的集合來構造k2-MDD

根據k2-MDD的定義，我們可以構造一個含有n個變量的k2-MDD，然后令這n個變量的值等于邊編碼集合里的值時，函數值為T，否則為F.這樣就得到了與有向圖G對應的k2-MDD.例如，根據圖12中的邊編碼，可以得到圖的k2-MDD結構如圖10所示.在構造k2-MDD時可以借助MEDDLY(multi-terminal and edge-valued decision diagram library)函數庫[11].MEDDLY函數庫是為操控MDD提供的一個CC++開源項目，由愛荷華州立大學在Linux平臺下開發，其中提供了豐富的MDD構造以及操作的函數.例如：可以使用createVariablesBottomUp()函數來創建將要構造MDD的變量個數以及每個變量的取值范圍；使用createEdge()函數來根據給定的一組或多組變量的值來生成一個MDD；使用apply()函數以及UNION運算符來將2個MDD進行合并.通過MEDDLY函數庫，根據邊編碼我們可以很方便地生成有向圖對應的k2-MDD.構造k2-MDD的偽代碼如算法3所示.

算法3. 構造k2-MDD.

輸入: 圖的所有邊；

輸出: 與輸入圖對應的k2-MDD.

①CreateK2MDD()*根據邊生成k2-MDD*

② Fori=1 TocodeNumDo*設置變量個數以及每個變量的值域*

③Bounds[i]←4;

④ EndFor

⑤createVariablesBottomUp(bounds[],codeNum);*創建變量*

⑥EncodingEdge(edgeCode[],nodeFrom[1],nodeTo[1]);*對第1條邊進行編碼*

⑦createEdge(edgeCode[],1,all);*根據第1條邊的編碼生成一個初始化MDD*

⑧ Fori=2 ToedgeNumDo

⑨EncodingEdge(edgeCode[],nodeFrom[i],nodeTo[i]);*對第i條邊進行編碼*

⑩createEdge(edgeCode[],1,rest);*根據第i條邊編碼生成MDD并存到rest*

3 基于k2-MDD的有向圖的操作

下面給出在k2-MDD存儲結構下有向圖的一些基本操作.

1) 邊查詢

根據邊的起止頂點v1和頂點v2的編號得到該條邊的編號E(v1,v2)，在圖的k2-MDD中檢測E(v1,v2)的函數值.若值為T，則該邊存在，否則不存在.MEDDLY庫中提供的INTERSECTION運算符可以幫我們完成此操作.INTERSECTION用來求2個MDD的交運算.因此，我們只要將原圖的k2-MDD與要查詢的邊生成的k2-MDD進行INTERSECTION運算，查看運算結果是否為空即可.邊查詢的偽代碼如算法4所示.

算法4. 邊查詢算法.

輸入: 要查詢的邊的起止頂點編號nodeFrom和nodeTo；

輸出: 該邊是否存在.

①edgeQuery(nodeFrom,nodeTo)*根據邊的起止頂點查詢圖中是否存在該邊*

②EncodingEdge(edgeCode[],nodeFrom,nodeTo);*對邊進行編碼*

③createEdge(edgeCode[],1,tmp);*生成這條邊的MDD*

④apply(INTERSECTION,K2MDD,tmp,res);*進行交運算，結果存到res中*

⑤ Ifres.getNode()=0 Then*如果結果為空，則邊不存在；否則存在*

⑥Print(不存在);

⑦ Else

⑧Print(存在);

⑨ EndIf

2) 外鄰查詢(包括求出度)

借助邊查詢，將要進行外鄰查詢的頂點賦值為v1，圖中所有頂點依次賦值為v2，檢測E(v1,v2)的函數值.若值為T，則當前v2是一個外鄰點，否則不是.通過統計外鄰點個數可以得到該頂點的出度.

3) 內鄰查詢(包括求入度)

查詢方法與外鄰查詢類似，只不過要查詢的點賦值為v2，圖中所有頂點依次賦值為v1.

4) 增加邊

根據要增加邊的起止頂點v1和v2的編號得到該條邊的編號E(v1,v2)，生成該條邊的k2-MDD;然后與原圖的k2-MDD進行UNION運算，即得到增加了該邊的新圖的k2-MDD.

5) 刪除邊

根據要刪除邊的起止頂點v1和頂點v2的編號得到該條邊的編號E(v1,v2)，生成該條邊的k2-MDD;然后將原圖的k2-MDD與要刪除邊的k2-MDD進行DIFFERENCE運算，即得到刪除了該邊的新圖的k2-MDD.DIFFERENCE是求2個MDD的差運算，執行函數apply(DIFFERENCE,A,B,res)后，res={x|x∈A且x?B}.

根據上述圖的基本操作，可以很方便地拓展到圖的一些復雜操作，比如圖中寬度優先搜索、求最短路、網絡流等.

4 算法復雜度分析

由邊編碼集合構造k2-MDD以及基于k2-MDD的有向圖的添加和刪除邊，由于涉及到MDD的初始化、生成、求交集、求并集及化簡等運算過程，在文獻[9]中已經進行了復雜度分析，這里不再分析.

在構造k2-MDD時，對圖的單個頂點編碼的時間復雜度為O(logk|V|)；同理，對圖的單條邊編碼的時間復雜度也是O(logk|V|)；因此對圖的所有邊進行編碼的時間復雜度即為O(|E|logk|V|).

對于大規模圖數據存儲于操作，在實際應用中，通常評價指標是存儲結果和查詢時間，對于構造時的復雜度一般并不關心.

5 實驗與分析

本文利用MEDDLY庫，采用C++語言實現所提出的算法.實驗用機器配置的軟件平臺為Ubuntu14.04 LTS 64位操作系統(內核Linux 3.19.0-61-generic)，硬件平臺為Intel?CoreTMi5-4690 CPU @ 3.50 GHz處理器，8 GB內存.測試數據采用公開的真實數據集和隨機數據集.真實數據集使得實驗結果具有更好的代表性，隨機數據集可以看出存儲結構在不同規模圖數據下的節點數變化趨勢.

5.1 基于真實數據集的實驗

表1列出了測試中使用的真實網頁圖和社交網絡數據，數據均來自米蘭大學LAW(Laboratory for Web Algorithmics)[12].表1分別給出了這些數據集的頂點數、邊數、頂點數與邊數的比值以及這些數據集在網站的文件名.

Table 1 Description of Testing Real Graphs

在網頁圖中同一個域內的網頁之間的鏈接數比較多，而域之間的鏈接數就比較少，其具備2個特征：

1) 本地性.大多數鏈接都是域內的，它們通常會指向字典序比較靠近的頁面.

2) 相似性.在字典序中鄰近頁面的鄰居集合也是相似的.

而社交網絡圖并不可以直接對其中的節點進行排序，但是也包含著類似于網頁圖體現的特征，例如同一個社區內的好友關系數量比較多，而社區之間的好友關系數量就比較少.

對于這些真實數據集的特性，本文提出的k2-MDD結構正好可以發揮其同構子樹合并的優勢.

針對這些數據集，分別使用k2樹、k2-MDD以及有序二叉決策圖(ordered binary decision diagram, OBDD)[10]共3種方法進行了測試.表2給出了這些數據集在上述3種方法下的實驗結果，表2中的數據為這3種存儲結構的節點數.

Table 2 The Experimental Results

5.2 基于隨機數據集的實驗

除上述真實數據集外，我們隨機生成了11組圖數據，頂點數均為1 000，邊數分別為10 000，100 000，200 000，…，900 000，1 000 000.這些圖中頂點之間的連接關系完全隨機，因此沒有網頁圖和社交網絡的特性.需要說明的是，當邊數為1 000 000時，圖為完全圖.圖13給出了k2樹和k2-MDD在這些隨機數據集上的實驗結果.

Fig. 13 The experimental results of the random graphs.圖13 隨機圖實驗結果

5.3 實驗分析

對于真實數據集，從表2的實驗結果中的數據可得，在選用的4組網頁圖上，k2-MDD的節點數平均僅為k2樹的2.59%；在選用的4組社交網絡上，k2-MDD的節點數平均僅為k2樹的4.51%.可以看出使用k2-MDD結構來存儲圖可以大大減少節點數量，達到了預期效果.另外，還可以看到，OBDD結構在存儲圖時，節點數也比k2樹大大減少，這也體現出了決策圖在節點合并方面的優勢.

對于隨機數據集，從圖13的實驗結果中的數據可以看出，在圖的頂點數不變的情況下，隨著邊數增多，即圖變的越來越稠密，k2樹的節點數在持續增加，而k2-MDD的節點數在圖的邊數達到完全圖的一半之后開始減少.這說明k2樹只適用于稀疏圖，而k2-MDD不僅適用于稀疏圖還適用于稠密圖.因為k2樹只對某節點的指針全部指向0節點的情況進行了合并，所以造成了這樣的結果.

在查詢時間方面，由于邊查詢的時間復雜度與k2樹相同，而同等規模的圖，k2-MDD與k2樹結構的高度也相同，因此查詢時間不相上下.通過對真實數據集和隨機數據集進行實驗驗證也確是如此.因此本文未給出k2-MDD與k2樹在查詢時間方面的數據對比.

6 結束語

本文提出了一種新的圖數據的表示方法——k2-MDD，這種存儲結構的設計跟傳統思想有所區別.k2-MDD把有向圖的鄰接矩陣進行k2劃分后，轉化為多值布爾函數并使用基于MDD的相關邏輯運算對有向圖進行操作.實驗表明：在處理真實數據集時，k2-MDD的節點數比k2樹大大減少，優勢相當明顯；在處理隨機數據集時，k2-MDD不僅適用于稀疏圖，同樣也適用于稠密圖.當存儲結構變得緊湊之后，對于圖的相關計算的復雜度也會相應地變低.文中給出了k2-MDD對圖的邊進行增加與刪除的操作，稍加拓展，即可得到對頂點的添加與刪除以及對子圖的添加與刪除，因此本結構適用于動態圖.圖數據的k2-MDD表示，既具有k2樹表示的緊湊型和查詢的高效性，又能實現符號決策圖表示下圖模式的高效操作，從而實現了描述和計算能力的統一.

[1]Angles R, Gutierrez C. Survey of graph database models[J]. ACM Computing Surveys, 2008, 40(1): 1-39

[2]Robinson I, Webber J, Elfrem E. Graph Databases[M]. Sebastopol, CA: O’Reilly Media Press, 2015

[3]Zhang Yu, Liu Yanbing, Xiong Gang, et al. Survey on succinct representation of graph data[J]. Journal of Software, 2014, 25(9): 1937-1952 (in Chinese)(張宇, 劉燕兵, 熊剛, 等. 圖數據表示與壓縮技術綜述[J]. 軟件學報, 2014, 25(9): 1937-1952)

[4]China Internet Network Information Center. The 37th statistical report on Internet development in China[EB/OL]. 2016[2016-01-31]. http://www.cnnic.net.cn/hlwfzyj/hlwxzbg/hlwtjbg/201601/t20160122_53271.htm (in Chinese)(中國互聯網絡信息中心. 第37次中國互聯網絡發展狀況統計報告[EB/OL]. 2016[2016-01-31]. http://www.cnnic.net.cn/hlwfzyj/hlwxzbg/hlwtjbg/201601/t20160122_53271.htm)

[5]Brisaboa N R, Ladra S, Navarro G.k2-trees for compact Web graph representation[C] //Proc of the 16th Int Symp on String Processing and Information Retrieval. Berlin: Springer, 2009: 18-30

[6]Brisaboa N R, Ladra S, Navarro G. Compact representation of Web graphs with extended functionality[J]. Information Systems, 2014, 39(1): 152-174

[7]Shi Quan, Xiao Yanghua, Lu Yiqi, et al. Towards optimizingk2-tree for large-scale graph storage[J]. Application Research of Computers, 2011, 28(7): 2488-2491 (in Chinese)(施佺, 肖仰華, 魯軼奇, 等. 基于k2樹的大圖存儲優化研究[J]. 計算機應用研究, 2011, 28(7): 2488-2491)

[8]Shi Quan, Xiao Yanghua, Bessis N, et al. Optimizingk2-trees: A case for validating the maturity of network of practices[J]. Computers & Mathematics with Applications, 2012, 63(2): 427-436

[9]Srinivasan A, Ham T, Malik S, et al. Algorithms for discrete function manipulation[C] //Proc of ICCAD-90. Piscataway, NJ: IEEE, 1990: 92-95

[10]Gu Tianlong, Xu Zhoubo. Ordered Binary Decision Diagram and Its Application[M]. Beijing: Science Press, 2009 (in Chinese)(古天龍, 徐周波. 有序二叉決策圖及其應用[M]. 北京: 科學出版社, 2009)

[11]Iowa State University Research Foundation. MEDDLY: Multi-terminal and edge-valued decision diagram library, Version 0.11.486[CP/OL]. 2014[2015-10-02]. http://meddly.sourceforge.net/index.html

[12]Department of Computer Science, University of Milan. Laboratory for Web algorithmics[DB/OL]. 2015[2015-11-01]. http://law.di.unimi.it/datasets.php

Dong Rongsheng, born in 1965. Professor. Senior member of China Computer Federation. His main research interests include protocol engineering and wirless sensor networks.

Zhang Xinkai, born in 1991. Master candidate. His main research interests include graph data representation and symbolic technology.

Liu Huadong, born in 1978. Lecturer. His main research interests include graph data representation and symbolic technology.

Gu Tianlong, born in 1964. PhD, professor, PhD supervisor. Senior member of China Computer Federation. His main research interests include formal method, formal computing and knowledge engineering.

Representation and Operations Research of k2-MDD in Large-Scale Graph Data

Dong Rongsheng, Zhang Xinkai, Liu Huadong, and Gu Tianlong

(Guangxi Key Laboratory of Trusted Software (Guilin University of Electronic Technology), Guilin, Guangxi 541004)

Efficient and compact representation and operation of graph data which contains hundreds of millions of vertices and edges are the basis of analyzing and processing the large scale of graph data. Aiming at the problem, this paper proposes a representation of large-scale graph data based on the decision diagram, that isk2-MDD, providing the initialization ofk2-MDD and the basic operation such as the edge query, inner(outer) neighbor query, finding out(in)-degree, adding(deleting) edge, etc. The representation method is optimized and improved on the basis ofk2tree, and after dividing the adjacency matrix of graph intok2, it is stored with the multi valued decision diagram, so as to achieve a more compact storage structure. According to the experimental results of a series of real Web graph and the social network graph data (cnr-2000, dewiki-2013, etc.) derived from the LAW laboratory at the University of Milan, it can be seen that the number ofk2-MDD’ nodes is only 2.59%-4.51% of thek2tree, which achieving the desired effect. According to the experimental results of random graphs, it can be seen that thek2-MDD structure is not only suitable for sparse graphs, but also for dense graphs. The graph data ofk2-MDD shows that both containing the compact and query efficiency representation ofk2tree and realizing the efficient operation of the graph model can thus achieve the unity of description and computing power.

graph data; storage optimization;k2-MDD;k2tree; decision diagram

2016-08-15；

2016-10-28

國家自然科學基金項目(U1501252,61363070,61572146,61363030)；廣西高等學校高水平創新團隊及卓越學者計劃；桂林電子科技大學創新團隊資助項目 This work was supported by the National Natural Science Foundation of China (U1501252, 61363070, 61572146, 61363030), the High Level Innovation Team of Guangxi Colleges and Universities and Outstanding Scholars Fund, and the Program for Innovative Research Team of Guilin University of Electronic Technology.

古天龍(gu@guet.edu.cn)

TP311