胡德敏,廖正佳

(上海理工大學(xué) 光電信息與計算機(jī)工程學(xué)院,上海 200093)

1 引 言

隨著手持設(shè)備的日益普及,基于位置的應(yīng)用程序和服務(wù)可以訪問準(zhǔn)確和實(shí)時的位置信息,在用戶發(fā)送查詢請求過程中難免會存在個人位置隱私泄露的問題.

許多基于k-匿名[1,2]置隱私保護(hù)方法已被證明不能充分保護(hù)LBS隱私,容易受到人口分布密度、背景知識攻擊等影響.差分隱私[3,4]能使數(shù)據(jù)集的計算結(jié)果對元素的變化不敏感,因此由于數(shù)據(jù)集的加入而導(dǎo)致個別元素隱私泄露的風(fēng)險被控制在可接受范圍內(nèi).差分隱私具有堅實(shí)的數(shù)學(xué)基礎(chǔ);嚴(yán)格定義隱私保護(hù)并提供定量評估方法,逐漸成為LBS隱私保護(hù)領(lǐng)域的熱門話題.但在連續(xù)的位置查詢服務(wù)時,容易造成疊加噪聲導(dǎo)致查詢精度下降.

針對以上問題,本文在Hilbert曲線構(gòu)建的k-匿名集的基礎(chǔ)上,提出了基于m叉平均樹的差分隱私位置隱私保護(hù)方法(m-Ary Average Tree Differential Privacy,MATDP).該方法通過引入m叉平均樹結(jié)構(gòu)拆分匿名集數(shù)據(jù)以增強(qiáng)數(shù)據(jù)效用,主要提出了經(jīng)過嚴(yán)密推導(dǎo)得出的具有較小誤差上界的拉普拉斯隱私預(yù)算分配策略.該隱私預(yù)算分配策略能有效控制連續(xù)查詢環(huán)境下噪聲疊加問題,在保證隱私保護(hù)強(qiáng)度的同時降低連續(xù)查詢誤差.實(shí)驗(yàn)結(jié)果表明,相較于其他位置隱私保護(hù)方法,該方法能在一定查詢范圍內(nèi)減小連續(xù)查詢誤差,并且在同類提高查詢精度的差分隱私算法中具有較高運(yùn)行效率.

2 相關(guān)工作

位置隱私保護(hù)主要有三大方面:位置匿名、位置加密、位置擾動.

位置匿名被大量討論和應(yīng)用,k-匿名機(jī)制是位置匿名的典型代表.文獻(xiàn)[5]提出的模型能支持具有上下文敏感的個性化隱私要求的廣泛用戶的位置k-匿名,從而使每個移動節(jié)點(diǎn)能夠指定最低匿名等級以及最大時間和空間分辨率.但該匿名集中位置元素不滿足互惠性[6],攻擊者通過連續(xù)查詢的匿名集求交后得到用戶實(shí)際位置.文獻(xiàn)[7]通過細(xì)化確定同一匿名集中移動用戶的匿名空間是否相同,并且刪除交集后的兩個匿名空間是否為單一路徑來保證互惠性.由于k-匿名機(jī)制容易受限于人口密度的分布,文獻(xiàn)[8,9]以網(wǎng)格模式生成虛擬位置,同時考慮真實(shí)環(huán)境中的人口分布密度.總體而言,k-匿名有兩個方面的制約因素,一方面匿名集中需要找代理用戶與匿名服務(wù)器間的通訊[10]或用戶間的對等協(xié)作,信任機(jī)制在這種模型中發(fā)揮著重的作用,信任的評估和量化變成一大挑戰(zhàn);另一方面k-匿名機(jī)制無法應(yīng)對背景知識攻擊,攻擊者獲得的背景知識是無法量化和建模的.因此單一的位置匿名方法隱私保護(hù)強(qiáng)度過低.

位置加密的密碼學(xué)技術(shù)在位置隱私問題中得到了廣泛的應(yīng)用,隱私信息檢索技術(shù)(PIR)[11],保證LSP在無法知曉查詢內(nèi)容和查詢結(jié)果的同時完成查詢工作.密碼技術(shù)在定位隱私保護(hù)方面更為徹底和安全,理論上完全消除了攻擊者的威脅,但密碼學(xué)方法的缺點(diǎn)是計算復(fù)雜度高,對硬件要求較高.

差分隱私位置保護(hù)方法因其具有嚴(yán)格推理和證明的隱私保證,成為位置擾動中的一個常被應(yīng)用的方法.在沒有任何關(guān)于攻擊者先前知識的假設(shè)情況下,地理不可區(qū)分[12]使用差分隱私來擾亂真正的用戶位置.在LBS應(yīng)用中,連續(xù)查詢環(huán)境時噪聲會累加到每次查詢上,產(chǎn)生的噪聲量會影響查詢精度和數(shù)據(jù)的可用性.如何在隱私保護(hù)和查詢精度之間獲得較好的權(quán)衡,是學(xué)者們一直在努力的方向.文獻(xiàn)[13]基于小波變換的差分隱私方法,該方法把數(shù)據(jù)映射成小波樹后添加噪聲,但映射成小波樹后會出現(xiàn)大量為零的值需要進(jìn)一步壓縮,增加了算法復(fù)雜度.文獻(xiàn)[14]提出PriLocation模型,將實(shí)際位置劃分到k個集合中,統(tǒng)計集合的訪問頻次,再對k個集合添加噪聲,由于集合數(shù)一定小于單個位置數(shù)量,所以噪聲的添加會減少,但實(shí)際查詢準(zhǔn)確率不高.文獻(xiàn)[15,16]提出了將樹結(jié)構(gòu)加入差分隱私的方法,缺點(diǎn)是劃分不穩(wěn)定會造成劃分結(jié)構(gòu)不均勻的情況.文獻(xiàn)[17]通過迭代的方式往樹的層次中添加噪聲,雖然降低了查詢誤差,然而在有些層次中不滿足一致性約束[18].如何設(shè)計一個適合于移動設(shè)備在連續(xù)查詢環(huán)境下的位置隱私保護(hù)方法,是本文要解決的關(guān)鍵問題.

單一的k-匿名機(jī)制,由于缺乏抵抗背景知識攻擊的能力,需要與其他位置隱私保護(hù)方法結(jié)合使用.從另一角度來看,若僅使用差分隱私位置保護(hù)方法擾動單個位置,依據(jù)定義可知,LSP查詢數(shù)據(jù)集時會導(dǎo)致對單個記錄的變化敏感度較低,使得LBS服務(wù)沒有意義[26].差分隱私更適用于對數(shù)據(jù)集信息的擾動,因此本文將k-匿名機(jī)制與差分隱私技術(shù)相結(jié)合.

對于當(dāng)前差分隱私位置保護(hù)方法中存在的噪聲累加導(dǎo)致查詢精度過低的情況,本文在Hilbert曲線劃分的k-匿名機(jī)制基礎(chǔ)上,提出基于m叉平均樹的差分隱私位置隱私保護(hù)方法.該方法使用m叉平均樹結(jié)構(gòu)來拆分?jǐn)?shù)據(jù)以增強(qiáng)數(shù)據(jù)效用,并經(jīng)過嚴(yán)格數(shù)學(xué)推導(dǎo),使得隱私預(yù)算的分配存在較小噪聲方差上界,在相同的隱私水平下提高了數(shù)據(jù)查詢的準(zhǔn)確性和數(shù)據(jù)效用.

3 相關(guān)概念

差分隱私

差分隱私保證數(shù)據(jù)的發(fā)布結(jié)果不會因任何特定個體的存在而發(fā)生顯著變化.對于數(shù)據(jù)是數(shù)值類的情況,最普遍的機(jī)制是將從拉普拉斯分布中抽取的受控隨機(jī)噪聲添加到查詢輸出中.噪音量與隨機(jī)函數(shù)的靈敏度相關(guān)聯(lián).

定義1.ε-差分隱私.對于任何兩個數(shù)據(jù)集D和D′,至多包含一個不同的記錄,對任意輸出S?Range(f)滿足:

Pr[f(D)∈S]≤eε×Pr[f(D′)∈S]

則算法f滿足ε-差分隱私.

隱私預(yù)算ε影響隱私保護(hù)程度,ε越小,f(D)與f(D′)的概率密度函數(shù)相似度越大,隱私強(qiáng)度也越大,數(shù)據(jù)可用性降低(即查詢精度降低).本文目標(biāo)是通過對隱私預(yù)算ε的合理分配,謀求在隱私保護(hù)強(qiáng)度與查詢精度之間的平衡.

Δf為f的敏感度,是數(shù)據(jù)集D中任何單個元組變化時f中的最大變化,即:

根據(jù)定義3可知,同一數(shù)據(jù)集下多個差分隱私的組合會導(dǎo)致隱私參數(shù)ε和方差的累加.因此,在連續(xù)查詢情況下,每個興趣點(diǎn)噪聲的累加的確會帶來較大的查詢誤差.

4 基于m叉平均樹的差分隱私位置隱私保護(hù)方法

4.1 整體框架

本文提出的位置隱私保護(hù)架構(gòu)由客戶端、匿名服務(wù)器(Anonymous Server,AS)和位置服務(wù)提供商(Location Service Provider,LSP)組成,如圖1所示.

圖1 整體框架圖Fig.1 Overall framework

1)客戶端.客戶發(fā)送實(shí)時查詢請求Q=(分別表示用戶身份信息,用戶真實(shí)位置,查詢內(nèi)容以及時間戳)給AS進(jìn)行匿名操作.

2)匿名服務(wù)器AS.出于對移動客戶端的計算能力和存儲負(fù)載的考慮,引入匿名服務(wù)器進(jìn)行匿名操作.匿名服務(wù)器能實(shí)現(xiàn)大規(guī)模計算,處理大量用戶頻繁的位置更新操作(特別是在連續(xù)查詢環(huán)境中)以及細(xì)化查詢結(jié)果.缺點(diǎn)是匿名服務(wù)器掌握了移動用戶相關(guān)的位置信息,成為系統(tǒng)處理的瓶頸,攻擊時會導(dǎo)致用戶隱私泄露.出于對系統(tǒng)安全性考慮,要求AS掌握查詢請求中的loc數(shù)據(jù),而無法獲知真實(shí)的查詢內(nèi)容(防止背景知識攻擊).

3)位置服務(wù)提供商LSP.LSP負(fù)責(zé)處理查詢,僅掌握content數(shù)據(jù)以及擾動后的匿名空間區(qū)域(Anonymous Space Region,ASR)數(shù)據(jù),無法獲知相關(guān)身份信息.完成查詢操作后,將候選結(jié)果集R發(fā)送給AS.

具體步驟如下:

1)用戶將查詢請求Q=發(fā)送給AS.

2)AS獲取Q中的位置信息loc,利用初始匿名集生成模塊生成初始k-匿名集;匿名集擾動模塊利用m叉平均樹差分隱私保護(hù)方法對k-匿名集中的興趣點(diǎn)進(jìn)行擾動,最終生成ASR.將擾動后的查詢請求Q′發(fā)送給LSP.

3)LSP獲取Q′中的查詢信息content以及ASR,完成查詢操作后返回給AS候選結(jié)果集R.

4)AS利用結(jié)果篩選模塊篩選出精確結(jié)果集(Exact Result Set,ERS),返回給客戶端.

4.2 生成初始k-匿名集

使用基于密度劃分的Hilbert曲線[21,22]將興趣點(diǎn)映射到一維.Hilbert曲線的優(yōu)勢是,在將二維空間數(shù)據(jù)映射到一維時,在二維空間上鄰近的點(diǎn)在Hilbert曲線上依然保持鄰近.考慮到興趣點(diǎn)分布密度的因素,首先對區(qū)域進(jìn)行四分樹劃分,使每個單元內(nèi)的興趣點(diǎn)個數(shù)不大于閾值δ,如圖2所示(圖中設(shè)δ=1);其次將興趣點(diǎn)依據(jù)Hilbert值(H值)從小到大排序;最后,為了滿足匿名集的互惠性,將排序后的興趣點(diǎn)基于桶的劃分得到k-匿名集.

定義4.互惠性[6].相同匿名集中的任意兩個元素a1,a2,若a1,a2分別構(gòu)造的匿名集Sa1,Sa2,滿足Sa1=Sa2,則稱此匿名集具有互惠性.

圖2 基于密度劃分的Hilbert曲線Fig.2 Hilbert curve based on density division

例如,圖2中離用戶實(shí)際位置最近的興趣點(diǎn)為P9,若k=3,Hilbert曲線填充后,興趣點(diǎn)依據(jù)從小到大排序并基于桶的劃分后得到:

P1,P2,P7P8,P9,P4P5,P6,P10P13,P15,P12P11,P14,P3

P9所在匿名集為,陰影部分為匿名區(qū)域.從圖中可以看出形成的匿名區(qū)域較大(包含的單元格較多,后期噪聲累加后會產(chǎn)生較大的查詢誤差),需要進(jìn)一步優(yōu)化.

為了優(yōu)化Hilbert曲線生成的匿名區(qū)域.通過改變曲線的起始點(diǎn)和方向,生成多種Hilbert曲線(本文只考慮8種Hilbert曲線,即4種起始點(diǎn)×2種方向),篩選出匿名區(qū)域最優(yōu)的匿名集作為最終的匿名集.如圖3所示,由該Hilbert曲線獲得的匿名區(qū)域明顯優(yōu)于原始曲線生成的匿名區(qū).

4.3 匿名集的差分?jǐn)_動

本文用提出基于m叉平均樹的差分隱私方法,對形成的初始匿名集添加拉普拉斯噪聲擾動.通過引入m叉平均樹的數(shù)據(jù)結(jié)構(gòu),推導(dǎo)出具有較小誤差上界的隱私預(yù)算分配方法降低噪聲.

圖3 改變后的Hilbert曲線Fig.3 Changed Hilbert curve

4.3.1 構(gòu)建M叉平均樹

定義5.廣義敏感度[23].設(shè)有函數(shù)集F,其中f∈F,W為f的權(quán)重函數(shù),函數(shù)f關(guān)于權(quán)重函數(shù)W的廣義敏感度為滿足以下式子中ρ的最小值:

∑f∈F(W(f)·|f(D)-f(D′)|)≤ρ·‖D-D′‖1

(1)

其中‖D-D′‖1=∑v∈D-D′|v|.

定義6.函數(shù)f關(guān)于權(quán)重函數(shù)W的廣義敏感度為ρ,若算法A在數(shù)據(jù)集D的輸出為{f(D)+X(f)},其中X(f)服從拉普拉斯分布λ/W(f)的隨機(jī)噪聲,那么算法A滿足(2ρ/λ)-差分隱私.

定義7.m叉平均樹.m叉平均樹中,除葉子節(jié)點(diǎn)以外,每個節(jié)點(diǎn)有m個孩子,內(nèi)部節(jié)點(diǎn)的值為其孩子節(jié)點(diǎn)的平均值.

例如,當(dāng)匿名集中興趣點(diǎn)個數(shù)為7(以圖3中Hilbert曲線值為例),給定高度h的值為3,則m=2,生成的平均樹如圖4.

圖4 m叉平均樹Fig.4 M-ary average tree

根據(jù)公式(1)和權(quán)重函數(shù)W(f)=mi計算出m叉平均數(shù)的廣義敏感度.設(shè)匿名集D上的元素值被改變了δ,則其葉節(jié)點(diǎn)及該葉節(jié)點(diǎn)的祖先節(jié)點(diǎn)也會被改變,共有h+1個節(jié)點(diǎn)值被改變,深度為i的節(jié)點(diǎn)被改變的大小為δ/mi,將此代入公式(1),得到關(guān)于權(quán)重函數(shù)的廣義敏感度為:

4.3.2 隱私預(yù)算分配

4.3.3 查詢誤差上界推導(dǎo)

本文用方差E(Q)表示查詢請求Q的誤差度量.由定義3可知,噪聲是在每個節(jié)點(diǎn)添加的,由此產(chǎn)生的誤差為每層產(chǎn)生的方差之和,即:

(2)

根據(jù)柯西不等式,

(3)

通過整理可得:

(4)

將公式(4)代入公式(3)得到:

(5)

由此得到了每層節(jié)點(diǎn)需要添加噪聲的隱私參數(shù)εi.

因?yàn)椴樵冋`差:

由式(5)可以得出誤差的最大值:

基于m叉平均樹的差分隱私位置保護(hù)方法的整體算法如下:

算法.基于m叉平均樹的差分隱私位置保護(hù)算法

輸入:用戶u所在的二維空間G,閾值δ,匿名集參數(shù)k

輸出:擾動后的匿名區(qū)域ASR,匿名集u.s

1.if(G.POI.count

2.return ERROR;

3.else

4.G劃分為4個子區(qū)域Gi;

5.for i=1 to 4

6.if(Gi.POI.count>δ)

7.do step 4;

8.else 結(jié)束區(qū)域G的劃分;

9.end for

10.end else

11.end if

12.G中填充Hilbert曲線;

13.order(H(G.POI));//將興趣點(diǎn)的Hilbert值排序

14.基于桶的劃分k-匿名集;

15.ASR=Area(u.s);//記錄下u所在的匿名集形成匿名區(qū)域

16.for i=1 to 8

17.改變Hilbert曲線的起始點(diǎn)或方向;

18.do step 13 to 15;

19.if(Area(u.s′)

20.ASR=Area(u.s′);

21.u.s=u.s′;u.s′=NULL;//保留當(dāng)前匿名集和匿名區(qū)域

22.end if

23.end for

26.將平均樹中前u.s.count個葉子節(jié)點(diǎn)的值依次賦給u.s中的每個元素.

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

本文針對查詢誤差和算法運(yùn)行效率對MATDP算法進(jìn)行對比分析.基于Hilbert曲線生成匿名集的部分,在匿名服務(wù)器離線狀態(tài)下生成,即離線狀態(tài)下根據(jù)既定的閾值δ劃分網(wǎng)格,填充8種Hilbert曲線,并按H值的大小排序興趣點(diǎn).影響查詢誤差的因素有很多方面,如網(wǎng)格劃分閾值δ、匿名集規(guī)模k、匿名區(qū)域大小、樹高h(yuǎn)、隱私預(yù)算ε以及興趣點(diǎn)分布密度等.因此實(shí)驗(yàn)不僅從以上幾個因素測試,也要與其他算法比較該算法的查詢誤差和運(yùn)行效率.

5.1 實(shí)驗(yàn)數(shù)據(jù)與環(huán)境

實(shí)驗(yàn)環(huán)境為Inter?CoreTMi5,windows7操作系統(tǒng),8GB內(nèi)存,算法是Eclipse環(huán)境下基于Java編寫.

實(shí)驗(yàn)選擇兩個數(shù)據(jù)集進(jìn)行,第一個數(shù)據(jù)集為infochimps大數(shù)據(jù)網(wǎng)站提供的美國48個大陸州的地標(biāo)位置組成的地標(biāo),實(shí)驗(yàn)中簡稱為“l(fā)andmark” 數(shù)據(jù)集,數(shù)據(jù)分布較密集,約有870k個數(shù)據(jù)點(diǎn).第二數(shù)據(jù)集為美國存儲設(shè)施位置數(shù)據(jù),包括國家連鎖存儲設(shè)施,以及本地?fù)碛泻瓦\(yùn)營的設(shè)施,數(shù)據(jù)集較小,約有9000個數(shù)據(jù)點(diǎn),簡稱為“storage”數(shù)據(jù).兩個數(shù)據(jù)集的密度和稀疏度是顯而易見的,因此可以用這兩個數(shù)據(jù)集來驗(yàn)證本文的方法對不同密度環(huán)境因素的影響.

實(shí)驗(yàn)中將平均方差作為查詢誤差的衡量標(biāo)準(zhǔn):

其中q(D)為真實(shí)位置的查詢結(jié)果,q(D′)為加噪后的查詢結(jié)果,|Q|為匿名集大小.用移動對象生成器[25],生成速度為30km/h的300個移動用戶,設(shè)查詢總時間為30min,查詢間隔為5min,因此所有用戶一共要發(fā)起1800次的連續(xù)查詢.

5.2 網(wǎng)格劃分閾值δ在不同匿名區(qū)大小中對查詢誤差的影響

該實(shí)驗(yàn)中取k=180,ε=1,h=3.比較不同密度環(huán)境下δ對查詢誤差的影響(實(shí)驗(yàn)中δ的最小取值要使得最小單元格不小于1km2).q1～q8為8種Hilbert曲線形成的匿名區(qū)域從小到大的排序.

從圖5(a)可知,在密度較大的landmark數(shù)據(jù)集中對于同一δ值,q1～q8的誤差波動幅度不大,基本相似.在圖5(b)storage數(shù)據(jù)集中,同一個δ值q1～q8的誤差呈逐漸遞增趨勢,匿名區(qū)面積較小的誤差值較小.這是因?yàn)檩^密環(huán)境中由于k值一定,不同Hilbert曲線所包含的單元格數(shù)相近,噪聲疊加后誤差也基本相似;而在稀疏環(huán)境中,k值一定時,匿名區(qū)越小的Hilbert曲線所包含的單元格也較少,誤差也越小.因此在密集環(huán)境中,k值一定時無論哪種Hilbert曲線,誤差影響都不大;稀疏環(huán)境中,k值一定時要選擇形成匿名區(qū)面積較小的Hilbert曲線.

圖5 閾值δ對查詢誤差的影響Fig.5 Influence of threshold δ on query error

比較圖5(a)和圖5(b)兩圖,δ取值極小和極大時,誤差都較大,δ取值較為適中時誤差最小,且密集環(huán)境中的最優(yōu)閾值大于稀疏環(huán)境的最優(yōu)閾值.這是因?yàn)棣倪^小,劃分的單元格就越細(xì),較多的單元格會使噪聲疊加較多;反之δ過大,查詢精度不夠也會造成誤差過大,所以較適中的δ值會降低查詢誤差.

5.3 樹高h(yuǎn)對查詢誤差的影響

該實(shí)驗(yàn)取k=180,根據(jù)上節(jié)的結(jié)論,landmark數(shù)據(jù)集取δ=100,storage數(shù)據(jù)集取δ=60,取q1為匿名區(qū)域(密集環(huán)境q1～q8誤差相差甚小,無論哪個匿名區(qū)都可以;稀疏環(huán)境q1的誤差最小,所以綜合選擇q1為匿名區(qū)).

比較圖6(a)和圖6(b)兩圖,不同h在landmark和storage數(shù)據(jù)集中平均方差相似,表示樹高對不同密度環(huán)境的影響較小.隨著隱私預(yù)算ε增大,誤差越小.隨著樹高h(yuǎn)的增加,誤差逐漸增加并呈指數(shù)函數(shù)增長,這是因?yàn)檎`差公式E(Q)與樹高h(yuǎn)呈指數(shù)關(guān)系,并且分配較小的h具有較低的誤差.

圖6 樹高h(yuǎn)對查詢誤差的影響Fig.6 Influence of tree height h on query error

5.4 匿名集規(guī)模k在不同隱私預(yù)算下對查詢誤差的影響

該實(shí)驗(yàn)只在landmark數(shù)據(jù)集中比較,因?yàn)閟torage數(shù)據(jù)集太小而無法從中受益.同時,引入差分隱私最基本的算法(稱Dwork算法)以及對提高差分隱私查詢精度有代表性的哈爾小波零樹壓縮算法(稱EHWT-DP算法),與本文MATDP算法進(jìn)行誤差的比較.根據(jù)前兩節(jié)的實(shí)驗(yàn)結(jié)論,該實(shí)驗(yàn)取δ=100,h=3,匿名區(qū)q1.

圖7中整體看得出,MATDP算法誤差在ε=0.1時要比ε=1時高出102倍.當(dāng)k值較小時,Dwork算法誤差要小于其他兩種算法.但隨著k值增大(查詢范圍也逐漸增大),Dwork算法誤差呈線性累加地增大,MATDP算法的誤差較小,且與EHWT-DP算法相比較具有更低的查詢誤差.同時,在圖中可看出,MATDP算法誤差雖然隨著查詢范圍的增加而增加,但會逐漸趨于穩(wěn)定,這是由于該算法的隱私預(yù)算分配有誤差上界.

5.5 算法運(yùn)行效率

該實(shí)驗(yàn)分別對landmark數(shù)據(jù)集取δ=100,storage數(shù)據(jù)集取δ=60,同時h=3,k=180,匿名區(qū)q1(該數(shù)據(jù)的選取參考上述實(shí)驗(yàn)結(jié)論),分別在不同ε值下比較三種算法的運(yùn)行效率.

圖7 匿名集規(guī)模k對查詢誤差的影響Fig.7 Impact of anonymous set size k on query error

由圖8可知,在相同數(shù)據(jù)集下不同的ε值每種算法的運(yùn)行時間基本相同,表示隱私預(yù)算ε不影響算法效率.Dwork算法運(yùn)行時間最短,其次MATDP算法相較于EHWT-DP算法運(yùn)行效率較高.是因?yàn)镋HWT-DP算法對數(shù)據(jù)轉(zhuǎn)換成小波樹的形式后還需將數(shù)據(jù)壓縮,再添加噪聲,算法復(fù)雜度為O(klogk),而MATDP算法復(fù)雜度為O(k).整體來看,storage數(shù)據(jù)集下三種算法運(yùn)行效率高于landmark數(shù)據(jù)集,這是由于δ值和k值一定時,較密環(huán)境生成的匿名區(qū)面積整體要小于稀疏環(huán)境的匿名區(qū),查詢時速度較快.

圖8 算法運(yùn)行效率Fig.8 Algorithm operating efficiency

6 結(jié)束語

基于位置的服務(wù)給生活帶便利的同時位置隱私問題也是不容小覷.本文在Hilbert曲線構(gòu)建的滿足相互性的k匿名集基礎(chǔ)上,通過改進(jìn)原始差分隱私方法在連續(xù)查詢下噪聲過大的問題,提出了基于m叉平均樹的差分隱私保護(hù)方法,該方法使用m叉平均樹結(jié)構(gòu)拆分匿名集數(shù)據(jù)以增強(qiáng)數(shù)據(jù)效用,并通過嚴(yán)密推導(dǎo)出具有較小誤差上界的拉普拉斯隱私預(yù)算分配策略.從閾值δ、匿名集規(guī)模k、匿名區(qū)域大小、樹高h(yuǎn)、隱私預(yù)算ε以及興趣點(diǎn)分布密度等方面測試了算法對誤差的影響.并且與同類提高查詢精度的差分隱私方法相比,具有高效的運(yùn)行效率.但在較小范圍中,查詢精度不太高,在未來的研究中,還要致力于在小范圍中對算法查詢精度的提高.