圖數(shù)據(jù)隱私保護可達性查詢算法研究

尹樹祥,靳 婷

(復旦大學計算機科學技術(shù)學院智能信息處理重點實驗室,上海200433)

圖數(shù)據(jù)隱私保護可達性查詢算法研究

尹樹祥,靳 婷

(復旦大學計算機科學技術(shù)學院智能信息處理重點實驗室,上海200433)

數(shù)據(jù)庫領(lǐng)域越來越多的數(shù)據(jù)通過圖的結(jié)構(gòu)進行存儲,隨著圖數(shù)據(jù)規(guī)模的快速增長和云計算的興起,數(shù)據(jù)擁有者希望將數(shù)據(jù)外包給具有強大計算能力的服務(wù)商為其客戶提供查詢服務(wù)。為解決數(shù)據(jù)庫中的可達性查詢問題,提出一種隱私保護的可達性索引和查詢方法。對原始的2-hop索引構(gòu)建方法進行優(yōu)化,設(shè)計maxISCover啟發(fā)式方法,給出根據(jù)人工節(jié)點添加算法建立pp-2-hop索引的unifyIS和unifyLS算法,并在此基礎(chǔ)上,給出基于密文域的優(yōu)化可達性查詢方法。實驗結(jié)果表明,基于maxISCover優(yōu)化方法和unifyIS算法建立的索引大小相比于基于原始2-hop索引的方法減小1個～2個數(shù)量級。

圖數(shù)據(jù);可達性查詢;2-hop索引;隱私保護;人工節(jié)點;查詢服務(wù)

1 概述

隨著大數(shù)據(jù)的發(fā)展,越來越多的應(yīng)用通過圖結(jié)構(gòu)的方式存儲數(shù)據(jù),如生物信息學、社交網(wǎng)絡(luò)以及半結(jié)構(gòu)化數(shù)據(jù)XML等。盡管圖數(shù)據(jù)的檢索和挖掘已經(jīng)有了很多經(jīng)典算法,然而,隨著圖數(shù)據(jù)量呈現(xiàn)爆炸式增長,使得一個快速有效的圖查詢服務(wù)成為一項具有挑戰(zhàn)性的任務(wù)。很多時候這些圖數(shù)據(jù)的擁有者并沒有維護這些查詢服務(wù)的專業(yè)知識,因此,希望有維護查詢服務(wù)專業(yè)知識和高性能集群或云計算平臺的查詢服務(wù)提供商(Service Provider,SP)能夠為其維護這樣的查詢服務(wù)。但是,SP并不是一直可以值得信賴的,同時,數(shù)據(jù)擁有者不希望有未授權(quán)的用戶知道他們的圖數(shù)據(jù),所以,安全和隱私保護成為服務(wù)質(zhì)量[1]的一個重要衡量指標。

圖數(shù)據(jù)上的可達性查詢[2]是數(shù)據(jù)庫領(lǐng)域中最為基礎(chǔ)的查詢之一。圖上的可達性查詢可以描述為:給定圖G和2個頂點u和v,可達性查詢是指通過特定的算法檢驗頂點u是否可以經(jīng)過一定的路徑到達頂點v。目前,建立高效的可達性查詢索引是圖數(shù)據(jù)上可達性查詢的研究重點。可達性查詢索引可以分為3類[3]:(1)基于傳遞閉包的壓縮算法[4],此類算法查詢效率最高效,但是其索引開銷通常是最大的,有時候是不可接受的;(2)利用深度優(yōu)先搜索算法或者廣度優(yōu)先搜索算法實現(xiàn)的優(yōu)化在線搜索算法[5],其索引空間最小,但是通常查詢時間最長;(3)基于hop的索引方法,比如2-hop[6]、TF-Label[7]、X-hop[8],和支持索引更新的hop索引方法[9]。該類算法在索引空間和查詢時間方面做了一個平衡,通常具有較小的索引和較快的查詢效率。

如今人們越來越重視隱私保護,然而目前沒有工作能夠較好地解決隱私保護的可達性查詢問題。由于2-hop索引結(jié)構(gòu)和查詢的簡單性,方便實現(xiàn)隱私保護,因此本文提出一種隱私保護的可達性索引和查詢方法。

2 2-hop索引方法

圖數(shù)據(jù)可達性查詢算法通常是基于有向無環(huán)圖,對于具有強連通分量的圖數(shù)據(jù),可以通過將其強連通分量轉(zhuǎn)化為一個頂點,該頂點與其他頂點的可達性等同于強連通分量里所有頂點和強連通分量以外頂點之間的可達性信息。為了便于描述,在本文中,假設(shè)所有的圖為有向無環(huán)圖(Directed Acyclic Graph,DAG)。

對于一個圖G=(V,E),圖上每一個頂點u∈V都具有2個集合Lin(u)和Lout(u),這2個集合稱之為頂點u的2-hop索引[6]。對于集合Lin(u)中的點,表示這些點可以到達頂點u。集合Lout(u)中的點,表示從頂點u出發(fā)可以到達的點。集合Lin(u)和Lout(u)中的點,稱之為中心點。對于給定的2個查詢頂點u和v,當且僅當Lout(u)∩Lin(v)≠?時,表示頂點u可以到達頂點v,記作u→v。

一個圖G的傳遞閉包T是關(guān)于頂點集合V上的一個二元關(guān)系。其中,(a,b)∈T當且僅當(a,b)∈E或者有一個點v∈V,同時,(a,v),(v,b)∈T。

首先,使用一個變量T′保存T中沒有被覆蓋的所有元素。初始化T′=T,使用啟發(fā)式算法進行迭代,使得T中的元素被覆蓋并從T′中移除,當T′中的元素為空時,算法結(jié)束。

然而文獻[10]發(fā)現(xiàn)MmaxDensCover中的分母對最后的索引大小作用很小,因此,本文提出了一個更加簡單的啟發(fā)式方法,稱為maxSetCover,其條件如下:

可以更加高效地建立2-hop索引。

3 隱私保護可達性查詢問題定義

本節(jié)從系統(tǒng)模型、隱私保護目標以及攻擊模型等3個方面來對本文研究問題進行定義。本文遵循數(shù)據(jù)外包領(lǐng)域中最常見的系統(tǒng)模型作為系統(tǒng)模型的基礎(chǔ),數(shù)據(jù)外包服務(wù)系統(tǒng)模型如圖1所示。

圖1 數(shù)據(jù)外包服務(wù)系統(tǒng)模型

該系統(tǒng)由3個重要組成部分:

(1)數(shù)據(jù)擁有者:數(shù)據(jù)擁有者是擁有圖數(shù)據(jù)并且需要離線計算一次隱私保護的2-hop索引的一方,建立好索引后將索引數(shù)據(jù)外包給第三方服務(wù)提供商,并對授權(quán)用戶進行授權(quán)。

(2)服務(wù)提供商(SP):SP通常具有強大的計算能力(例如云計算平臺)和專業(yè)的服務(wù)維護知識。SP可以代替數(shù)據(jù)擁有者在密文基礎(chǔ)上處理高并發(fā)查詢請求,并將運算結(jié)果返回給用戶。

(3)客戶端:客戶端向SP提交可達性查詢請求,并從SP獲得查詢結(jié)果,并對結(jié)果進行解密。

在本文中,主要保護以下兩方面的隱私,使得攻擊者無法獲取信息:

(1)查詢點之間的可達性信息,這主要是希望對于一個查詢,希望攻擊者不能夠猜測出2個頂點之間是否可達。

(2)圖數(shù)據(jù)結(jié)構(gòu),使得攻擊者無法從索引,以及每次的查詢結(jié)果獲得圖數(shù)據(jù)的結(jié)構(gòu)信息。

和其他所有數(shù)據(jù)外包研究中的假設(shè)一樣,本文認為SP是具有好奇心的,即希望獲取到包到它上面的數(shù)據(jù)信息來獲得商業(yè)利益。本文假設(shè)SP可以采取以下2種攻擊方式:

(1)基于密文的攻擊,由于上傳到SP上的所有數(shù)據(jù)都是經(jīng)過加密處理的數(shù)據(jù),因此SP只能對密文數(shù)據(jù)進行攻擊。

(2)基于集合大小的攻擊,假設(shè)SP嘗試根據(jù)索引文件大小和查詢結(jié)果集合大小來進行信息的推測。

4 圖數(shù)據(jù)隱私保護的可達性查詢

本節(jié)將重點介紹隱私保護的2-hop索引算法以及基于該索引的可達性查詢方法。

4.1 具有Imax感知的2-hop索引算法

實驗發(fā)現(xiàn)通過maxDensCover和maxSetCover啟發(fā)式方法構(gòu)建的2-hop索引Imax通常較大。較大的Imax通常會導致需要加入更多的人工節(jié)點來達到隱私保護的目的。

在本節(jié)中,提出了一種新的啟發(fā)式條件使得建立2-hop索引的過程中能夠使得Imax盡可能最小。其主要思想是在建立2-hop索引的過程中將交集的信息考慮進去。該啟發(fā)式條件的任務(wù)主要是最小化以下的2個指標:

(1)2-hop索引的大小;

為了達到以上的2個目標,本文提出了一種新的啟發(fā)式方法,稱之為maxISCover:

其中,u∈Lw,v∈Rw。該方法包括以下2個部分信息:

(1)|Ew∩T′|表示如果在該次迭代中選擇w為中心點的話,那么通過選擇該中心點能夠覆蓋T(G)中未覆蓋的元素的數(shù)目。

通過將以上2個部分信息結(jié)合起來,表示在每一次選擇中心點時,希望該中心點既可以盡可能多的覆蓋未被覆蓋的傳遞閉包元素,同時使得所有的Louts和Lins之間的交集盡可能小。

4.2 人工節(jié)點添加算法

在本節(jié)中,通過使用2個人工節(jié)點添加算法來對4.1節(jié)中建立的2-hop索引進行處理,使得其可以滿足第3節(jié)中定義的隱私保護目標。同時,為了滿足隱私保護的目的,期望向原始的2-hop索引中引入一些人工節(jié)點使得所有的Louts和Lins之間的交集大小一致。最后,通過再引入一些人工結(jié)點使得所有的Lout(Lin)集合里面的元素數(shù)目都能在一個用戶指定差值閾值之內(nèi),以防止SP可以通過基于集合大小的攻擊方法來對索引信息進行推測。

4.2.1 交集大小的歸一化

交集大小歸一化主要處理的問題是如何通過向2-hop索引(Lins和Louts)中引入一些人工節(jié)點來實現(xiàn)對于所有的u,v∈V,Lout(u)和Lin(v)的交集大小為一個定值Imax。本文將這個問題稱之為最少人工節(jié)點添加問題。下面給出最少人工節(jié)點添加問題的定義。

定義2最少人工節(jié)點添加問題是對于給定一個圖G的2-hop索引,通過向Lins和Louts中添加一些人工節(jié)點得到使得:

很容易證明最少人工節(jié)點添加問題是一個NP-hard問題。具體的證明見文獻[11]。針對該問題,本文中提出了一種貪心算法,稱之為unifyIS算法,具體的算法見算法1。

算法1交集大小歸一化算法(unifyIS)

輸入2-hop索引(Lins和Louts)

輸出添加了人工節(jié)點后的2-hop索引

算法1中F(i,k)表示如果將節(jié)點k添加到當前的Lin(i)中,可以使得當前的Lin(i)和多少的Lout(v),v∈V的交集大小增加1。如果是重復利用一個已有的節(jié)點,則可以通過向Lin(i)中添加一個節(jié)點帶來F(i,k)對的交集大小增加1,此時F(i,k)≥1。如果所有的已有的節(jié)點都不能重復利用,則同時向當前的Lin(i)和m個對應(yīng)的Lout(v),v∈V中添加一個新元素,使得添加m+1個節(jié)點,帶來m對交集大小的增加,此時F(i,k)＜1。算法1總是先尋找F(i,k)≥1的元素進行添加,在沒有這樣的元素之后,通過引入一個新的元素,并更新大頂堆H中所有的元素。進行下一步的迭代。當所有的交集大小都為Imax時,算法終止。

4.2.2 索引大小的歸一化

在4.2.1節(jié)中,最少人工節(jié)點添加問題已經(jīng)是NP-hard問題了,所以,在算法1中只考慮了如何使得任意2個集合之間的交集大小一致,但是通常由unifyIS算法建立出的2-hop索引中的Lins和Louts集合元素個數(shù)差距較大。為了防止攻擊者利用索引集合大小的信息對圖中一些具有較高或者較低的出度或入度的頂點信息進行推測。在本節(jié)中提出一種后處理的Lins和Louts集合大小歸一化處理算法unifyLS。由于對Louts的歸一化和Lins是完全一樣的過程,因此為了描述的簡潔性,這里只討論如何歸一化Lins的大小,對于Louts可以使用和Lins完全一樣的算法進行處理。

本文使用Linmax和Loutmax分別表示Lins和Louts中最大的集合大小。算法主要思想基于以下想法:

(2)算法保證在對任何中心點進行分裂的過程中,不增加Imax大小。

下面給出索引大小歸一化問題的嚴格定義。

本文在算法2中介紹了ULS算法來解決索引歸一化問題。

算法2索引大小歸一化算法(unifyLS)

輸入交集大小歸一化后的2-hop索引

輸出索引大小歸一化后的2-hop索引

在算法2中,第1行對于每一個頂點u的Lin(u),如果發(fā)現(xiàn)它的集合大小小于Linmax。在算法第2行和第3行,從當前的Lin(u)中選擇一個人工節(jié)點,并將其分裂為n+1個新的人工節(jié)點。在第4行中,使用分裂后的節(jié)點集合代替原來的節(jié)點w。在算法第5行～第10行,針對其他頂點的Lin(v)和Lout(v),v∈V的不同的大小和是否包含節(jié)點w的情況,分別根絕算法進行相應(yīng)的處理,以使得在替換節(jié)點的同時保證所有集合之間的交集大小保持Imax不改變。

通過以上的索引大小歸一化算法處理后的2-hop索引的任意集合之間的交集大小并未改變,與此同時,算法總是使得距離目標遠的集合的增長速度大于距離目標近的集合,最后可以交替在Lins和Louts上使用索引大小歸一化算法直到每一類集合之間的大小滿足定義的閾值δ。

4.3 索引加密處理算法

在4.2節(jié)中,通過引入unifyIS和unifyLS算法使得任何2個Lins和Louts集合之間的交集大小都等于Imax同時使得所有的Lins和Louts的集合大小都在一個規(guī)定的閾值范圍內(nèi)。在本節(jié)中,介紹如何對索引進行加密以滿足安全性要求。

為了區(qū)分在索引中,哪些是原始2-hop索引中真實的中心點,哪些是通過算法引入的人工中心點,本文對2-hop索引中的中心點使用一個標志位來表示它的真實與否,具體見定義4。

定義42-hop索引中的每一個中心點都是一個二元組(w,f),當該w中心點是一個真實的中心點時f=0,否則f=1。

基于定義4,文中對所有的中心點進行加密使得既可以保護查詢點之間的可達性信息也可以保護圖的結(jié)構(gòu)信息。為了隱藏圖中頂點和索引中中心點的聯(lián)系,對(w,f)中的w和Lin(u),Lout(u)中的u使用帶有不同參數(shù)的單向哈希函數(shù)來對這2類點進行映射,把這2個帶有不同參數(shù)的哈希函數(shù)分別標記為hs1(w)和hs2(u)。使用不同的參數(shù)使得對于w=u,hs1(w)≠hs2(u)。關(guān)于二元組中標志位的加密,文中使用乘法同態(tài)加密算法Elgamal算法(E(f))對其進行加密。采用Elgamal加密算法主要有以下好處:(1)由于標志位只有2種不同的值0或1, Elgamal算法在加密時引入隨機數(shù)使得相同的值可以被加密成不同的密文,因此使用Elgamal算法可以使得加密后的密文域變大,進而SP無法通過對相同的標志位進行統(tǒng)計以獲得標志位信息。(2)由于Elgamal算法是乘法同態(tài)加密算法,可以減少客戶端的解密計算量。

至此已經(jīng)完成了隱私保護的2-hop索引的創(chuàng)建,下面給出隱私保護的2-hop(pp-2-hop)索引的精確定義。

定義5對于一個圖G=(V,E),它的pp-2-hop索引就是對于圖中每個加密的頂點ue(ue=hs2(u))都帶有2個加密的集合Lout(ue)和Lin(ue)表示頂點u的可達性信息。其中,對于集合Lout(ue)和集合Lin(ue)中的每一個元素都是一個二元組(we,fe),we=hs1(w),fe=E(f)。

4.4 隱私保護的可達性查詢處理

基于4.3節(jié)中建立的pp-2-hop索引,本節(jié)介紹如何在SP不需要對索引進行解密的情況下進行可達性查詢。查詢處理主要有以下3個步驟:(1)客戶端對查詢內(nèi)容(u,v)進行加密,使用hs2(·)哈希方法進行映射處理,將查詢內(nèi)容映射成(ue,ve),并將其提交到服務(wù)商SP進行查詢;(2)在服務(wù)端SP對集合Lout(ue)和Lin(ve)進行集合交集操作,將交集后的結(jié)果Re返回給客戶端;(3)客戶端使用從數(shù)據(jù)擁有者處通過授權(quán)獲得的密鑰K通過Elgamal解密程序?qū)e進行解密并得到結(jié)果。

在樸素的查詢算法中,在上述的查詢步驟的步驟(3)中,服務(wù)商將所有的交集結(jié)果中的標志位返回給客戶端。由于在索引算法中,保證了所有的查詢結(jié)果的大小都為Imax,因此客戶端需要對所有的Imax個加密后的標志位信息進行解密,直到找到一個解密后為0的結(jié)果,說明查詢點u可以到達頂點v。很明顯,在這種算法中,客戶端解密次數(shù)最多要解密Imax次,由于解密是一件很耗時的事情,因此本文提出一種基于乘法同態(tài)加密算法的查詢處理方法。

在基于乘法同態(tài)加密算法的查詢算法中,客戶端只需要進行一次解密操作就可以得到最終的查詢結(jié)果。將2個查詢點(ue,ve)的Lout(ue)和Lin(ve)的交集結(jié)果記為:

由于標志位是使用的乘法同態(tài)加密算法Elgamal進行實現(xiàn),所謂乘法同態(tài)是指密文下的乘法運算結(jié)果等于明文下的乘法再進行加密,因此密文下的乘法運算結(jié)果進行解密就等于明文下的乘法結(jié)果。所以,最終的查詢結(jié)果可以定義為:

最終將Re返回給客戶端,客戶端私用私有密鑰進行一次解密,如果得到結(jié)果為0,表面頂點u可以到達頂點v,否則不可達。

5 隱私分析

本節(jié)針對之前定義的攻擊模型和保護目標,對本文提出的可達性索引和查詢方法安全性進行分析。

首先,分析攻擊者在查詢算法進行的每一步攻擊者SP可以獲取到的信息。對于一個給定的查詢(ue,ve),SP首先會在pp-2-hop索引中檢索到Lout(ue)和Lin(ve),然后SP求得這2個集合的交集,并在基于Elgamal加密后的標志位上進行乘法運算進而得到最終的返回結(jié)果Re。

由于SHA-1哈希算法和Elgamal算法在安全領(lǐng)域都被證明是沒法攻破的,因此SP無法破解哈希算法,它就無法破解出查詢點ue,ve的真實信息,同時,它也無法破解出索引中的中心點信息,那么它就無法在這2類點之間找到映射關(guān)系,進而無法猜測出哪些中心點是人工節(jié)點。同時,由于SP無法破解Elgamal算法,因此它不能破解索引中的標志位信息,進而同樣無法判定一個點是否為真實中心點或者人工節(jié)點?；谝陨?點,由于SP無法辨別中心點的真實性,它無法獲知一個查詢的結(jié)果信息,因此它無法破解查詢點之間的可達性信息。由于所有的查詢都無法獲取可達性信息,因此它無法破解圖的結(jié)構(gòu)信息,它始終不知道圖中任意2個點之間的可達性。

其次,由于通過算法使得所有的交集集合大小均為Imax,因此對于任何的查詢,從SP使得角度,它獲得的信息是一致的。所以,它無法從查詢結(jié)果的大小來推斷查詢點之間的信息。由于所有的索引集合大小都完全相同,因此SP也無法從索引集合的大小推測出圖中某些點的度的信息。

綜上,證明隱私保護的2-hop索引和查詢算法可有效保護查詢點之間的可達性信息和圖結(jié)構(gòu)信息。

6 實驗結(jié)果與分析

本節(jié)通過實驗驗證本文算法的效率以及對原始2-hop算法的優(yōu)化效果。實驗環(huán)境為Intel i3-2310 2.10 GHz CPU,4 GB內(nèi)存,Windows7操作系統(tǒng),文中的算法用C++實現(xiàn)。實驗中的哈希函數(shù)采用160 bit SHA-1算法,加密算法是1024 bit Elgamal算法。

實驗使用4個真實數(shù)據(jù)集[12]來進行實驗效果的驗證,關(guān)于這些數(shù)據(jù)集信息見表1,其中,G表示數(shù)據(jù)集名稱;|V|表示圖的頂點個數(shù);|E|表示圖的邊數(shù);|E|/|V|表示圖的稀疏性。對于每個數(shù)據(jù)集生成1000個隨機的查詢,50%為可達的查詢;另外50%為不可達的查詢。

表1 數(shù)據(jù)集信息

在表2中,比較了3種不同的啟發(fā)式方法條件下,建立出的2-hop索引中的最大的交集集合大小Imax的比較。從表中很明顯看出通過maxISCover啟發(fā)式方法條件創(chuàng)建出的索引的最大交集集合大小Imax要比其他2種啟發(fā)式條件要小很多。其主要原因在于利用maxISCover啟發(fā)式方法條件建立2-hop索引時,在每一次迭代中,總是將當前的Imax考慮到索引的建立過程中,所以每次總是選擇能夠覆蓋盡可能多的傳遞閉包集合元素同時使得Imax盡可能小的中心點。從具體數(shù)據(jù)來看,maxIScover方法比maxDens-Cover方法和maxSetCover方法的實驗結(jié)果要好108倍和1.43倍。

表2 不同啟發(fā)式條件下最大交集大小Imax比較

觀察交集大小歸一化算法在不同的Imax條件下的效果。在表3比較了交集大小歸一化后的索引大小。

表3 不同啟發(fā)式條件下unifyIS算法效果比較

從表中可以看出,在基于maxISCover啟發(fā)式方法條件下,由于Imax是最小的,然后對比表中不同的啟發(fā)式條件下添加人工節(jié)點后的索引大小,可以看出unifyIS算法可以保證在添加人工節(jié)點后的索引大小要比最壞的|V2|級別要小1個～2個數(shù)量級。本文中的算法在所有的數(shù)據(jù)集上都具有較好的結(jié)果。

在表4中,列出了對于一個可達性查詢在SP端和客戶端所需要的時間,表中的時間是1000個查詢平均后每個查詢的時間。

表4 服務(wù)端和客戶端的查詢時間ms

從表4可以看出,幾乎所有的服務(wù)端的查詢時間與Imax成正相關(guān),其主要原因在于服務(wù)端SP的查詢時間在于集合求交集和對Imax個標志位進行密文域上的乘法操作這兩部分構(gòu)成,集合的交集可以在幾乎可以忽略不計的時間內(nèi)完成,SP端的時間差距在Imax個密文域的標志位乘法運算。本文提出的maxISCover方法具有較小的Imax,因此,SP端本文的算法查詢效率較高。所有的算法客戶端都只需要進行一次解密操作,所以,所有的客戶端的查詢時間都幾乎一致,并且客戶端查詢時間較快,用戶可以接受。

7 結(jié)束語

本文對圖數(shù)據(jù)隱私保護可達性查詢問題進行研究。首先對原始2-hop索引建立算法的啟發(fā)式方法進行優(yōu)化,并針對優(yōu)化后的2-hop索引引入了unifyIS算法和unifyLS算法,以構(gòu)建隱私保護的2-hop索引(pp-2-hop)?；趐p-2-hop索引,提出隱私保護的查詢方法及其優(yōu)化方法。同時,對提出的pp-2-hop索引和查詢方法的安全性進行分析和證明,結(jié)果表明了該算法的有效性。今后將考慮如何基于pp-2-hop索引結(jié)構(gòu)實現(xiàn)隱私保護的最短路徑查詢。

[1] Menezes D A.QoS Issues in Web Services[J].Internet Computing,2002,6(6):72-75.

[2] 李先通.圖數(shù)據(jù)查詢技術(shù)的研究[D].哈爾濱:哈爾濱工業(yè)大學,2009.

[3] Jin Ruoming.Scarab:Scaling Reachability Computation on Large Graphs[C]//Proceedings of SIGMOD’12. Scottsdale,USA:ACM Press,2012:169-180.

[4] Schaik S J,Moor O.A Memory Efficient Reachability Data Structure Through Bit Vector Compression[C]// Proceedings of SIGMOD’11.Athens,Greece:ACM Press,2011:913-924.

[5] Seufert S.Ferrari:Flexible and Efficient Reachability Range Assignment for Graph Indexing[C]//Proceedings of ICDE’13.Brisbane,Australia:IEEE Press, 2013:1009-1020.

[6] Cohen E.Reachability and Distance Queries via 2-hop Labels[J].SIAM Journal on Computing,2003,32(5): 1338-1355.

[7] James C,Huang Silu.Tf-label:A Topological-folding Labeling Scheme for Reachability Querying in a Large Graph[C]//Proceedings of SIGMOD’13.New York, USA:ACM Press,2013:193-204.

[8] 舒 虎,崇志宏,倪巍偉,等.X-Hop:傳遞閉包的多跳數(shù)壓縮存儲和快速可達性查詢[J].計算機科學, 2012,39(3):144-148.

[9] 劉旭輝,馮建華,洪 親.一種支持更新的圖可達性查詢算法[J].計算機科學,2007,34(10):49-52.

[10] Cheng Jiefeng,Jeffrey X Y.Fast Computation of Reachability Labeling for Large Graphs[C]//Proceedings of EDBT’06.Munich,Germany:ACMPress,2006: 961-979.

[11] Yin Shuxiang,Jin Ting.Privacy Preserving Reachability Query Algorithm[EB/OL].(2012-10-21).http:// admis.fudan.edu.cn/member/sxyin/proof.pdf.

[12] Vladimir B.Pajek Datasets[EB/OL].(2013-01-21). http://vlado.fmf.uni-lj.si/pub/networks/data/.

編輯 劉 冰

Research on Privacy Protection Reachability Query Algorithm of Graph Data

YIN Shuxiang,JIN Ting
(Key Lab of Intelligent Information Processing,School of Computer Science,Fudan University,Shanghai 200433,China)

Due to the massive volume of graph data from a wide range of recent applications and unprecedented graph data growth,it is becoming economically appealing for data owners to outsource their data to a powerful Service Provider (SP),such as a cloud computing platform,which provides high computational query services.This paper studies a novel privacy preserving 2-hop index and query algorithm for a fundamental query for graphs namely the reachability query.It optimizes the existing method for building 2-hop index,proposes one optimizing method(maxISCover),and two algorithms(unifyIS and unifyLS)to build privacy preserving 2-hop(pp-2-hop)index by adding some surrogate nodes, and raises up an optimized query processing algorithm based on pp-2-hop index.Experimental results show that the index size of this algorithm based on maxISCover optimization method and the unifyIS is reduced by1～2 orders of magnitude, compared with the method based on the original 2-hop.

graph data;reachability query;2-hop index;privacy protection;artificial node;query service

尹樹祥,靳 婷.圖數(shù)據(jù)隱私保護可達性查詢算法研究[J].計算機工程,2015,41(2):167-172.

英文引用格式:Yin Shuxiang,Jin Ting.Research on Privacy Protection Reachability Query Algorithm of Graph Data[J].Computer Engineering,41(2):167-172.

1000-3428(2015)02-0167-06

:A

:TP391

10.3969/j.issn.1000-3428.2015.02.032

尹樹祥(1989-),男,碩士研究生,主研方向:機器學習,模式識別;靳 婷,博士研究生。

2014-04-08

:2014-04-29E-mail:sxyin@fudan.edu.cn