張志遠(yuǎn)，徐恒盼

(中國(guó)民航大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300300)

一種基于倒排索引的多維網(wǎng)絡(luò)存儲(chǔ)模型

張志遠(yuǎn)，徐恒盼

(中國(guó)民航大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300300)

具有多維屬性的實(shí)體相互連接構(gòu)成的網(wǎng)絡(luò)(如社交網(wǎng)絡(luò))稱為多維網(wǎng)絡(luò)，在多維網(wǎng)絡(luò)上支持聯(lián)機(jī)分析處理具有重要的應(yīng)用價(jià)值?，F(xiàn)有方法大都從文件或數(shù)據(jù)庫(kù)中逐條讀取記錄，當(dāng)數(shù)據(jù)量很大時(shí)，需要多次讀取磁盤，導(dǎo)致查詢響應(yīng)時(shí)間過(guò)長(zhǎng)，效率較低。文中提出了一種新的基于倒排索引的多維網(wǎng)絡(luò)存儲(chǔ)模型II-GC(Inverted Index based Graph Cube)，通過(guò)將圖的拓?fù)浣Y(jié)構(gòu)和頂點(diǎn)的多維屬性存儲(chǔ)在倒排索引列表中加快查詢速度，并給出了在多維網(wǎng)絡(luò)上進(jìn)行聚集查詢(cuboid)和交叉查詢(crossboid)的算法。在DBLP數(shù)據(jù)集上的實(shí)驗(yàn)表明，該模型較GraphCube的查詢效率更高，擴(kuò)展性更好。

多維網(wǎng)絡(luò)；圖立方體；倒排索引；聯(lián)機(jī)分析處理

0 引 言

隨著Web2.0等互聯(lián)網(wǎng)新概念的飛速發(fā)展，大量新型社交網(wǎng)絡(luò)服務(wù)不斷涌現(xiàn)，社交網(wǎng)絡(luò)在人們的生活中扮演著越來(lái)越重要的角色。作為一個(gè)交叉領(lǐng)域，社交網(wǎng)絡(luò)研究已經(jīng)得到國(guó)內(nèi)外學(xué)者們的廣泛關(guān)注。目前對(duì)于社交網(wǎng)絡(luò)的研究多集中于其拓?fù)浣Y(jié)構(gòu)，如社區(qū)劃分[1-2]、輿情傳播[3]等。在實(shí)際應(yīng)用中，除拓?fù)浣Y(jié)構(gòu)外，與頂點(diǎn)相關(guān)的多維屬性信息也非常重要，如統(tǒng)計(jì)合著網(wǎng)絡(luò)中的男女比例及連接關(guān)系等。文中主要研究由拓?fù)浣Y(jié)構(gòu)及與頂點(diǎn)關(guān)聯(lián)的多維屬性一起構(gòu)成的多維網(wǎng)絡(luò)[4]。

對(duì)多維網(wǎng)絡(luò)進(jìn)行OLAP[5]分析可展現(xiàn)不同尺度上的網(wǎng)絡(luò)結(jié)構(gòu)特征，如聚集操作可分析合著網(wǎng)絡(luò)中不同領(lǐng)域人員之間的網(wǎng)絡(luò)結(jié)構(gòu)，切片操作可分析某特定領(lǐng)域如數(shù)據(jù)挖掘?qū)W者之間的網(wǎng)絡(luò)關(guān)系。為突破傳統(tǒng)OLAP技術(shù)無(wú)法支持帶有圖結(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò)分析的限制，近年來(lái)研究人員開展了很多相關(guān)研究。2007年吳巍[6]提出了Link OLAP的概念，將面向?qū)嶓w的分析擴(kuò)展為面向連接的分析，以復(fù)雜網(wǎng)絡(luò)可視化為基礎(chǔ)，突破了以往傳統(tǒng)OLAP系統(tǒng)中單調(diào)的二維表格表現(xiàn)方式。同年，Chen等[7]提出了Graph OLAP的概念，將OLAP技術(shù)引入到復(fù)雜網(wǎng)絡(luò)分析中，實(shí)現(xiàn)了在信息維和拓?fù)渚S兩種維度上的OLAP操作。2010年，Li等[8]提出了一種適合Graph OLAP的數(shù)據(jù)倉(cāng)庫(kù)概念模型，即雙星模型，并提出了信息維聚集算法I-OLAPing和拓?fù)渚S聚集算法T-OLAPing。2011年，Li等[9]又在原有基礎(chǔ)上提出了基于信息網(wǎng)絡(luò)數(shù)據(jù)倉(cāng)庫(kù)和信息網(wǎng)絡(luò)數(shù)據(jù)立方體的概念，提出了雙星座數(shù)據(jù)模型，實(shí)現(xiàn)了信息維和拓?fù)渚S的聚集算法以及上卷下鉆的OLAP操作。同年，Zhao等[10]詳細(xì)介紹了一個(gè)新的數(shù)據(jù)倉(cāng)庫(kù)模型，即基于圖的數(shù)據(jù)立方體Graph Cube，同時(shí)提出了用于Graph OLAP的新的查詢方式crossboid(詳見(jiàn)定義4)，并討論了Graph Cube的物化策略。2011年，Qu等[11]提出了一種信息網(wǎng)絡(luò)拓?fù)渚S的框架，并基于此框架提出了更高效的查詢方法以及數(shù)據(jù)立方體的物化策略，對(duì)拓?fù)渚S在線分析處理(T-OLAP)操作中特定類型度量的優(yōu)化進(jìn)行了有針對(duì)性的深入分析。

現(xiàn)有的GraphCube OLAP聚集算法研究大多是直接對(duì)文件或數(shù)據(jù)庫(kù)中的數(shù)據(jù)進(jìn)行聚集查詢，逐條檢索記錄，判斷是否符合條件。當(dāng)文件很大時(shí)，往往要多次讀寫磁盤，較為耗時(shí)。文中提出了一種新的多維網(wǎng)絡(luò)存儲(chǔ)模型II-GC(Inverted Index based Graph Cube)，通過(guò)引入倒排索引技術(shù)，把直接對(duì)數(shù)據(jù)庫(kù)中數(shù)據(jù)進(jìn)行的聚集查詢轉(zhuǎn)化成倒排索引集合間的交、并運(yùn)算，不用逐個(gè)讀取記錄，參與運(yùn)算的數(shù)據(jù)大幅減少，提高了檢索速度。

1 基本概念

定義1：多維網(wǎng)絡(luò)[4,12]。多維網(wǎng)絡(luò)是一個(gè)形式為G=(V,E,A)的圖，其中V是頂點(diǎn)集合，E?V×V是邊的集合，A={A1,A2,…,An}是與頂點(diǎn)相關(guān)聯(lián)的屬性集合。任取v∈V，存在一個(gè)多維元組A(v)=(A1(v),A2(v),…,Am(v))，其中Ai(v)是頂點(diǎn)v上的第i個(gè)屬性，1≤i≤m。

圖1是一個(gè)社交網(wǎng)絡(luò)中的多維網(wǎng)絡(luò)示例。圖中有10個(gè)頂點(diǎn)，記作v1,v2,…,v10，分別代表社交網(wǎng)絡(luò)中不同的個(gè)體；13條邊分別代表個(gè)體間的關(guān)系。每個(gè)頂點(diǎn)均關(guān)聯(lián)一個(gè)多維屬性元組，記錄該個(gè)體的基本信息，包括ID，Gender，Location及Profession。所有頂點(diǎn)的多維屬性元組集合構(gòu)成多維屬性表，如表1所示。

圖1 一個(gè)社交網(wǎng)絡(luò)的多維網(wǎng)絡(luò)圖

表1 多維屬性表

(2)?u',v'∈V'，其中u'代表[u]，v'代表[v]，令E(u',v')={(u,v)|u∈[u],v∈[v],(u,v)∈E}，若E(u',v')非空，則?e'∈E代表E(u',v')。邊的權(quán)重ω(e')=Fe(E[u',v'])，其中Fe()為作用在邊上的聚集函數(shù)，稱e'為聚集邊。

以圖1中的“社交網(wǎng)絡(luò)”為例，選取A的一種聚集A'=(Gender，*，*)，以Count()作為頂點(diǎn)和邊上的聚集函數(shù)，則產(chǎn)生的聚集網(wǎng)絡(luò)含Male和Female兩個(gè)聚集頂點(diǎn)，其權(quán)重值分別為男女實(shí)例的個(gè)數(shù)，本例中均為5。邊的權(quán)重代表聚集頂點(diǎn)間的關(guān)系，如Female頂點(diǎn)集合{v2,v3,v4,v6,v9}中有三條邊連接，即v2v4,v3v4,v3v6，因此其權(quán)重為3。

定義3：圖立方體[10]。給定多維網(wǎng)絡(luò)(V,E,A)，根據(jù)A的所有可能的聚集產(chǎn)生的聚集網(wǎng)絡(luò)集合構(gòu)成圖立方體(GraphCube，GC)，其每個(gè)聚集網(wǎng)絡(luò)又被稱為cuboid。

仍以圖1中的社交網(wǎng)絡(luò)為例，頂點(diǎn)代表在不同的聚集屬性下得到的聚集網(wǎng)絡(luò)，邊代表不同的聚集網(wǎng)絡(luò)間的父子關(guān)系，其中(Gender，Location，Profession)是所有其他聚集網(wǎng)絡(luò)的基礎(chǔ)，(*，Location，Profession),(Gender，*，Profession)及(Gender，Location，*)均可從(Gender，Location，Profession)直接求得。

圖2 crossboid查詢產(chǎn)生的聚集網(wǎng)絡(luò)

2 II-GC存儲(chǔ)模型

多維網(wǎng)絡(luò)可看作是具有多維屬性頂點(diǎn)的網(wǎng)絡(luò)圖，節(jié)點(diǎn)的屬性信息可存儲(chǔ)在其data域中，也可像表1一樣將所有頂點(diǎn)信息存儲(chǔ)在一個(gè)二維表格中。在進(jìn)行聚集操作時(shí)，兩種方式均需要對(duì)圖進(jìn)行遍歷，時(shí)間復(fù)雜度為O(n+e)。其中，n是頂點(diǎn)個(gè)數(shù)，e是邊的條數(shù)。隨著網(wǎng)絡(luò)規(guī)模的增加，這種線性復(fù)雜度甚至都是不能忍受的。為此文中提出基于倒排索引的多維網(wǎng)絡(luò)存儲(chǔ)模型，將所有信息存儲(chǔ)在頂點(diǎn)的倒排索引和邊的倒排索引中，如圖3所示。

圖3 基于倒排索引的多維網(wǎng)絡(luò)存儲(chǔ)模型

按照廣度優(yōu)先的遍歷順序?qū)c(diǎn)和邊進(jìn)行編號(hào)，2.1節(jié)中討論了這種編號(hào)方式帶來(lái)的好處。邊的倒排索引按起點(diǎn)和終點(diǎn)分為兩組，對(duì)如圖1所示的無(wú)向圖，以數(shù)字較小的頂點(diǎn)為起點(diǎn)。例如邊起點(diǎn)倒排索引中的Male：1,2,11,12表明有四條邊的起點(diǎn)中Gender屬性為Male。起點(diǎn)倒排索引中的Male和終點(diǎn)倒排索引中的Male交集只含有11這一條邊，因此可以確定Male和Male之間的連接邊只有一條，正好回答了Male自身連接權(quán)重的問(wèn)題。采用基于倒排索引的存儲(chǔ)模型至少有以下幾個(gè)優(yōu)點(diǎn)：

(1)將圖遍歷轉(zhuǎn)換為集合的交并操作，加快了查詢速度；

(2)采用倒排索引壓縮算法可進(jìn)一步減少存儲(chǔ)空間；

(3)相對(duì)于結(jié)構(gòu)復(fù)雜的圖來(lái)說(shuō)，基于倒排索引的查詢更容易并行化。

2.1 模型初始化

將多維網(wǎng)絡(luò)轉(zhuǎn)換為基于倒排索引的存儲(chǔ)模型，初始化算法如下：

輸入：一個(gè)多維網(wǎng)絡(luò)G=(V,E,A)；

輸出：點(diǎn)倒排索引表N，邊倒排索引表E1,E2，邊編號(hào)索引表EI。

begin

//按廣度優(yōu)先順序?qū)D節(jié)點(diǎn)編號(hào)

初始化隊(duì)列Q，并將v1加入Q;

nodeno←0;設(shè)置所有節(jié)點(diǎn)為未訪問(wèn);

whileQ非空{(diào)

從隊(duì)列中取出一個(gè)頂點(diǎn)u并標(biāo)記為已訪問(wèn);

u.id=++nodeno;

foru的每個(gè)未訪問(wèn)過(guò)的鄰居節(jié)點(diǎn)v{

ifv不在Q中則將其加入隊(duì)列Q;

}

}

//對(duì)圖廣度優(yōu)先遍歷并設(shè)置倒排索引表

初始化隊(duì)列Q，并將v1加入Q;

edgeno←0;設(shè)置所有節(jié)點(diǎn)為未訪問(wèn);

whileQ非空{(diào)

從隊(duì)列中取出一個(gè)頂點(diǎn)u并標(biāo)記u為已訪問(wèn);

for除id外的每一個(gè)屬性Ai{

N(Ai(u))←N(Ai(u))∪{u.id}；

}

foru的每個(gè)未訪問(wèn)過(guò)的鄰居節(jié)點(diǎn)v{

EI[++edgeno]←(u.id,v.id);

for除id外每一個(gè)屬性Ai{

E1(Ai(u))←E1(Ai(u))∪{edgeno};

E2(Ai(u))←E2(Ai(v))∪{edgeno};

}

ifv不在Q中則將其加入隊(duì)列Q;

}

}

end

按廣度優(yōu)先順序?qū)D節(jié)點(diǎn)和邊進(jìn)行編號(hào)，這樣可保證點(diǎn)和邊的倒排索引列表按升序排列，為后面的求交操作帶來(lái)便利。算法相當(dāng)于對(duì)原圖進(jìn)行了兩次廣度優(yōu)先遍歷，其時(shí)間復(fù)雜度亦為O(2n+2e)。采用倒排索引格式存儲(chǔ)后，原多維網(wǎng)絡(luò)不必繼續(xù)保留。若采用的聚集函數(shù)為Count()，則邊編號(hào)索引表EI也可以去掉。由于倒排索引存儲(chǔ)的均為整數(shù)，和原來(lái)使用大量字符串相比存儲(chǔ)空間有所減少。需要注意的是，該存儲(chǔ)模型對(duì)類別較多的列屬性(如姓名)而言是低效的，因?yàn)檫@會(huì)造成大量的短倒排索引列表，不利于后面的查詢操作。

2.2 cuboid查詢

以聚集A'=(Gender,*,*)為例，Gender對(duì)應(yīng)的屬性值有Male和Female，查看相應(yīng)的點(diǎn)倒排索引表N得：N(Female)={2,3,4,6,9}，N(Male)={1,5,7,8,10}。說(shuō)明Female和Male分別有5人。然后再查他們之間的連接關(guān)系得：E1(Male)={1,2,11,12}，E2(Male)={5,7,8,9,10,11,13}。兩者的交集為{11}，說(shuō)明以Male為起點(diǎn)和終點(diǎn)的邊只有1條。同理可得E1(Female)∩E2(Female)={3,4,6}，說(shuō)明以Female為起點(diǎn)和終點(diǎn)的邊共有3條。連接Male和Female之間的邊或者以Male為起點(diǎn)，或者以Female為起點(diǎn)，對(duì)應(yīng)的集合為{E1(Male)∩E2(Female)}∪ {E1(Female)∩E2(Male)}={1,2,5,7,8,9,10,12,13}，說(shuō)明Male和Female之間有9條邊。Cuboid查詢算法如下：

輸入：倒排索引多維網(wǎng)絡(luò)IIG=(N，E1，E2，EI)，聚集屬性A'；

begin

V'←?;E'←?;

//計(jì)算所有可能的聚集頂點(diǎn)

Vt1←?;Vt2←?;

ifV'為空集{V'←Vt1;continue;}

forV'的每一個(gè)元素v'{

forVt1的每一個(gè)元素vt1{

Vt2←Vt2∪{v',vt1};

}}

V'←Vt2;Vt1←?;Vt2←?;

}

//計(jì)算頂點(diǎn)的權(quán)重

if(T==?){將v'從V'中刪除;continue;}

}

//計(jì)算邊的權(quán)重

forV'的每一個(gè)頂點(diǎn)對(duì)(u',v'){

if(u'≠v'){

e←e∪e';

}

if(e≠?) {

{E'←E'∪{(u',v')};

}

}

end

設(shè)cuboid聚集網(wǎng)絡(luò)有m個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)有k個(gè)分量(如Male,Professor)，則算法最多需要2m2k+mk次求交集操作，而實(shí)際上會(huì)小得多，因?yàn)榍蠼患瘯r(shí)集合大小隨著次數(shù)的增加將明顯變小，當(dāng)結(jié)果為空時(shí)即可停止。

2.3 crossboid查詢

以(Gender，*，*)和(*，Location，*)為例，對(duì)兩個(gè)聚集屬性依次應(yīng)用2.2中算法的前兩步得6個(gè)聚集節(jié)點(diǎn)：Male(5)，F(xiàn)emale(5)，CA(3)，WA(3)，NY(2)，IL(2)。其中括號(hào)內(nèi)的值為點(diǎn)的權(quán)重。然后應(yīng)用邊倒排索引查詢連接邊，例如Male和CA之間的連接為：(E1(Male)∩E2(CA))∪(E1(CA)∩E2(Male))=([1,2,11,12]∩[2,12])∪([1,2,4,5,6,7,8,13]∩[5,7,8,9,10,11,13])=[2,5,7,8,12,13]。因此Male和CA之間的連接權(quán)重為6。crossboid查詢算法如下：

//求S和T的連接邊及權(quán)重

e←e∪e'；

if(e≠?) {

E'←E'∪{(u',v')};

}

}

}

2.4 雙二分查找

倒排索引源于實(shí)際應(yīng)用中需要根據(jù)屬性的值來(lái)查找記錄。這種索引表中的每一項(xiàng)都包括一個(gè)屬性值和具有該屬性值的各記錄的地址。由于不是由記錄來(lái)確定屬性值，而是由屬性值來(lái)確定記錄的位置，因而稱為倒排索引。利用倒排索引查詢的時(shí)間復(fù)雜度主要取決于集合求交的過(guò)程，注意到所有的倒排索引列表都是升序排列的，可以采用雙二分查找算法[13]提高查找速度。對(duì)于兩個(gè)有序集合D和Q，假設(shè)D比Q的元素多。該算法首先在D中對(duì)Q的中間值Qmid進(jìn)行二分查找，若找到則將Qmid添加至結(jié)果集R中。無(wú)論是否找到，都可以將D和Q劃分為兩個(gè)部分：D1，D2以及Q1，Q2。其中D1和Q1中的所有元素都小于Qmid，D2和Q2中的所有元素都大于Qmid。如此，問(wèn)題轉(zhuǎn)換為求D1和Q1的交集及D2和Q2的交集。實(shí)際過(guò)程中可先比較兩個(gè)集合的最大最小值判斷其交叉重疊部分，從而減少比較集合的大小。Ricardo指出，當(dāng)兩個(gè)集合的元素個(gè)數(shù)相差較大時(shí)，該算法的復(fù)雜度為O(mlg(n))。其中m和n分別為短集合和長(zhǎng)集合的元素個(gè)數(shù)[14]。由于需要進(jìn)行多次求交運(yùn)算，結(jié)果集合肯定會(huì)越來(lái)越短，因此適合采用雙二分查找。

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

3.1 實(shí)驗(yàn)數(shù)據(jù)集

從1969年到2014年的DBLP數(shù)據(jù)集中選取四個(gè)領(lǐng)域的會(huì)議文章共289 135篇，按作者統(tǒng)計(jì)文章發(fā)表情況建立了合著關(guān)系網(wǎng)絡(luò)，含34 259個(gè)作者作為頂點(diǎn)，193 902個(gè)作者之間的合作關(guān)系為邊。頂點(diǎn)屬性信息為Author、Area、Year、Productive。共包含4個(gè)Area，每個(gè)Area選取5個(gè)代表性會(huì)議：數(shù)據(jù)庫(kù)(SIGMOD，VLDB，ICDE，PODS，EDBT)、數(shù)據(jù)挖掘(KDD，ICDM，SDM，PKDD，PAKDD)、信息檢索(SIGIR，WWW，CIKM，ECIR，WSDM)和人工智能(IJCAI，AAAI，ICML，CVPR，ECML)。若作者在多個(gè)領(lǐng)域發(fā)表文章，選擇文章數(shù)量最多的領(lǐng)域?yàn)槠銩rea。Productive根據(jù)作者發(fā)表的文章篇數(shù)分為四個(gè)類別：excellent(35篇以上)、good(15到34篇)、fair(3到14篇)以及poor(小于3篇)。

3.2 cuboid查詢實(shí)驗(yàn)

本小節(jié)對(duì)比II-GC和GraphCube[10]的cuboid查詢?cè)诓煌?guī)模多維網(wǎng)絡(luò)上的響應(yīng)時(shí)間。網(wǎng)絡(luò)邊數(shù)從1萬(wàn)到6萬(wàn)變化時(shí)的cuboid查詢響應(yīng)時(shí)間對(duì)比如圖4所示。

圖4 不同規(guī)模網(wǎng)絡(luò)上的cuboid查詢對(duì)比

可以看出，II-GC比GraphCube上的cuboid查詢響應(yīng)時(shí)間短，且隨著復(fù)雜網(wǎng)絡(luò)邊數(shù)的增加，II-GC的查詢響應(yīng)時(shí)間變化不大，而GraphCube的查詢時(shí)間則迅速增加。

聚集維度從1到3變化時(shí)，兩者的cuboid查詢響應(yīng)時(shí)間對(duì)比如圖5所示。

圖5 不同維數(shù)上的cuboid查詢對(duì)比

可以看出，II-GC的cuboid查詢響應(yīng)時(shí)間更短，且隨著維數(shù)的增加，II-GC的查詢響應(yīng)時(shí)間呈線性增長(zhǎng)，而GraphCube則迅速增加。

實(shí)驗(yàn)結(jié)果驗(yàn)證了基于II-GC處理cuboid查詢的高效性。

3.3 crossboid查詢實(shí)驗(yàn)

本小節(jié)對(duì)比II-GC和GraphCube的crossboid查詢響應(yīng)時(shí)間。在不同規(guī)模網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果如圖6所示。

圖6 不同規(guī)模網(wǎng)絡(luò)上的crossboid查詢對(duì)比

可以看出，在II-GC的crossboid查詢性能較優(yōu)，且隨著網(wǎng)絡(luò)規(guī)模增大，GraphCube上的crossboid查詢響應(yīng)時(shí)間呈直線上升，而II-GC的變化則較為平緩。實(shí)驗(yàn)結(jié)果驗(yàn)證了基于II-GC處理crossboid查詢的高效性。

4 結(jié)束語(yǔ)

基于倒排索引的多維網(wǎng)絡(luò)存儲(chǔ)模型將逐條對(duì)比的查詢操作轉(zhuǎn)換為有序集合的交并操作，在減小存儲(chǔ)空間的同時(shí)優(yōu)化了查詢性能。在DBLP數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，該模型擴(kuò)展性較好，查詢效率較高。當(dāng)屬性值的分類個(gè)數(shù)較多時(shí)，會(huì)出現(xiàn)大量短倒排索引，影響查詢效率。

[1] 程學(xué)旗,沈華偉.復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué),2011,8(1):57-70.

[2] 張 娜.復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分算法研究[D].大連:大連理工大學(xué),2009.

[3] 陳 旭.基于社會(huì)網(wǎng)絡(luò)的WEB輿情系統(tǒng)的研究與實(shí)現(xiàn)[D].西安:西安電子科技大學(xué),2010.

[4] 張?zhí)m華.復(fù)雜網(wǎng)絡(luò)建模的仿真與應(yīng)用研究[D].大連:大連理工大學(xué),2013.

[5] Han Jiawei, Sun Yizhou. Mining heterogeneous information networks[C]//Proc of the 16th ACM SIGKDD international conference on knowledge discovery and data mining.[s.l.]:ACM,2013.

[6] 吳 巍.復(fù)雜網(wǎng)絡(luò)可視化與Link OLAP[D].北京:北京郵電大學(xué),2007．

[7] Chen Chen, Yan Xifeng, Zhu Feida,et al. Graph OLAP:a multi-dimensional framework for graph data analysis[J].Knowledge and Information Systems,2009,21(1):41-63.

[8] Li Chuan,Zhao Lei,Tang Jie,et al.Modeling,design and implementation of graph olaping[J].Journal of Software,2011,22(2):258-268.

[9] Li Chuan,Yu P S,Zhao Lei,et al.InfoNetOLAPer:integrating InfoNetWarehouse and InfoNetCube with InfoNetOLAP[J].Proceedings of the VLDB Endowment,2011,4(12):1422-1425.

[10] Zhao Peixiang,Li Xiaolei,Xin Dong,et al.Graph cube:on warehousing and OLAP multidimensional networks[C]//Proc of ACM SIGMOD international conference on management of data.[s.1.]:ACM Press,2011:853-864.

[11] Qu Qiang,Zhu Feida,Yan Xifeng,et al.Efficient topological OLAP on information networks[C]//Proc of the 16th international conference on database systems for advanced applications.Berlin:Springer-Verlag,2011:389-403.

[12] 邵連龍,尹 沐.基于DBLP的多維異質(zhì)網(wǎng)絡(luò)Graph Cube設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用研究,2014,31(3):720-724.

[13] Baeza-Yates R.Experimental analysis of a fast intersection algorithm for sorted sequences[C]//Proceedings of the 12th international conference on string processing and information retrieval.[s.l.]:[s.n.],2005:13-24.

[14] Baeza-Yates R.A fast set intersection algorithm for sorted sequences[C]//Proceedings of the 15th annual symposium on combinatorial pattern matching.[s.l.]:[s.n.],2004:400-408.

A Multi-dimensional Network Storage Model Based on Inverted Index

ZHANG Zhi-yuan，XU Heng-pan

(School of Computer Science & Technology,Civil Aviation University of China, Tianjin 300300,China)

A network such as social network linked by entities with multiple attributes is called multi-dimensional network.OLAP query on multi-dimensional network has an important application value.Most existing methods read records one by one from a file or a database.When a lot of data involved,these methods need more I/O time,thus leading to large query response time and low query efficiency.A new multi-dimensional network storage model based on inverted index is presented,called II-GC (Inverted Index based Graph Cube).It speeds up the process by constructing inverted index both on topological graph and multiple attributes.Algorithms about cuboid and crossboid are also introduced.Experimental results on DBLP show that this model is more efficient and scalable than GraphCube.

multi-dimensional network;graph cube;inverted index;OLAP

2015-07-15

2015-10-21

時(shí)間：2016-03-22

國(guó)家自然科學(xué)基金資助項(xiàng)目(61201414,61301245,U1233113)

張志遠(yuǎn)(1978-)，男，副教授，碩士研究生導(dǎo)師，研究方向?yàn)閿?shù)據(jù)挖掘；徐恒盼(1987-)，女，碩士研究生，研究方向?yàn)閿?shù)據(jù)倉(cāng)庫(kù)技術(shù)。

http://www.cnki.net/kcms/detail/61.1450.TP.20160322.1521.070.html

TP391.9

A

1673-629X(2016)04-0025-06

10.3969/j.issn.1673-629X.2016.04.006