張麗平 ，楊 玉 ，金飛虎 ，李 松 ，郝忠孝 ,2

（1. 哈爾濱理工大學計算機科學與技術學院，黑龍江 哈爾濱 150080；2. 哈爾濱工業(yè)大學計算機科學與技術學院，黑龍江 哈爾濱 150001）

Skyline 查詢是解決計算機多目標優(yōu)化問題的一類重要方法，由Borzony 等[1]提出，目前在位置導航、數(shù)據(jù)挖掘和推薦算法中具有越來越廣泛的應用[2-5]. 盡管skyline 查詢機制從理論上講能夠保證隱私，但在實踐中，攻擊者通過重復攻擊仍然可以獲得個人信息[6]. 因此，需要進一步研究該機制中防止重復攻擊的問題. skyline 查詢的結(jié)果為沒有被其他任何點支配的對象，也正是因為這一特性，用戶的隱私容易泄露[7]. 為進行數(shù)據(jù)的隱私保護，Dwork[8]提出了一種基于差分隱私保護的方法，通過對數(shù)據(jù)進行一般的統(tǒng)計分析，為隱私保護提供定量的評估技術，從而實現(xiàn)差分隱私保護的功能. 文獻[9]提出了一種操作方便、定量準確的方法，可以在執(zhí)行獨立的差異私有機制的過程中跟蹤累積的隱私損失. 文獻[10]提出了一種基于環(huán)境中整體跡線和已發(fā)布跡線之間相互聯(lián)系的方法，該方法可以在給定查詢約束的情況下將跡線隱私泄漏的幾率最小化. 文獻[11]提出了一種設置線性查詢數(shù)量上限的方法，該方法能夠找到最優(yōu)的線性查詢. 基于差分隱私的查詢機制有兩種，分別是拉普拉斯機制[12]和指數(shù)機制[13]，基于差分隱私的數(shù)據(jù)挖掘方法廣泛應用于頻繁模式挖掘[14]、MapReduce 大數(shù)據(jù)分析查詢[15]、智能權重截取算法[16]和智能電網(wǎng)[17].

為了解決差分隱私保護機制中重復攻擊會泄露用戶隱私的問題，國內(nèi)外研究人員提出了許多解決方法. 文獻[18]為解決二維多媒體數(shù)據(jù)不均勻和精度降低的問題，提出了一種基于標準偏差圓半徑的差分隱私噪聲動態(tài)分配算法. 文獻[19]使用傳統(tǒng)搜索未涵蓋的屬性關聯(lián)來調(diào)查新的隱私威脅，通過配置差異隱私的噪聲參數(shù)來減輕周期滑動推理攻擊對差分隱私的影響. 文獻[20]通過對樣本數(shù)據(jù)進行訓練，獲得一個對抗性網(wǎng)絡數(shù)據(jù)模型，將噪聲數(shù)據(jù)添加到真實數(shù)據(jù)集中，可以在高斯分布下實現(xiàn)不同等級的隱私保護. 文獻[21]提出了一種用于位置數(shù)據(jù)隱私的隱私保護方法，該方法可滿足不同的隱私約束. 但是，目前這些方法都無法滿足skyline 查詢中隱私保護的要求，并且無法動態(tài)設定隱私預算值以實現(xiàn)不同等級的隱私保護級別. 文獻[22]提出了一種設定查詢上限的高效方法，通過計算準確性的期望值與可用于補償個人的預算值之間的平均值來確定計算查詢上限. 文獻[23]提出了一種基于環(huán)境中整體跡線和已發(fā)布跡線之間的相互聯(lián)系的方法，通過計算整體位置跡線的隱私度量值來確定接下來最優(yōu)的位置跡線方案，該方法可以在給定查詢約束的情況下將跡線隱私泄漏幾率最小化. 文獻[24]提出了一種設置線性查詢數(shù)量上限的方法，通過找到最優(yōu)的線性查詢，設置查詢數(shù)量的上限，使得最優(yōu)的線性查詢也無法泄露過多的隱私. 但是仍然無法在分級查詢中動態(tài)改變隱私預算值的同時對查詢次數(shù)的上限進行調(diào)整.因此，文獻[25]提出了一種有效且可保護隱私的在線醫(yī)療基礎診斷框架，在該框架內(nèi)通過skyline 查詢，用戶可以準確訪問在線醫(yī)療診斷服務，而無需泄露他們的醫(yī)療數(shù)據(jù).

綜上所述，針對傳統(tǒng)skyline 查詢方法無法有效地解決用戶隱私泄露的問題，提出了一種基于差分隱私保護的skyline 查詢方法. 本文的主要貢獻包括3 個方面：

1） 為提高skyline 查詢的效率，提出最優(yōu)主導頁的概念. 最優(yōu)主導頁能夠針對skyline 查詢結(jié)果的分頁特性，確定查詢范圍的數(shù)據(jù)隱私保護等級. 針對skyline 查詢的特性提出頁敏感度的概念，頁敏感度能夠滿足ε-差分隱私.

2） 為解決因噪音導致有效查詢結(jié)果的范圍無法量化的問題，引進置信區(qū)間和置信率的概念；為解決不同信任等級的用戶查詢結(jié)果相同會泄露數(shù)據(jù)隱私的問題，提出一種基于置信率的隱私預算值調(diào)節(jié)方法，對不同的信任等級的用戶設定不同的隱私預算值，實現(xiàn)數(shù)據(jù)的分級保護.

3） 為解決攻擊次數(shù)過多導致用戶隱私泄露的問題，提出調(diào)整隱私預算和置信率，限制查詢次數(shù)的策略，從而保護隱私數(shù)據(jù).

1 基本定義

定義1全局敏感度[12]. 設有函數(shù)f：T→Rd，T為輸入數(shù)據(jù)集，輸出為d維實數(shù)向量. 對于T的任意鄰近數(shù)據(jù)集Ta，函數(shù)f的全局敏感度GSf= max{T,Ta} ||f(T) -f(Ta) ||1，其中，||f(T) -f(Ta) ||1是f(T) 和f(Ta) 之間的1-階范數(shù)距離，表示相差的個數(shù)，這里個數(shù)只能為1，若 ||f(T)-f(Ta) ||1=1，表示相差一個.

函數(shù)的全局敏感度由函數(shù)本身決定，不同的函數(shù)會有不同的全局敏感度. 一些函數(shù)具有較小的全局敏感度，因此，只需加入少量噪聲即可掩蓋因一個記錄被刪除對查詢結(jié)果所產(chǎn)生的影響，從而實現(xiàn)差分隱私保護. 但是仍然無法滿足某些需求，例如求平均值和中位數(shù)等函數(shù)，則具有較大的全局敏感度. 此時，敏感度可能是一個很大的值，無法滿足隱私保護的要求. 為解決該問題，進一步提出了頁敏感度的概念.

定義2頁敏感度. 設有函數(shù)f：T→Rd，T為一個輸入數(shù)據(jù)集，輸出為d維實數(shù)向量，對于輸入數(shù)據(jù)集T和任意的鄰近數(shù)據(jù)集Ta，LSf(T) = max{Ta}×||f(T) -f(Ta) ||1，稱為函數(shù)f在數(shù)據(jù)集T上的頁敏感度.

為進一步調(diào)節(jié)頁敏感度，合理設置隱私預算的值，引入了基于差異化拉普拉斯分布的置信區(qū)間和置信率的概念. 置信區(qū)間和置信率與隱私預算有關，隱私預算的大小決定隱私保護的效果，如果所添加的噪聲是有效的，則一次查詢無法獲得用戶的隱私.但是，如果攻擊者進行多次重復攻擊，并且噪聲分布符合拉普拉斯分布，實際結(jié)果就會在某一個區(qū)間. 為進一步量化該區(qū)間范圍，給出置信區(qū)間的定義如定義3 所示.

定義3置信區(qū)間. 符合拉普拉斯分布的噪聲在某一個區(qū)間范圍內(nèi)，如果用 φ 代表置信區(qū)間的一半長度，則 [ -φ,φ] 為置信區(qū)間[24].

由拉普拉斯分布知置信區(qū)間是對稱的，則可以推斷出被攻擊數(shù)據(jù)的私有數(shù)據(jù)，并且可以通過累計函數(shù)計算攻擊的成功率A(T)，實際結(jié)果為

式中：ε為隱私預算值； Δf為全局敏感度； L(·) 為拉普拉斯變換.

L(ε/Δf) 的置信區(qū)間為[ μ-φ, μ+φ] ，其中，μ為位置參數(shù)，是相對于參數(shù) φ 對稱的未知參數(shù). 為量化計算結(jié)果在置信區(qū)間的概率，進一步給出了置信率的概念，如定義4 所示.

定義4置信率.f(T)的查詢結(jié)果落在置信區(qū)間[μ-φ, μ+φ]的概率為置信率，則置信率通過累計函數(shù)計算為[24]

根據(jù)置信率進一步量化隱私預算值ε的上界，設p為隱私泄露的概率，則

隱私預算值上界可以限制隱私預算值的大小，并且與置信率相關. 查詢結(jié)果有兩種可能性，分別是查詢結(jié)果落在置信區(qū)間和查詢結(jié)果不落在置信區(qū)間，兩種結(jié)果互斥. 設攻擊者進行查詢的總次數(shù)為C，在置信區(qū)間內(nèi)的查詢結(jié)果次數(shù)為m，m為大于0 的整數(shù)，則攻擊成功的概率為

因此，若對攻擊者的成功率進行限制，使其不大于某個閾值，則能夠確定隱私預算的取值范圍. 隱私預算ε的選擇與查詢的頁敏感度LSf(T)、攻擊者的總查詢次數(shù)C、置信區(qū)間 [ -φ, φ] 和攻擊成功率pc有關，隱私預算取值范圍的計算如式（5）所示.

理想的情況下，成功的事件和不成功的事件互斥，ε的值接近1/2 時，則成功率近似為50%. 假設置信區(qū)間為 [ 1/2-ω,1/2+ω] ，其中，ω為用戶設定的成功率參數(shù)，取決于數(shù)據(jù)的隱私性和能夠承受攻擊的上限. 當查詢結(jié)果在置信區(qū)間的成功率大于1/2 時，可對頁敏感度進行調(diào)整，即降低頁敏感度，增加隱私保護等級，因此，置信區(qū)間成功率可以控制在用戶設定的 [ 1/2-ω,1/2+ω] 區(qū)間內(nèi).

最后，為對skyline 的查詢結(jié)果進行優(yōu)化，給出最優(yōu)主導頁的概念如定義5 所示.

定義5最優(yōu)主導頁. 根據(jù)支配頁將skyline 查詢的輸入數(shù)據(jù)集T分為h個子數(shù)據(jù)集Tsub1,Tsub2, … ,Tsubh，在一次具體查詢中，如果查詢數(shù)據(jù)集為部分子數(shù)據(jù)集Tsubk,Tsubk+1, … ,Tsubk+z，其中k和z為正整數(shù)且0 ＜k+z≤h，則該查詢的最優(yōu)主導頁為Tsubk.

2 基于差分隱私保護的skyline 查詢方法

skyline 查詢結(jié)果通常是隱私數(shù)據(jù)，故用戶的隱私更容易泄露. 為保護用戶隱私，提出了基于差分隱私保護的skyline 查詢方法，所提方法的主要思想為：根據(jù)查詢對象的范圍確定查詢的最優(yōu)主導頁，從而確定頁敏感度；根據(jù)查詢者的查詢范圍、查詢次數(shù)評估查詢者的信任等級，限制查詢次數(shù)；根據(jù)頁敏感度和信任等級進一步確定隱私預算，給出查詢結(jié)果.

2.1 最優(yōu)主導頁的計算方法

最優(yōu)主導頁是指在一次skyline 查詢范圍中，隱私最容易被泄露的某一頁查詢結(jié)果. 最優(yōu)主導頁的計算過程為：首先，通過skyline 查詢獲得查詢結(jié)果，將隱私最容易被泄露的某一頁查詢結(jié)果確定為最優(yōu)主導頁；其次，遍歷數(shù)據(jù)集并實時更新查詢結(jié)果；后續(xù)依據(jù)查詢范圍的改變再動態(tài)更新最優(yōu)主導頁. 如圖1 所示，圖中，Pt、Oy分別為第t頁、第y個對象.

圖1 skyline 分頁查詢示例Fig. 1 skyline paged query

首先，利用skyline 分頁查詢對所有的數(shù)據(jù)點進行分頁，查到每一頁所有不被支配的數(shù)據(jù)點，每一頁為一個隱私泄露等級的子數(shù)據(jù)集.

第一頁的第一個對象記為(P1,O1)，第一頁的對象子數(shù)據(jù)集為{(P1,O1), (P1,O2), (P1,O3), (P1,O4),(P1,O5)}，以此類推，每一頁查詢結(jié)果如表1 所示.

表1 skyline 分頁查詢結(jié)果Tab. 1 Skyline paged query results

根據(jù)所有對象的屬性向量計算第i（i= 1, 2, …）頁skyline 查詢結(jié)果，第1 頁為首次查詢確定的最優(yōu)主導頁，每一次查詢的最優(yōu)主導頁都代表最容易泄露當前數(shù)據(jù)隱私的子數(shù)據(jù)集.

2.2 頁敏感度的計算方法

在skyline 查詢過程中，局部敏感度計算的過程比較復雜，全局敏感度無法對子集進行分類保護；查詢次數(shù)和查詢結(jié)果的隱私泄露程度具有正相關性，頁敏感度能夠調(diào)節(jié)兩者相關性的大小.

基于差分隱私保護的查詢通過添加噪音干擾查詢結(jié)果，從而保護用戶隱私. 查詢機制有兩種，分別是拉普拉斯機制和指數(shù)機制，其中拉普拉斯機制是一種噪音干擾機制，噪音是一種滿足拉普拉斯分布（Laplace distribution）的函數(shù). 基于拉普拉斯機制的skyline 查詢的頁敏感度為LSf(T)時，滿足ε-差分隱私.

基于以上論述，所提計算頁敏感度算法 （page sensitivity calculation algorithm，PSC_A）的主要思想為：首先，在預處理階段通過skyline 查詢結(jié)果初步確定第一次查詢的最優(yōu)主導頁，并計算頁敏感度；其次，在每次查詢時遍歷數(shù)據(jù)集，將當前計算的頁數(shù)與最優(yōu)主導頁進行比較，更新最優(yōu)主導頁，最終，輸出頁敏感度的值. PSC_A 如算法1 所示.

算法1PSC_A /*頁敏感度計算算法*/

輸入：數(shù)據(jù)集T.

輸出：頁敏感度LSf(T).

1） 執(zhí)行skyline 查詢，通過skyline 查詢結(jié)果初步確定第一次查詢的最優(yōu)主導頁；

2） 對skyline 查詢數(shù)據(jù)集T進行遍歷，計算每一個對象的頁數(shù)；

3） 將當前計算的頁數(shù)與最優(yōu)主導頁進行比較；

4） 如果當前數(shù)據(jù)對象的頁數(shù)小于最優(yōu)主導頁，則更新最優(yōu)主導頁；

5） 計算當前最優(yōu)主導頁的頁敏感度LSf(T)；

6） 返回頁敏感度LSf(T).

2.3 基于置信率的隱私預算值調(diào)節(jié)方法

針對不同的隱私泄露等級的子數(shù)據(jù)集，為了差異性地保護隱私，利用基于拉普拉斯分布的差分隱私保護機制保護數(shù)據(jù)隱私. 傳統(tǒng)的隱私保護方法可以通過引入隨機性增加干擾，達到對隱私的有效保護. 設x為查詢參數(shù)變量，Nnoise是服從某種隨機分布的噪聲，則f(x) ＝Ccount(x) +Nnoise，其中，Ccount(x)為針對x的統(tǒng)計函數(shù). 在傳統(tǒng)的差分隱私保護方法中，無法對輸出的結(jié)果進行特定的處理，針對skyline 分頁查詢結(jié)果集中的數(shù)據(jù)隱私保護等級不同的問題，為進一步對不同隱私等級的數(shù)據(jù)進行分級調(diào)節(jié)，提出基于置信率的隱私預算值調(diào)節(jié)方法.

利用拉普拉斯機制執(zhí)行ε-差分隱私保護，將滿足拉普拉斯分布的隨機噪聲添加到查詢結(jié)果中，拉普拉斯機制滿足

拉普拉斯噪聲計算公式為

式中：b＞ 0 為尺度參數(shù).

設b=ε/ Δf， μ = 0，則

對于任意絕對值變量，累計函數(shù)為

添加的噪聲大小與隱私預算值ε和 Δf密切相關，ε的取值越小，隱私保護效果越好，但是數(shù)據(jù)的有效性越低；ε的取值越大，數(shù)據(jù)的隱私保護則效果越差，但是數(shù)據(jù)的有效性越高. 基于以上論述分析，所提出的基于置信率的隱私預算值調(diào)節(jié)算法（privacy budget adjustment algorithm for confidence rate，PBAACR_A）如算法2 所示.

算法2PBAACR_A /*隱私預算值調(diào)節(jié)算法*/

輸入：查詢數(shù)據(jù)集T, 置信區(qū)間[1/2-ω,1/2+ω]，查詢次數(shù)C.

輸出：隱私預算值.

1） 調(diào)用PSC_A 算法計算頁敏感度；

2） 針對置信區(qū)間 [ 1/2-ω,1/2+ω] ，利用頁敏感度和式（2）計算置信率；

3） 利用式（3）計算隱私預算值；

4） 基于拉普拉斯機制執(zhí)行ε-差分隱私，利用拉普拉斯噪聲計算公式（式（7））將滿足拉普拉斯分布的隨機噪聲添加到查詢結(jié)果中；

5） 對置信區(qū)間 [ 1/2-ω,1/2+ω] 的隱私預算值進行判斷，如果滿足該置信區(qū)間的置信率要求，則輸出隱私預算值；否則，隱私預算值設置為0.

2.4 基于差分隱私保護的skyline 查詢算法

基于頁敏感度計算和隱私預算值調(diào)節(jié)方法，針對skyline 查詢的次數(shù)過多導致用戶隱私可能泄露的情況，可采取限制用戶查詢次數(shù)的策略加大隱私保護力度. 在置信區(qū)間為 [ 1/2-ω,1/2+ω] 的情況下可根據(jù)隱私預算值和全局敏感度計算出置信率. 查詢結(jié)果滿足ε-差分隱私的查詢次數(shù)上限設為c，當查詢次數(shù)達到c時，需要對用戶信任等級和隱私參數(shù)重新計算，再利用PBAACR_A算法對隱私預算值進行調(diào)節(jié)，最終得到滿足隱私保護要求的skyline查詢結(jié)果.

進一步給出基于差分隱私保護的skyline 查詢算法（skyline query algorithm for differential privacy protection，SQADP_A ），該算法首先計算隱私預算值；其次，基于隱私預算值更新查詢次數(shù)上限；對每次查詢結(jié)果進行判斷；查詢完成后再計算頁敏感度；最后，利用拉普拉斯機制添加噪音，輸出skyline 查詢結(jié)果. SQADP_A 如算法3 所示.

算法3SQADP_A /*基于差分隱私保護的skyline 查詢算法*/

輸入：查詢數(shù)據(jù)集T，置信區(qū)間 [ 1/2-ω,1/2+ω] ，查詢總次數(shù)C，滿足ε-差分隱私的查詢次數(shù)最大值c.

輸出：skyline 查詢結(jié)果.

1） 調(diào)用PBAACR_A 算法得出隱私預算值；

2） 判斷隱私預算值，若隱私預算值為0，則更新查詢次數(shù)上限，重新計算隱私預算值；若隱私預算值不為0，則增加查詢次數(shù)；

3） 基于置信區(qū)間 [ 1/2-ω,1/2+ω] 計算置信率；

4） 遍歷查詢數(shù)據(jù)集T中的所有子數(shù)據(jù)集；

5） 針對相鄰子數(shù)據(jù)集進行skyline 查詢，得到查詢結(jié)果集；

6） 計算頁敏感度；

7） 利用拉普拉斯機制，根據(jù)隱私預算值和頁敏感度對查詢結(jié)果集添加噪音；

8） 發(fā)布skyline 查詢結(jié)果.

3 實驗評估

3.1 實驗環(huán)境

為更好地保護隱私，本實驗加入人工合成的人名、性別和年齡等信息. 人名為隨機生成的3 個漢字，性別為男或者女，年齡為0 ～ 100 周歲的整數(shù)，符合正態(tài)分布. 實驗環(huán)境為Microsoft Windows 10，Core (TM) i7- 3537U CPU@ 2.00 GHz （2 501 MHz）處理器，4 GB 內(nèi)存. 假設人名、性別和年齡均為隱私數(shù)據(jù)，本實驗分析skyline 查詢的效率、查詢結(jié)果的可靠性以及查詢結(jié)果的隱私泄露程度.

為構(gòu)造對比算法，對文獻[20]所提算法和文獻[21]所提算法的關鍵步驟進行適當?shù)男薷? 在文獻[20]所提算法進行剪枝之前增加了最優(yōu)主導頁的計算，并將敏感度更改為頁敏感度，簡稱為OGWP （optimizing GAN obfuscator with pruning）算法；在文獻[21]所提算法進行信息熵的計算之前增加最優(yōu)主導頁的計算，并將敏感度的計算更改為動態(tài)調(diào)節(jié)敏感度，簡稱為FOQIL （find the optimal quantization interval length）算法. 本節(jié)將本文所提SQADP_A 算法與OGWP 算法、FOQIL 算法進行對比實驗，驗證所提算法的可行性和有效性.

3.2 實驗結(jié)果分析

實驗1本實驗主要對比3 種算法的數(shù)據(jù)規(guī)模對算法執(zhí)行時間的影響. 圖2 展示了數(shù)據(jù)集對象數(shù)量從64 kB 增長到1 024 kB 時3 種算法的查詢效率對比結(jié)果，分別分析數(shù)據(jù)規(guī)模的不同對CPU 運行時間的影響. 由于剪枝算法能夠剪掉一部分無效對象，且最優(yōu)主導頁是動態(tài)更新的，所以3 種算法在數(shù)據(jù)規(guī)模較小的時候相差不大，但是隨著數(shù)據(jù)規(guī)模的增加，F(xiàn)OQIL 算法需要額外處理的數(shù)據(jù)量較多，因此，對很多無效的對象進行最優(yōu)主導頁和信息熵的計算量也增加，查詢效率相對較低. 梯度修剪策略由于沒有涉及到大量的復雜計算，而是基于高斯分布針對不同場景進行差異化剪枝，因此，OGWP 算法效率較高.

圖2 數(shù)據(jù)規(guī)模對查詢效率的影響Fig. 2 Effect of data size on query efficiency

實驗2本實驗主要評估數(shù)據(jù)規(guī)模對查詢結(jié)果可靠性的影響. SQADP_A 算法依據(jù)剪枝規(guī)則和存在概率排序規(guī)則進行查詢. 實驗中數(shù)據(jù)項泄露數(shù)為結(jié)果集中隱私數(shù)據(jù)數(shù)量，因變量為數(shù)據(jù)集的規(guī)模，在5 個不同規(guī)模的數(shù)據(jù)集上進行查詢. 如圖3 所示，因為每次skyline 查詢的結(jié)果輸出后，才作為計算頁敏感度的剪枝結(jié)果，所以SQADP_A 算法的輸出結(jié)果集的無效數(shù)據(jù)最少. 與SQADP_A 算法相比，F(xiàn)OQIL 算法的查詢結(jié)果隱私項較少，隱私保護等級較高，但是由于涉及到大量的計算，查詢效率較低.OGWP 算法輸出結(jié)果的隱私數(shù)據(jù)數(shù)量高于FOQIL算法和SQADP_A 算法，隱私保護效果最差. 因此，由實驗結(jié)果可知：如果不考慮查詢時間的影響，F(xiàn)OQIL 算法和SQADP_A 算法更能保護用戶隱私.此外，雖然FOQIL 算法和SQADP_A 算法的隱私保護等級相差不大，但是，SQADP_A 算法的查詢速度更快. 因此，隨著數(shù)據(jù)規(guī)模的增加，SQADP_A 算法能在查詢速度較快的情況下增強查詢結(jié)果的隱私保護.

圖3 數(shù)據(jù)規(guī)模對查詢結(jié)果可靠性的影響Fig. 3 Effect of data size on the reliability of query results

實驗3本實驗評估了隱私預算值調(diào)節(jié)策略和梯度修剪策略對算法輸出結(jié)果集的隱私泄露程度的影響. 實驗中采用控制變量法保證隱私預算值計算的策略不同，結(jié)果如 圖4 所示. 由圖4 可知：兩種查詢算法在skyline查詢過程中采用不同的策略，其查詢結(jié)果集中的有效的隱私泄露數(shù)具有顯著差異；隱私預算值調(diào)節(jié)策略更適應于對skyline 查詢隱私保護要求較高的場所，skyline 查詢的查詢結(jié)果為沒有被其他任何點支配的對象，關于skyline 查詢的查詢結(jié)果通常是隱私數(shù)據(jù)，因此，這種方式可以用較小的時間代價換取隱私保護等級的增加；而梯度修剪策略雖然具有較快的查詢速度，但是隱私泄露程度隨著數(shù)據(jù)規(guī)模的增加而快速增加. 故如果對skyline查詢結(jié)果的隱私保護有較高要求則可以采用隱私預算值調(diào)節(jié)策略，對查詢速度有較高要求則可以采用梯度修剪策略.

圖4 兩種策略對查詢結(jié)果隱私泄露程度的影響Fig. 4 Effect of two strategies on the degree of privacy disclosure of query results

實驗4本實驗評估了3 種算法中的隱私預算值設定對skyline 查詢結(jié)果集中隱私泄露程度的影響，數(shù)據(jù)規(guī)模為256 kB，隱私預算值分別設為10.0、5.0、0.8、0.5、0.4，實驗結(jié)果如圖5 所示. 由實驗結(jié)果可知：隱私預算值設定較低的情況下3 種算法的隱私泄露程度沒有明顯的區(qū)別，3 種算法在隱私預算設定為0.4 時的隱私泄露的差距較小，但是隨著隱私預算值設定值的增加，SQADP_A 算法的隱私泄露程度逐漸收斂，并且在隱私預算值較?。ㄐ∮?.0）的情況下，SQADP_A 算法的隱私保護效果最好. 隱私預算設定值為10.0 時，OGWP 算法的隱私泄露程度較高，隨著隱私預算值的增加，F(xiàn)OQIL 算法的隱私保護效果有降低的趨勢.

圖5 隱私預算值對隱私泄露程度的影響Fig. 5 Effect of privacy budget value on privacy disclosure

實驗5本實驗評估了3 種算法中的隱私預算值設定對skyline 查詢結(jié)果集中準確率的影響，實驗結(jié)果如圖6 所示. 由圖6 可知：隱私預算值設定較低的情況下，OGWP 算法的查詢準確率最低；隨著隱私預算值的增加，OGWP 算法的隱私保護效果變差，OGWP 算法的查詢準確率卻有所提高. 在隱私預算值設定較低的情況下，SQADP_A 算法的查詢準確率最高，當隱私預算設定為0.8 以內(nèi)時其查詢準確率沒有明顯的變化，當隱私預算值設定大于0.8 時，查詢準確率有明顯變高的趨勢. FOQIL 算法在隱私預算設定較低的時候也有較高的準確率，隱私預算值設定為0.8 以內(nèi)時，準確率變化依舊不明顯，甚至有降低的趨勢；當隱私預算的值大于0.8 后準確率逐漸增加. 由實驗可知：在skyline 查詢結(jié)果中，SQADP_A 算法的準確率相對最高.

圖6 隱私預算值對skyline 查詢結(jié)果集中準確率的影響Fig. 6 Effect of privacy budget value on the accuracy of skyline query result set

4 結(jié) 論

skyline 查詢的隱私保護問題受到越來越廣泛的關注，差分隱私能夠有效地保護skyline 查詢結(jié)果中不同子結(jié)果頁的隱私. 本文研究了基于差分隱私保護的skyline 查詢方法，提出了有效的頁敏感度計算方法和隱私預算值調(diào)節(jié)策略. 頁敏感度的計算能夠有效地適用于skyline 查詢方法，基于置信率和置信區(qū)間的隱私預算值調(diào)節(jié)策略確保了數(shù)據(jù)對象的有效性. 最后給出了基于拉普拉斯機制進行查詢結(jié)果隱私保護的SQADP_A 算法. 通過實驗表明：所提方法能減少skyline 查詢結(jié)果的隱私泄露數(shù)量，為用戶提供有效的隱私保護. 未來將深入研究不確定高維skyline 查詢過程中的數(shù)據(jù)隱私問題，使得在執(zhí)行多次查詢時，查詢結(jié)果不僅能保證數(shù)據(jù)的有效性，也能保證數(shù)據(jù)的隱私性.