高圣巍,彭 超

(華東師范大學(xué)軟件學(xué)院,上海200062)

一種改進(jìn)的鄰接關(guān)系可查詢壓縮算法

高圣巍,彭 超

(華東師范大學(xué)軟件學(xué)院,上海200062)

目前多數(shù)數(shù)據(jù)壓縮算法不能直接在壓縮結(jié)果上進(jìn)行數(shù)據(jù)查詢,大數(shù)據(jù)的線性化壓縮算法雖然可直接在壓縮后的數(shù)據(jù)上進(jìn)行鄰接關(guān)系查詢,但壓縮率較低。針對(duì)該問(wèn)題,對(duì)線性化壓縮的實(shí)現(xiàn)原理進(jìn)行研究,分析MPk線性化算法在不同社會(huì)網(wǎng)絡(luò)樣本下的壓縮效率,發(fā)現(xiàn)線性化壓縮結(jié)果中存在冗余信息,并針對(duì)該情況設(shè)計(jì)改進(jìn)算法,刪去原有數(shù)據(jù)結(jié)構(gòu)中的冗余部分,進(jìn)一步提高壓縮率。實(shí)驗(yàn)結(jié)果證明,改進(jìn)算法的時(shí)間復(fù)雜度與原算法相同,壓縮率平均提升23%。

線性化壓縮算法;大數(shù)據(jù);社會(huì)網(wǎng)絡(luò);啟發(fā)式算法;Eulerian數(shù)據(jù)結(jié)構(gòu)

1 概述

近些年來(lái),由于在生物、天文、經(jīng)濟(jì)和社會(huì)網(wǎng)絡(luò)等諸多領(lǐng)域的應(yīng)用,超大規(guī)模復(fù)雜圖的相關(guān)研究受到廣泛重視。這當(dāng)中社會(huì)網(wǎng)絡(luò)尤為突出,其能幫助人們發(fā)現(xiàn)潛在問(wèn)題,做出決策,管理人際關(guān)系、組織機(jī)構(gòu)乃至國(guó)家社會(huì)。社會(huì)網(wǎng)絡(luò)通常被建模為超大圖,成員對(duì)應(yīng)圖的節(jié)點(diǎn),而成員間的關(guān)系則為圖的邊。這些關(guān)系可以是友誼、血緣、貿(mào)易或沖突等,是研究的重點(diǎn)對(duì)象。因此,在分析社會(huì)網(wǎng)絡(luò)時(shí),查詢鄰居節(jié)點(diǎn)是最頻繁也最重要的工作之一[1]。

社會(huì)網(wǎng)絡(luò)一般都由上百萬(wàn)的節(jié)點(diǎn)和邊組成,存儲(chǔ)社會(huì)網(wǎng)絡(luò)需要很大的空間。問(wèn)題也隨之而來(lái):如何壓縮網(wǎng)絡(luò)數(shù)據(jù)以節(jié)省空間?好的算法會(huì)利用社會(huì)網(wǎng)絡(luò)的一些特性來(lái)獲得高壓縮率,比如節(jié)點(diǎn)通常會(huì)以簇的形式出現(xiàn)在社會(huì)網(wǎng)絡(luò)中。在以往,人們?cè)诓樵兩鐣?huì)網(wǎng)絡(luò)時(shí),都會(huì)將其圖數(shù)據(jù)解壓縮。如果查詢操作能直接在壓縮數(shù)據(jù)上進(jìn)行,將可以大量節(jié)省解壓縮的時(shí)間。本文利用線性化壓縮的特性,提出一種改進(jìn)的線性化壓縮算法。該算法不需要解壓即可查詢,通過(guò)計(jì)算節(jié)點(diǎn)間的關(guān)聯(lián)度,調(diào)整節(jié)點(diǎn)在壓縮結(jié)果中的排放位置,從而提高線性化壓縮的壓縮率。

2 相關(guān)研究

在大規(guī)模復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)的壓縮方面,國(guó)內(nèi)外已經(jīng)有一些相關(guān)研究工作。例如:文獻(xiàn)[2]將壓縮問(wèn)題轉(zhuǎn)化為在有向圖中尋找最小生成樹(shù)的過(guò)程;文獻(xiàn)[3]通過(guò)廣度優(yōu)先遍歷的方法壓縮圖,并優(yōu)化了壓縮圖的編碼方式;文獻(xiàn)[4]介紹了幾種常用無(wú)損數(shù)據(jù)壓縮算法。

針對(duì)海量社會(huì)網(wǎng)絡(luò)數(shù)據(jù),要獲得高壓縮率,首先,圖中頂點(diǎn)出現(xiàn)的順序十分重要,文獻(xiàn)[5]說(shuō)明了節(jié)點(diǎn)的排列對(duì)壓縮實(shí)際帶來(lái)的影響。其次,設(shè)計(jì)良好的數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)數(shù)據(jù)十分重要。文獻(xiàn)[6-7]中總結(jié)了一些壓縮社會(huì)圖的方法,主要有記錄鄰接表、記錄間距、引用壓縮和差量壓縮,并且設(shè)計(jì)了通用的圖壓縮框架。在后續(xù)的工作中,Paolo Boldi采用Task Decomposition技術(shù)[8],將壓縮框架擴(kuò)展為在多核架構(gòu)上運(yùn)行,提高壓縮速度。文獻(xiàn)[9]分析了社會(huì)網(wǎng)絡(luò)不同于普通圖的特性,提出通過(guò)找出具有相似鄰居的節(jié)點(diǎn)進(jìn)行壓縮的方法。這些壓縮方法都有著較好的壓縮率,但在社會(huì)網(wǎng)絡(luò)上做查詢操作前,都要先將壓縮的圖解壓。

文獻(xiàn)[10]提出了一種“線性化”技術(shù),這種技術(shù)將社會(huì)網(wǎng)絡(luò)中的節(jié)點(diǎn)表示成一個(gè)序列,序列中的每個(gè)節(jié)點(diǎn)僅存儲(chǔ)序列中相鄰節(jié)點(diǎn)的鄰居關(guān)系,雖然這樣壓縮率與其他壓縮算法稍有降低,但這種技術(shù)使得查詢可以直接在壓縮后的結(jié)果上進(jìn)行。尋找這樣一種序列基本上被認(rèn)為是NP完全的問(wèn)題,因此一般來(lái)說(shuō)不存在有效的多項(xiàng)式時(shí)間算法,文獻(xiàn)[11]對(duì)此作了闡述。

本文對(duì)線性化壓縮的實(shí)現(xiàn)原理進(jìn)行研究,分析線性化方法在不同社會(huì)網(wǎng)絡(luò)樣本下的壓縮效率,發(fā)現(xiàn)線性化壓縮結(jié)果中存在的冗余信息,并針對(duì)該情況提出一種改進(jìn)算法。

3 MPK線性化算法

一個(gè)社會(huì)網(wǎng)絡(luò)可以用一個(gè)有向圖G(V,E)表示,其中,V表示圖中點(diǎn)的集合;E表示圖中邊的集合,即E∈V×V,本文假定網(wǎng)絡(luò)是簡(jiǎn)單的(即沒(méi)有自環(huán)),源節(jié)點(diǎn)到目的節(jié)點(diǎn)最多只有一條邊。有向圖的邊用e=(u,v)表示,其中,u為源節(jié)點(diǎn);v為目的節(jié)點(diǎn),且(u,v)≠(v,u)。圖1是一個(gè)有向圖示例。

圖1 有向圖G

定義有向圖對(duì)應(yīng)的無(wú)向圖,無(wú)向圖存在邊,當(dāng)且僅當(dāng)(u,v)∈E(G)或(v,u)∈E(G)。圖2是圖1中有向圖G對(duì)應(yīng)的無(wú)向圖。

圖2 G對(duì)應(yīng)的無(wú)向圖

定義有向圖對(duì)應(yīng)的轉(zhuǎn)置圖GT,轉(zhuǎn)置圖存在邊(u,v)∈E(GT),當(dāng)且僅當(dāng)(v,u)∈E(G)。

對(duì)有向圖G的查詢分為2種:查詢節(jié)點(diǎn)u指向的所有鄰點(diǎn){v|(u,v)∈G};查詢所有指向節(jié)點(diǎn)u的鄰點(diǎn){v|(v,u)∈G}。為有效支持這2種查詢,多數(shù)壓縮算法需要存儲(chǔ)圖G和轉(zhuǎn)置圖GT。而線性化算法將圖G進(jìn)行編碼,節(jié)省了大量的空間,同時(shí)支持在已編碼的結(jié)果上直接作查詢。下文將給出MPk的定義和用 MPk于存儲(chǔ)圖G的編碼的數(shù)據(jù)結(jié)構(gòu)——Eulerian結(jié)構(gòu)。

3.1 MPk線性化定義

定義1設(shè)S=(vi1,vi2,…,vim)是由圖G的節(jié)點(diǎn)組成的序列,如果G中所有的節(jié)點(diǎn)在S中至少出現(xiàn)一次,則稱S覆蓋了圖G,這里請(qǐng)注意S中前后相鄰出現(xiàn)的點(diǎn)不一定在G中存在鄰接邊。

定義2給定一個(gè)覆蓋圖G的序列S,dist(u,v)表示序列S中節(jié)點(diǎn)u和節(jié)點(diǎn)v最相近的距離。

定義3給定一個(gè)覆蓋圖G的序列S,如果對(duì)于圖G中所有的邊(u,v)∈E(G),在S中都有dist(u,v)≤k,則稱S是圖G的MPk階線性化序列。圖G中的節(jié)點(diǎn)允許在S中重復(fù)出現(xiàn)。

3.2 Eulerian數(shù)據(jù)結(jié)構(gòu)

Eulerian數(shù)據(jù)結(jié)構(gòu)用來(lái)保存對(duì)圖G的MP線性化序列L,它是一個(gè)數(shù)組,L的長(zhǎng)度用|L|表示,設(shè)v(i)是出現(xiàn)在數(shù)組第i個(gè)位置的節(jié)點(diǎn),v(i)保存2個(gè)信息:

(1)鄰居信息:對(duì)于MP1線性化序列,鄰居信息占2 bit,分別記錄有向邊(v(i),v(i+1))和(v(i+1),v(i))是否屬于E(G)。對(duì)于MPk線性化,每個(gè)元素需要一個(gè)2kbit的比特串保存鄰居信息,其中,第2j-1個(gè)和第2j個(gè)比特分別記錄有向邊(v(i),v(i+j))和(v(i+j),v(i))是否屬于E(G)。

(2)節(jié)點(diǎn)指針:同一節(jié)點(diǎn)在序列中允許重復(fù)出現(xiàn)。節(jié)點(diǎn)指針指向節(jié)點(diǎn)下一次出現(xiàn)的位置。節(jié)點(diǎn)最后一次出現(xiàn)時(shí),節(jié)點(diǎn)指針指向它首次出現(xiàn)的位置。

圖G的MP1和MP1線性化序列的Eulerian表示如圖3和圖4所示。

圖3 圖G的MP1線性化序列的Eulerian表示

圖4 圖G的MP2線性化序列的Eulerian表示

4 MPk線性化的改進(jìn)

4.1 Eulerian數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)冗余

在稀疏圖中,節(jié)點(diǎn)的出入度都較小,在k比較大的情況下進(jìn)行MPk壓縮,會(huì)導(dǎo)致Eulerian數(shù)據(jù)結(jié)構(gòu)中的鄰居信息存儲(chǔ)著大量的不連續(xù)的0 bit(表示節(jié)點(diǎn)之間沒(méi)有邊相連)。假設(shè)圖G的MPk序列的某一段如下排列:a,u1,v1,u2,v2,…,uk/2,vk/2,其中,,則節(jié)點(diǎn)a的鄰居信息表示為:001100110011…(共2kbit)。如果變換節(jié)點(diǎn)出現(xiàn)的順序?yàn)閍,u1,u2,…,uk/2,v1,v2,vk/2,同時(shí)保證序列仍然符合MPk的定義,則節(jié)點(diǎn)a的鄰居信息變?yōu)?0000…01111…1(0 bit與1 bit各k個(gè)),可以省去開(kāi)始的k個(gè)0 bit,從第1個(gè)1 bit開(kāi)始記錄鄰居信息。由于鄰居信息的長(zhǎng)度不再固定為2k,因此需要增加lbk個(gè)比特記錄鄰居信息的比特串長(zhǎng)度。通常lbk遠(yuǎn)小于k,所以,整體壓縮率仍然是提高的。

改進(jìn)的Eulerian數(shù)據(jù)結(jié)構(gòu)除了保存圖G的節(jié)點(diǎn)外,還保存著一個(gè)二元組(NI,δN),其中,δN表示鄰居信息比特串的長(zhǎng)度;NI表示鄰居信息。

4.2 改進(jìn)的MPk線性化算法

本文通過(guò)算法調(diào)整序列中節(jié)點(diǎn)出現(xiàn)的順序。用數(shù)組L來(lái)記錄線性化序列中的節(jié)點(diǎn),初始時(shí)L長(zhǎng)度為0,此時(shí)隨機(jī)選擇一個(gè)節(jié)點(diǎn)加入到L。當(dāng)向L加入新節(jié)點(diǎn)時(shí),計(jì)算每個(gè)候選節(jié)點(diǎn)u與L中最后k個(gè)節(jié)點(diǎn)的關(guān)聯(lián)度,稱之為權(quán)值。設(shè)當(dāng)前L的長(zhǎng)度為|L|,權(quán)值C的計(jì)算方法如下:

最終,權(quán)值最大的節(jié)點(diǎn)優(yōu)先加入數(shù)組L中。

結(jié)合上述的分析,本文對(duì)MPk算法進(jìn)行了重新設(shè)計(jì),并使用改進(jìn)的Eulerian數(shù)據(jù)結(jié)構(gòu),稱為IMPk算法。算法描述如下:

輸入圖G,k

輸出G的線性化序列

4.3 MPk與IMPk的計(jì)算復(fù)雜度對(duì)比

在構(gòu)造線性化序列時(shí),IMPk算法與MPk算法的主要區(qū)別在于選擇新加入節(jié)點(diǎn)時(shí)的策略不同,MPk算法選擇與X集合有最多相連邊的節(jié)點(diǎn)優(yōu)先加入序列,完成這個(gè)過(guò)程的步驟如下:

(1)找出X集合中節(jié)點(diǎn)的所有鄰居,最多有個(gè)鄰居;

(2)對(duì)于X集合的每個(gè)鄰居v,判斷v與X集合共有多少邊相連,復(fù)雜度為c1×K,其中,c1為判斷兩節(jié)點(diǎn)之間是否有邊的開(kāi)銷。因此,MPk算法完成整個(gè)選擇的復(fù)雜度為:

而IMPk算法在上述第(2)步加入了權(quán)值計(jì)算,對(duì)于X集合的每個(gè)鄰居v,判斷其權(quán)值的復(fù)雜度為(c1+c2)×K,其中,c2表示計(jì)算v與X中節(jié)點(diǎn)的距離所花費(fèi)的開(kāi)銷,完成整個(gè)選擇的復(fù)雜度為:(c1+c2)×K×

由于X集合每次更新一個(gè)節(jié)點(diǎn),根據(jù)其中節(jié)點(diǎn)順序可以快速計(jì)算到v的距離,c2的值比c1小很多。因此,IMPk算法計(jì)算復(fù)雜度與MPk算法復(fù)雜度基本相當(dāng)。

4.4 MPk線性化的長(zhǎng)度下界

設(shè)MPk線性化序列L的長(zhǎng)度為|L|,L中的每個(gè)節(jié)點(diǎn)需要lb|L|個(gè)比特保存節(jié)點(diǎn)指針,2k個(gè)比特保存鄰居信息,整個(gè)序列需要保存。本文用圖G中每條有向邊,在壓縮結(jié)果中占用的bit數(shù)來(lái)衡量壓縮率,稱為BPE(Bits Per Edge),其值為:

本文給出改進(jìn)MPk線性化序列長(zhǎng)度的下界,設(shè)v∈V(G),L中每個(gè)節(jié)點(diǎn)鄰居信息占用2kbit,在最好情況下,只能記錄它的k個(gè)鄰居,所以,v在最終序列L中至少出現(xiàn)「deg(v)/k?次,deg(v)為節(jié)點(diǎn)v的度數(shù)。則L的長(zhǎng)度至少為:

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

本文使用C++實(shí)現(xiàn)了改進(jìn)的算法,并用網(wǎng)站http://snap.stanford.edu/data中提供的社會(huì)網(wǎng)絡(luò)圖數(shù)據(jù)作為輸入,分別取k=10,k=15,k=20,k=30為參數(shù)進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如表1和表2所示,表中數(shù)據(jù)為原 MPk算法與 IMPk算法運(yùn)行結(jié)果的BPE值。

表1 MP10,MP15與IMP10,IMP15序列壓縮結(jié)果比較

表2 MP20,MP30與IMP20,IMP30序列壓縮結(jié)果比較

可以看出,改進(jìn)后的IMPk算法之平均壓縮效率比原MPk算法平均高出大約23%。本文對(duì)實(shí)驗(yàn)結(jié)果作進(jìn)一步分析后發(fā)現(xiàn),社會(huì)網(wǎng)絡(luò)的聚合度對(duì)壓縮效率有很大的影響。在這些社會(huì)網(wǎng)絡(luò)中,web-Standford圖中的節(jié)點(diǎn)都以簇的形式分布[12],簇內(nèi)的節(jié)點(diǎn)連接緊密,而與其他簇連接較少,因此該網(wǎng)絡(luò)的壓縮效率最好,達(dá)到6.37 bits/edge,比原MPk算法效果提升38%。在email-EuAll圖中,各節(jié)點(diǎn)的鄰居分布比較隨機(jī),使得算法在執(zhí)行時(shí),加入了許多隨機(jī)節(jié)點(diǎn)(即跳至外層while循環(huán),選擇隨機(jī)節(jié)點(diǎn))來(lái)保證序列符合MPk定義。最終,改進(jìn)算法仍比原算法有2%的效率提升。

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

本文改進(jìn)社會(huì)網(wǎng)絡(luò)的線性化壓縮算法,通過(guò)計(jì)算權(quán)值,優(yōu)化最終序列中的節(jié)點(diǎn)順序和Eulerian數(shù)據(jù)結(jié)構(gòu)。實(shí)驗(yàn)結(jié)果證明,改進(jìn)后的壓縮算法的壓縮率相比原算法平均提高了23%。下一步工作是深入分析社會(huì)網(wǎng)絡(luò)的聚合程度對(duì)算法的影響,改進(jìn)算法以適應(yīng)社會(huì)網(wǎng)絡(luò)的不同特征。

[1] 馬 帥,李 佳,劉旭東,等.大數(shù)據(jù)時(shí)代的圖搜索技術(shù)[J].信息通信技術(shù),2013,(6):44-51.

[2] Adler M,Mitzenmacher M.Towards Compressing Web Graphs[C]//Proceedings of 2001 Data Compression Conference.Snowbird,USA:IEEE Press,2001:202-213.

[3] Apostolico A,DrovandiG.Graph Compression by BFS[J].Algorithms,2009,2(3):1031-1044.

[4] 鄭翠芳.幾種常用無(wú)損數(shù)據(jù)壓縮算法研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,2011,21(9):73-76.

[5] Boldi P,Santini M,Vigna S.Permuting Web Graphs, Algorithms and Models for the Web-Graph[M].Berlin, Germany:Springer,2009:116-126.

[6] Boldi P,Vigna S.The WebGraph Framework I: Compression Techniques[C]//Proceedings of the 13th International Conference on World Wide Web.New York, USA:ACM Press,2004:595-602.

[7] Boldi P,Vigna S.The WebGraph Framework II:Codes for the World-wide Web[C]//Proceedings of 2004 Data Compression Conference.Snowbird,USA:IEEE Press, 2004:528.

[8] Boldi P,Rosa M,Santini M,et al.Layered Label Propagation:A Multiresolution Coordinate-free Ordering for Compressing Social Networks[C]//Proceedings of the 20th International Conference on World Wide Web. Hyderabad,India[s.n.],2011:587-596.

[9] Chierichetti F,Kumar R,Lattanzi S,et al.On Compressing Social Networks[C]//Proceedings of the 15th ACM SIGKDD InternationalConference on Knowledge Discovery and Data Mining.Paris,France: ACM Press,2009:219-228.

[10] Maserrat H,Pei J.Neighbor Query Friendly Compression of Social Networks[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Washington D.C.,USA: [s.n.]:2010:533-542.

[11] Papadimitriou C H.The NP-completeness of the Bandwidth Minimization Problem[J].Computing,1976,16(3): 263-270.

[12] Easley D,Kleinberg J.Networks,Crowds,and Markets[M]. Cambridge,UK:Cambridge University Press,2010.

編輯 金胡考

An Improved Compression Algorithm Supporting Neighbor Query

GAO Shengwei,PENG Chao
(Software Engineering Institute,East China Normal University,Shanghai 200062,China)

Nowadays,most data compression algorithms do not support performing query directly on compressed data. Though the compression algorithm can perform query neighbor relations on compressed result,the compression ratio is relatively low.To solve the problem,this paper does some research on the principle of linearization compression algorithm.It analyzes the compression ratio of MPkalgorithm in different sample social network and finds the redundant information in compressed result.To eliminate these redundant information,it improves the original data structure, removes the unnecessary bits and improves the compression ratio.Experiments show that the proposed algorithm has same time complexity compared with primal algorithm,but the compression ratio can be increased by 23%in average.

linearization compression algorithm;big data;social network;heuristic algorithm;Eulerian data structure

1000-3428(2015)01-0061-04

A

TP312

10.3969/j.issn.1000-3428.2015.01.011

國(guó)家自然科學(xué)基金資助項(xiàng)目(91118008,61232006);國(guó)家“863”計(jì)劃基金資助重點(diǎn)項(xiàng)目(SQ2010AA0101016001);上海市教育委員會(huì)科研創(chuàng)新基金資助項(xiàng)目(44440590)。

高圣巍(1989-),男,碩士研究生,主研方向:移動(dòng)路由算法;彭 超,副教授。

2014-01-20

2014-03-15 E-mail:51111500026@ecnu.cn

中文引用格式:高圣巍,彭 超.一種改進(jìn)的鄰接關(guān)系可查詢壓縮算法[J].計(jì)算機(jī)工程,2015,41(1):61-64.

英文引用格式:Gao Shengwei,Peng Chao.An Improved Compression Algorithm Supporting Neighbor Query[J]. Computer Engineering,2015,41(1):61-64.