大規(guī)模圖數(shù)據(jù)的k2-MDD表示方法與操作研究

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

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

?

大規(guī)模圖數(shù)據(jù)的k2-MDD表示方法與操作研究

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

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

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

圖數(shù)據(jù)；存儲優(yōu)化；k2-MDD；k2樹；決策圖

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

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

但是，不論是k2樹還是施佺等人優(yōu)化過的k2樹，在對大規(guī)模圖數(shù)據(jù)表示時仍具有一定的局限性，具體表現(xiàn)在3個方面：

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

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

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

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

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

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

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

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

本文以有向無權圖為例，對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個變量的離散多值函數(shù)，f:D1×D2×…×Di×…×Dn→S，其中：

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

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

4) 非終端節(jié)點用xi表示，包含k2個指向其他節(jié)點的指針，這些指針和函數(shù)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 化簡規(guī)則

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

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

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

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

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

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

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

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

例1. 頂點數(shù)量等于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. 頂點數(shù)量不等于k的若干次冪.

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

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

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

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

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

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

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

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的過程分為對圖的頂點進行編碼、對邊進行編碼、根據(jù)邊的編碼來構造k2-MDD3個步驟，具體如下：

1) 對圖的頂點編碼

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

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

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

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

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

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

③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的邊可用特征函數(shù)E(v0,v1)來描述.當k=2時，設X=(x1,x2,…,xn),Y=(y1,y2,…,yn)是圖中頂點的編碼向量，則頂點X到頂點Y邊的特征函數(shù)表示為

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

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

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

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

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

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

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

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

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

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

⑥ EndFor

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

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

算法3. 構造k2-MDD.

輸入: 圖的所有邊；

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

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

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

③Bounds[i]←4;

④ EndFor

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

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

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

⑧ Fori=2 ToedgeNumDo

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

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

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

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

1) 邊查詢

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

算法4. 邊查詢算法.

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

輸出: 該邊是否存在.

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

②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)的函數(shù)值.若值為T，則當前v2是一個外鄰點，否則不是.通過統(tǒng)計外鄰點個數(shù)可以得到該頂點的出度.

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

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

4) 增加邊

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

5) 刪除邊

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

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

4 算法復雜度分析

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

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

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

5 實驗與分析

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

5.1 基于真實數(shù)據(jù)集的實驗

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

Table 1 Description of Testing Real Graphs

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

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

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

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

對于這些真實數(shù)據(jù)集的特性，本文提出的k2-MDD結構正好可以發(fā)揮其同構子樹合并的優(yōu)勢.

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

Table 2 The Experimental Results

5.2 基于隨機數(shù)據(jù)集的實驗

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

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

5.3 實驗分析

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

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

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

6 結束語

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

[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)(張宇, 劉燕兵, 熊剛, 等. 圖數(shù)據(jù)表示與壓縮技術綜述[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)(中國互聯(lián)網絡信息中心. 第37次中國互聯(lián)網絡發(fā)展狀況統(tǒng)計報告[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樹的大圖存儲優(yōu)化研究[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)；廣西高等學校高水平創(chuàng)新團隊及卓越學者計劃；桂林電子科技大學創(chuàng)新團隊資助項目 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