異方差加噪下的差分隱私直方圖發布算法*

康　健，吳英杰，黃泗勇，陳　鴻，孫　嵐福州大學 數學與計算機科學學院，福州 350116

?

異方差加噪下的差分隱私直方圖發布算法*

康健，吳英杰+，黃泗勇，陳鴻，孫嵐
福州大學 數學與計算機科學學院，福州 350116

KANG Jian,WU Yingjie,HUANG Siyong,et al.Algorithm for differential privacy histogram publication with non-uniform private budget.Journal of Frontiers of Computer Science and Technology,2016,10(6):786-798.

摘要：現有基于區間樹結構的差分隱私直方圖發布方法大多采用同方差加噪方式，對其進一步研究發現，采用異方差加噪策略可以進一步提升發布直方圖的區間計數查詢精度，然而當前基于異方差加噪的差分隱私直方圖發布方法對區間樹結構卻有嚴格的要求，導致靈活性與實用性較低。為此，提出了一種異方差加噪下面向任意區間樹結構的差分隱私直方圖發布算法LUE-DPTree（inear unbiased estimator for differential private tree）。首先根據區間計數查詢的分布，計算區間樹中節點的覆蓋概率，并據此分配隱私預算，實現異方差加噪；接著經分析指出該異方差加噪策略適用于任意區間樹結構，且從理論上證明了在任意區間樹結構下進行異方差加噪后，仍可在一致性約束下利用最優線性無偏估計進一步降低區間計數查詢的誤差。針對算法的區間計數查詢精度及執行效率，與同類算法進行了比較分析。實驗結果表明，LUE-DPTree算法是有效可行的。

關鍵詞：隱私保護；差分隱私；直方圖發布；異方差加噪；區間樹

ISSN 1673-9418CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(06)-0786-13

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056

1　引言

隨著信息技術的發展，大量數據的收集與發布在促進科學技術進步的同時，也帶來了隱私信息泄露的問題。因此，數據發布隱私保護成為現今一項熱門的研究課題。

近年來，在數據發布隱私保護領域，研究人員開展了一系列的研究，主要可分為數據加密、限制發布和數據擾亂等方面[1-3]，包括k-anonymity[4]、l-diversity[5]等保護方法。其中，Dwork[6]提出了差分隱私保護模型。該模型采用了嚴格的量化評估標準，能夠實現有效的隱私保護，并保證較高的數據可用性。此后，研究人員在差分隱私保護的各個領域展開了大量研究，其中包括差分隱私直方圖發布方法的研究[7-15]，主要包含層次樹變換、聚類變換和傅里葉變換等[3]。本文主要針對層次樹變換中基于區間樹的差分隱私直方圖發布方法進行討論。

現有基于區間樹的差分隱私直方圖發布方法大多采用同方差的加噪方式。Hay等人[8]建立了差分隱私區間樹，并進行了同方差加噪與一致性調節。Xu等人[9]提出了StructureFirst，優化直方圖劃分策略，并在劃分區間后的構造區間樹中進行了同方差加噪。采用同方差加噪方式的發布方法有效提升了發布數據的可用性和算法效率。而實際上通過研究可以發現，若采用異方差加噪方式，可進一步提高發布精度。文獻[10]提出了通過迭代方式在區間樹進行層次間隱私預算分配的方法，有效降低了查詢誤差，但其在相同層次的節點中仍使用相同的隱私預算，因此仍具有進一步優化的空間。文獻[11]提出了DP-tree（differential private tree），通過異方差加噪，能夠對多維數據進行發布并提高查詢精度，但該方法采用了完全K叉樹結構，限制了樹結構調節的靈活性。

針對以上問題，本文提出了一種異方差加噪下，面向任意區間樹結構的差分隱私直方圖發布算法，以期進一步降低區間計數查詢誤差，提高發布數據的可用性。

2　基礎知識與問題

在現有差分隱私直方圖發布方法的研究中，主要通過重構直方圖結構來回答區間計數查詢，代表方法為基于差分隱私區間樹的發布方法。該方法利用區間樹結構重構原始直方圖，可有效提高發布數據的精確度和算法運行效率。

定義1（差分隱私區間樹[8]）對于給定計數直方圖H={C1,C2,…,Cn}，對H建立的差分隱私區間樹T滿足以下特性：

（1）非葉節點的兒子節點數大于等于2。

（2）每個節點x對應于H中的一個區間范圍，表示為[L(x),R(x)]，根節點所代表的區間為[1,n]。

定義2（同/異方差加噪方式[8,11]）給定區間樹T，通過噪聲機制[8]使每個節點x滿足εx-差分隱私。若對任意節點x、y，均有εx=εy，則稱作同方差加噪方式；若存在節點x、y，使得εx≠εy，則稱作異方差加噪方式。

如圖1，當ε=1.0時，在圖1（a）的同方差加噪方式下，區間樹的每個節點的隱私預算εx均為0.5。而在圖1（b）的異方差加噪方式中，節點1隱私預算為0.33，節點2、3、4的隱私預算均為0.67。由于通常情況下，區間樹中的各個節點被查詢區間覆蓋的頻率并不完全相同。例如在查詢區間隨機分布的情況下，節點2、3、4具有高于節點1的覆蓋概率（計算過程將在下文給出），因此在圖1（b）中能夠對多數高頻覆蓋節點添加更少的噪聲，對少數低頻覆蓋節點添加更多噪聲，從而降低整體區間計數查詢誤差。

Fig.1　Uniform/non-uniform private budget distribution圖1　同/異方差加噪下的隱私預算分配

定義3（查詢一致性約束[8]）在發布后的差分隱私區間樹T中，任意節點x的計數值應與其兒子節點的計數值總和相等，稱為查詢一致性約束：

其中，hˉ代表最終發布后節點的計數值；Son(x)為節點x的兒子節點集合。

現有基于區間樹結構的差分隱私直方圖發布方法大多采用同方差的加噪方式，少數采用異方差加噪的差分隱私直方圖發布方法對樹結構有著嚴格的要求。為此，本文的研究問題及目標是：對于給定的原始直方圖H，建立與其對應的差分隱私區間樹T，并通過異方差方式進行加噪；接著說明該加噪方式適用于任意區間樹結構，并利用查詢一致性約束條件進一步優化區間計數查詢精度；最后提出異方差加噪下面向任意區間樹結構的差分隱私直方圖發布算法LUE-DPTree，同時保證算法滿足ε-差分隱私。

3　異方差加噪下面向任意區間樹結構的差分隱私直方圖發布算法

為實現異方差加噪，首先需要解決區間樹中節點的覆蓋概率計算問題，并據此進行隱私預算分配。

3.1節點覆蓋概率計算

當對區間樹進行區間計數查詢時，其計數值為查詢區間[QL,QR]所覆蓋的多個節點計數值之和[8]。所覆蓋的節點互不相交，且并集等于查詢區間，因此被覆蓋節點x需滿足QL≤L(x)≤R(x)≤QR。同時，對任意一次查詢，若其父節點fx能被查詢區間覆蓋，節點x將被忽略，因此節點x被查詢區間覆蓋條件為：

當x為根節點時，因其父節點fx不存在，令QL≤L(fx)≤R(fx)≤QR為假。

本文假定所有查詢區間的出現概率相等。由式（1）可得出節點覆蓋概率px的計算公式：

根據式（2），可由算法1計算節點覆蓋概率。

算法1 CNCP（calculate node coverage probability）

輸入：待計算節點x及其父節點fx。

輸出：區間樹中所有節點的覆蓋概率px。

1.若x為根節點：

2.若x為其他節點：

3.對所有y∈Son(x)，執行CNCP(y,x)；

實際上，當查詢區間滿足其他分布特性時，通過對式（2）的調整，其節點覆蓋概率亦可通過本算法進行計算。算法1僅要求樹結構滿足區間樹定義，因此適用于任意樹結構的差分隱私區間樹。

3.2節點系數計算及隱私預算分配

在計算出節點覆蓋概率后，即可據此調整隱私預算，通過異方差加噪方式降低整體的查詢誤差。而在此之前，需分析如何保證異方差加噪后的差分隱私區間樹滿足ε-差分隱私。

證明 對任意節點x，設Sub(x)表示以節點x為根節點的子樹，A(x)表示對子樹Sub(x)進行發布的算法，則：

根據結論1，若要保證異方差加噪后的區間樹滿足ε-差分隱私，需滿足以下條件：

則區間計數查詢誤差期望：

因此，在滿足ε-差分隱私的前提下，求解區間樹上各節點的差分隱私預算，從而最小化區間計數查詢誤差期望的問題，可轉化為以下最優化問題：

其中，εˉ表示區間樹中節點的差分隱私預算向量。

下面通過定義4與結論2進行求解。

定義4（路徑隱私預算和）

結論2為最小化區間計數查詢誤差期望（即求解式（3）），區間樹中差分隱私預算分配方案需滿足：

稱ax、bx為節點x的節點系數，有:

證明（1）若x為葉節點，則結論2顯然成立。

（2）若x為非葉節點，利用拉格朗日乘數法，可構造如下函數：

其中，λ為引入的未知標量。因目標函數 f(ε)為凸函數，同時求解式（3）與求解函數F(εˉ,λ)的全局最優解等價，因此將F(εˉ,λ)對εˉ求導，得：

假設對于y∈Son(x)，結論均成立，則：

對于節點SonBound(x)和任意 y∈Son(x)，在式（3）約束條件下，任意葉節點到根節點路徑上的隱私預算和等于ε，因此：

由式（5）（6），得：

為滿足式（4），必有：

將式（7）代入式（8）可得：

因此：

令

綜合（1）（2），結論得證。

至此，可通過算法2計算節點系數ax、bx。

算法2 CNP（calculate node parameter）

輸入：待計算節點x。

輸出：區間樹中所有節點的節點系數ax、bx。

1.若x為葉節點：ax←1,bx←1；

2.若x為其他節點：

3.對于y∈Son(x),運行CNP(y);

計算出節點系數ax、bx后，可通過算法3分配每個節點的差分隱私預算εx并進行異方差加噪。

算法3 NPBD（non-uniform private budget distribution）

輸入：待加噪節點x，路徑隱私預算和psum(x)。

3.對所有y∈Son(x)，執行：

本文以圖1所示差分隱私區間樹為例，分析異方差加噪對區間計數查詢精度的影響。

將圖1所示區間樹通過算法1及算法2進行節點覆蓋概率和系數計算，結果如圖2所示。再通過算法3進行隱私預算分配，得到各節點的隱私預算：

Fig.2　Example of non-uniform private budget distribution圖2　異方差加噪示例

該方案與圖1（b）所示一致。分別對圖1（a）、圖1 （b）中的隱私預算分配方案計算區間計數查詢誤差期望：

查詢誤差期望由原先同方差加噪的10.67，降低至異方差加噪的8.25，查詢精度得到提高。

3.3異方差加噪下面向任意區間樹結構的差分隱私直方圖發布算法

上述步驟實現了對差分隱私區間樹進行的異方差加噪。由于僅要求樹結構滿足差分隱私區間樹定義，并無其他限定，該異方差加噪策略不僅適用于完全K叉樹，還能夠運用在任意區間樹結構上。

任意樹結構的差分隱私區間樹示例如圖3所示。

Fig.3　Range tree with different structures圖3　不同樹結構下的區間樹

圖3中，對于長度為22的直方圖數據集而言，可采用如圖3（a）的完全二叉樹進行統計表示，也可用類似于圖3（b）的任意樹結構差分隱私區間樹進行表示。對其分別計算區間計數查詢誤差期望：

可以看出，采用任意區間樹結構之后，可以對樹結構進行更靈活的調整，從而有效降低查詢誤差。結合異方差加噪方式，更能夠進一步提升查詢精度。

任意樹結構差分隱私區間樹的構建算法如下：

算法4 TSC（tree structure construct）

輸入：待構建子樹節點x，當前區間[l,r]。

輸出：差分隱私區間樹T。

在算法4中，對分支數K的選擇和子區間長度的分配方式上進行改變，均會導致樹結構的變化。樹結構構建完成并進行節點覆蓋概率計算（CNCP）、節點系數計算（CNP）和異方差加噪（NPBD）后，即可得到異方差加噪下的任意樹結構差分隱私區間樹。

在建立任意區間樹并進行異方差加噪后，可有效提高區間計數查詢精度。然而，通過如圖4的示例可以發現，加噪后的區間樹并不滿足一致性約束。

Fig.4　Example of consistency constraintafter adding noise圖4　加噪后造成的一致性約束問題示例

圖4中，未加噪區間樹（a）經加噪后，變為加噪區間樹（b），其父節點1的計數值10.5與子節點計數值之和9.3不同，不滿足一致性約束。以下將針對此問題，通過理論分析，證明異方差加噪下的任意區間樹，仍可利用一致性約束進行最優線性無偏估計優化。

結論4差分隱私區間樹從葉節點w到根節點路徑上的節點線性無偏估計值hˉ滿足下列公式：

證明 式(9)可轉換為求解下式：

對于任意葉節點w，對hˉw求偏導：

結論5以節點x為根節點的子樹中，節點x的估計值hˉx、葉節點到節點x的估計值加權和gˉx，均是關于葉節點的線性方程：

其中：

Bound(x)是以x為根節點的子樹中第一個葉節點，w= SonBound(x)。

證明 定義節點高度：

（1）若節點x∈{y|Height(y)=0}，即x∈Leaf(root)，結論5顯然成立。

（2）假設對任意節點y∈{y|Height(y)≤n}，式（11）均成立。當Height(x)=n+1時：

令hsum(x)表示從葉節點x到根節點路徑上節點集合的加噪值加權和，由結論4可知：

令w=SonBound(x)，由式（12）可知，對于節點y∈Son(x)，有Height(y)≤n，Height(w)≤n，且根據結論4，有：

代入式(11)可得：

由一致性約束可得：

綜合（1）（2），證明式（11）成立。

經由以上結論及證明，通過維護參數(α,β,c,d)的值，并利用式（11）進行估計值計算，設計了對差分隱私區間樹加噪后，在任意區間樹結構下，利用最優線性無偏估計進行調整的優化算法。

算法5 PA_BLUE（parameter adjust using best linear unbiased estimate）

輸入：待計算發布計數值的節點x。

輸出：區間樹所有節點的參數(α,β,c,d)。

1.若x為葉節點，更新：

并結束算法

計算參數(α,β,c,d)后，通過算法6計算優化后的最終發布值。

算法6 CRC（calculate range count）

輸入：待計算發布計數值的節點x，令tot為

輸出：區間樹所有節點的發布計數值hˉx。

通過以上步驟，本文提出了異方差加噪下，面向任意區間樹結構進行最優線性無偏估計優化的差分隱私直方圖發布算法。

算法7 LUE-DPTree（linear unbiased estimator for differential private tree）

輸入：原始直方圖H，差分隱私參數ε。

輸出：異方差加噪，任意樹結構的ε-差分隱私區間樹T_Publish。

下面對算法7的差分隱私保障和算法復雜度進行分析證明。

結論6算法7所生成的差分隱私區間樹T_publish滿足ε-差分隱私。

證明 對于區間樹T_Publish，由式（3）中的約束條件可知，在計算各節點隱私預算εx時，始終在該約束下進行：

由結論1可知，整體發布過程滿足ε-差分隱私。

結論7算法7的算法時間復雜度、空間復雜度均為O(n)。

證明 在算法7中，各步驟均為對區間樹進行一次掃描，時間復雜度為O(n)。在CNCP、CNP和PA_BLUE算法中，分別需存儲各節點的節點覆蓋概率、節點系數等值，空間復雜度為O(n)。在TSC、NPBC、CRC算法中，分別對樹節點的發布值進行計算及改變，空間復雜度同樣為O(n)。因此，算法7的時間、空間復雜度均為O(n)，為線性復雜度。

4　實驗結果與分析

本文從區間計數查詢精度和算法運行效率兩方面與同類代表算法Boost[8]進行對比分析。在文獻[10]中，提出了在區間樹的不同層次間進行異方差分配的迭代方法，本文將其應用于Boost算法中，并標識為Boost-UN。同時，為了更好地體現本文算法的有效性，實驗也與基于小波變換的Privelet[15]算法進行了比較分析。同樣采用了異方差加噪方式的算法DP-tree[11]，由于并未給出具體算法描述，從而未與其進行實驗對比。在實驗中，隱私參數ε取值分別為{1.0，0.1，0.01}。采用如式（13）所示的平均方差進行誤差衡量。為使實驗結果更具一般性，取算法執行50次的平均值作為最終結果。

其中，q(T)為區間計數查詢的真實結果；q(T′)為區間計數查詢的加噪計數值； ||Q為查詢集大小。

4.1實驗環境

為便于對比分析，采用了與文獻[8]相同的實驗數據集Social Network、Search Logs、NetTrace進行實驗。Social Network數據集記錄了某在線社交平臺的用戶關系無向圖中具有特點度的用戶數。Search Logs數據集統計了2004年1月至2009年8月期間，關于“Obama”關鍵詞的搜索頻率。NetTrace數據集對某大學在一個時間段內的IP數據包信息進行了記錄。其數據規模如表1所示。

實驗硬件環境為：Intel Core i7 930 2.8 GHz處理器，4 GB內存，Windows 7操作系統。算法實現采用C++語言，由Matlab生成實驗圖表。

Table 1　Dataset size表1 數據集規模

4.2查詢精度

本文通過與Boost、Privelet等算法的對比，分析LUE-DPTree在區間計數查詢精度上的表現。并通過對樹結構的調整，分析不同樹結構對查詢精度的影響。

4.2.1與Boost、Privelet等算法的對比

本文分別采用隨機任意長度區間和隨機固定長度區間兩種方式，對算法查詢精度進行檢驗。其中，任意長度區間隨機生成1 000條，區間的起點L和終點R隨機生成，且L≤R。隨機固定長度的區間，區間大小分別取20,21，…，213，…，每種長度隨機生成1 000條查詢區間。考慮到Boost和Privelet算法適用于2的整數冪的數據規模，在這部分實驗中，僅選取Search Logs和NetTrace為實驗數據集。

在圖5和圖6的實驗對比結果中，隨隱私參數ε的減小，平均誤差約按102的量級增長。在4種算法中，LUE-DPTree算法的查詢精度較優。說明異方差加噪策略和一致性約束下的最優線性無偏估計優化，有效提高了算法的區間計數查詢精度。

在圖7和圖8中，固定區間大小的隨機查詢，其誤差隨區間大小增加而增大。在各區間長度下，LUE-DPTree算法的查詢精度均優于Boost和Privelet算法。而Boost-UN算法中，采用異方差加噪方式，僅在不同層次中進行了隱私預算分配，而在同一層次的節點中，仍采用了相同的隱私預算，因此查詢精度介于Boost和LUE-DPTree算法之間。該實驗結果說明，LUE-DPTree算法中的隱私預算分配策略，在能夠適用于任意區間樹結構，提供更高靈活度的同時，還能更有效地提升查詢精度。

綜合上述實驗分析表明，相比其他兩種算法，LUE-DPTree算法具有更高的數據發布質量。

4.2.2不同區間樹結構對精度的影響

為觀察不同區間樹結構對查詢精度的影響，選取了4種樹結構：2叉樹、3叉樹、4叉樹和任意叉樹（每次隨機分2～4叉）分別標識為LUE-DPTree-2、LUE-DPTree-3、LUE-DPTree-4、LUE-DPTree-R。為方便起見，這部分實驗僅選取ε=1.0時，LUE-DPTree算法在Social Network和NetTrace兩個數據集上的結果進行對比。

Fig.5　Comparison of random range queries error in Search Logs圖5　隨機任意長度區間的查詢誤差對比(Search Logs)

Fig.6　Comparison of random range queries error in NetTrace圖6　隨機任意長度區間的查詢誤差對比(NetTrace)

Fig.7　Comparison of random range queries error under different lengths in Search Logs圖7　不同區間大小下的查詢誤差曲線圖(Search Logs)

Fig.8　Comparison of random range queries error under different lengths in NetTrace圖8　不同區間大小下的查詢誤差曲線圖(NetTrace)

從圖9中可以觀察到，在Social Network數據集上，不同樹結構的查詢精度差別較大，相比其他結構，任意叉樹結構的查詢精度更高；而在NetTrace數據上，精度差別較小，2叉樹結構相比其他結構有更小的誤差。結果說明，對于不同特征的數據集，若要更好地提高數據發布質量，需要建立不同的樹結構，包括任意區間樹結構。Boost算法僅適用于完全K叉樹的情況，使得人們無法通過改變樹結構來降低查詢誤差。而LUE-DPTree算法則可以適用于任意區間樹結構，使得人們可以有更大的調整空間，能夠尋找更佳的構建方式來進一步提高直方圖發布的質量。

Fig.9　Comparison of random range queries error of LUE-DPTree under different range tree structures圖9　LUE-DPTree算法在不同區間樹結構下的查詢誤差

Fig.10　Comparison of average running time under differentε圖10　不同隱私參數ε下的平均運行時間

4.3算法運行效率

本文通過以下方案對比分析4種算法在不同情況下的運行效率：（1）在樹結構相同，數據集和隱私參數取值不同的情況下分析4者的運行效率。（2）在隱私參數和數據集相同，樹結構不同的情況下分析LUE-DPTree算法的運行效率。同樣考慮到Boost和Privelet算法對樹結構的要求，在實驗（1）中僅采用Search Logs和NetTrace兩個數據集。在實驗（1）中，隱私參數ε分別取值1.0、0.1、0.01，在實驗（2）中取值1.0。為使結果更具可比性，在實驗（1）中樹結構采用完全2叉樹結構，在實驗（2）中LUE-DPTree分別選擇2叉樹、3叉樹、4叉樹和任意叉樹（每次隨機分2～4叉）。運行時間不包含數據讀入和查詢時間。實驗結果分別如圖10和圖11所示。

Fig.11　Comparison of average running time of LUEDPTree under different tree structures圖11 不同樹結構下LUE-DPTree算法的平均運行時間

從圖10中可以得出：（1）4種算法的運行時間均隨著數據規模的增大而增大，與數據規模成比例增加。（2）由于4種算法的運行效率與隱私參數無關，運行時間基本不隨隱私預算改變而變化。相比其他算法，LUE-DPTree算法多進行了一次隱私預算分配的過程，因此運行時間稍長于另外3種算法。

從圖11中可以看出，LUE-DPTree算法的運行時間隨著樹結構的變動而變動，基本與差分隱私區間樹的節點數量成正相關，與結論7所分析的線性復雜度相符。

總體來說，LUE-DPTree算法與Boost、Privelet算法均具有較高的運行效率。LUE-DPTree算法的運行效率雖略差于同類經典算法，但仍具較高的性能。

5　結束語

本文提出了一種異方差加噪下面向任意區間樹結構的差分隱私直方圖發布算法，該算法能夠在保證運行效率的前提下，有效降低查詢誤差。相比采用特定區間樹結構的發布算法，該算法適用于任意區間樹結構，在樹結構上有更大的調整靈活度，而異方差加噪方式，也為在不同的查詢規律、數據特性下進行查詢精度提升提供了更大的優化空間，因此該算法具有更好的靈活性。同時，由于任意樹結構放寬了對數據集長度的限制，提高了算法的適用范圍，使得算法具有更高的實用性。

在接下來的研究工作中，將考慮如何更加合理地通過數據分布情況和查詢區間規律，設計啟發式的區間樹構建方法與隱私預算分配方式，進一步提高發布數據的質量。

References:

[1]Zhou Shuigeng,Li Feng,Tao Yufei,et al.Privacy preservation in database applications:a survey[J].Chinese Journal of Computers,2009,32(5):847-861.

[2]Xiong Ping,Zhu Tianqing,Wang Xiaofeng.A survey on diafaferential privacy and applications[J].Chinese Journal of Computers,2014,37(1):101-122.

[3]Zhang Xiaojian,Meng Xiaofeng.Differential privacy in data publication and analysis[J].Chinese Journal of Computers, 2014,37(4):927-949.

[4]Sweeney L.k-anonymity:a model for protecting privacy[J]. International Journal on Uncertainty,Fuzziness and Knowledge Based Systems,2002,10(5):557-570.

[5]Machanavajjhala A,Gehrke J,Kifer D,et al.l-diversity:privacy beyond k-anonymity[C]//Proceedings of the 22nd International Conference on Data Engineering,Atlanta,USA, Apr 3-8,2006.Piscataway,USA:IEEE,2006:24-35.

[6]Dwork C.Differential privacy[C]//Proceedings of the 33rd International Colloquium on Automata,Languages and Programming,Venice,Italy,Jul 10-14,2006.Berlin,Heidelberg:Springer,2006:1-12.

[7]Acs G,Castelluccia C,Chen Rui.Differentially private histogram publishing through Lossy compression[C]//Proceedings of the 12th IEEE International Conference on Data Mining,Brussels,Belgium,Dec 10-13,2012.Piscataway, USA:IEEE,2012:84-95.

[8]Hay M,Rastogi V,Miklau G,et al.Boosting the accuracy of differentially private histograms through consistency[J]. Proceedings of the VLDB Endowment,2010,3(1):1021-1032.

[9]Xu Jia,Zhang Zhenjie,Xiao Xiaokui,et al.Differentially private histogram publication[J].The VLDB Journal,2013, 22(6):797-822.

[10]Qardaji W,Yang Weining,Li Ninghui.Understanding hierarchical methods for differentially private histograms[J]. Proceedings of the VLDB Endowment,2013,6(14):1954-1965.

[11]Peng Shangfu,Yang Yin,Zhang Zhenjie,et al.DP-tree:indexing multi-dimensional data under differential privacy[C]// Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data,Scottsdale,USA,May 20-24,2012.New York,USA:ACM,2012:864.

[12]Dwork C,McSherry F,Nissim K,et al.Calibrating noise to sensitivity in private data analysis[C]//LNCS 3876:Proceedings of the 3rd Theory of Cryptography Conference, New York,USA,Mar 4-7,2006.Berlin,Heidelberg:Springer, 2006:265-284.

[13]McSherry F,Talwar K.Mechanism design via differential privacy[C]//Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science,Providence, USA,Oct 21-23,2007.Piscataway,USA:IEEE,2007:94-103.

[14]Ghosh A,Roughgarden T,Sundararajan M.Universally utility-maximizing privacy mechanisms[C]//Proceedings of the 41st Annual ACM Symposium on Theory of Computing,Betheda,USA,May 31-Jun 2,2009.New York,USA: ACM,2009:351-360.

[15]Xiao Xiaokui,Wang Guozhang,Gehrke J.Differential privacyviawavelettransforms[J].IEEETransactionson Knowledge and Data Engineering,2011,23(8):1200-1214.

附中文參考文獻：

[1]周水庚,李豐,陶宇飛,等.面向數據庫應用的隱私保護研究綜述[J].計算機學報,2009,32(5):847-861.

[2]熊平,朱天清,王曉峰.差分隱私保護及其應用[J].計算機學報,2014,37(1):101-122.

[3]張嘯劍,孟小峰.面向數據發布和分析的差分隱私保護[J]計算機學報,2014,37(4):927-949.

KANG Jian was born in 1989.He is an M.S candidate at College of Mathematics and Computer Science,Fuzhou University.His research interest is differential privacy preserving.

康健（1989—），男，福建漳州人，福州大學數學與計算機科學學院碩士研究生，主要研究領域為差分隱私保護。

WU Yingjie was born in 1979.He received the Ph.D.degree in computer science from Southeast University in 2012.Now he is an associate professor at Fuzhou University.His research interests include data mining,data security and privacy preserving,etc.

吳英杰（1979—），男，2012年于東南大學計算機科學專業獲得博士學位，現為福州大學副教授，主要研究領域為數據挖掘，數據安全與隱私保護等。

HUANG Siyong was born in 1989.He received the M.S.degree from Fuzhou University in 2015.His research interest is differential privacy preserving.

黃泗勇（1989—），男，福建漳州人，2015年于福州大學獲得碩士學位，主要研究領域為差分隱私保護。

CHEN Hong was born in 1989.He received the M.S.degree from Fuzhou University in 2014.His research interest is differential privacy preserving.

陳鴻（1989—），男，福建長樂人，2014年于福州大學獲得碩士學位，主要研究領域為差分隱私保護。

SUN Lan was born in 1978.She received the M.S.degree from Xi’an Jiaotong University in 2003.Now she is a lecturer at Fuzhou University.Her research interests include data security and privacy preserving.

孫嵐（1978—），女，陜西西安人，2003年于西安交通大學獲得碩士學位，現為福州大學講師，主要研究領域為數據安全與隱私保護。

*The National Natural Science Foundation of China under Grant No.61300026(國家自然科學基金);the Natural Science Foundation of Fujian Province under Grant No.2014J01230(福建省自然科學基金).

Received 2015-07,Accepted 2015-09.

CNKI網絡優先出版:2015-09-15,http://www.cnki.net/kcms/detail/11.5602.TP.20150915.1630.010.htmlqueries and the algorithm efficiency.The experimental results show that LUE-DPTree is effective and feasible.

+Corresponding author:E-mail:yjwu@fzu.edu.cn

文獻標志碼：A

中圖分類號：TP311

doi:10.3778/j.issn.1673-9418.1507067

Algorithm for Differential Privacy Histogram Publication with Non-uniform Private Budget?

KANG Jian,WU Yingjie+,HUANG Siyong,CHEN Hong,SUN Lan
College of Mathematics and Computer Science,Fuzhou University,Fuzhou 350116,China

Abstract:Most of existing methods for differential privacy histogram publication based on range tree adopt a uniform private budget.However,it is found that the accuracy of range queries can be further enhanced if using a non-uniform private budget.Unfortunately,current techniques for differential privacy histogram publication with non-uniform private budget require strict range tree structure,which lowers its flexibility and practicability.This paper proposes an algorithm LUE-DPTree(linear unbiased estimator for differential private tree)for differential privacy histogram publication with non-uniform private budget under arbitrary range tree structure.The key idea of LUE-DPTree is to firstly calculate the query coverage probability of range tree nodes based on the distribution of range counting queries so as to allocate the non-uniform private budget.After that,it is shown by further analysis that the strategy of non-uniform private budget can be used in arbitrary range tree.Furthermore,it is indicated by theoretical proof that,after allocated non-uniform private budget under arbitrary range tree structure,the error of range counting queries still can be further reduced by solving the best linear unbiased estimators of the tree nodes’values through consistency constraint.The experimental analysis is designed by comparing LUE-DPTree and the traditional algorithms on the accuracy of range counting

Key words:privacy preserving;differential privacy;histogram publication;non-uniform private budget;range tree