差分隱私流數據自適應發布算法

吳英杰 張立群 康 健 王一蕾

(福州大學數學與計算機科學學院 福州 350116)

差分隱私流數據自適應發布算法

吳英杰 張立群 康 健 王一蕾

(福州大學數學與計算機科學學院 福州 350116)

(yjwu@fzu.edu.cn)

當前，許多實際應用需要持續地對流數據進行發布，現有關于單條流數據的差分隱私發布研究大多考慮區間的累和發布，而現實應用中往往需要對發布流數據進行任意區間計數查詢，同時，用戶查詢往往存在特定規律，可針對歷史查詢進行自適應統計與分析，提高發布數據可用性.為此，提出一個基于歷史查詢的差分隱私流數據自適應發布算法HQ_DPSAP.算法HQ_DPSAP首先結合流數據的特性，利用滑動窗口機制動態構建窗口內流數據對應的差分隱私區間樹，而后進一步分析與計算樹節點的覆蓋概率；接著自底向上計算隱私分配參數，再自頂向下分配隱私預算，并據此對樹節點進行異方差加噪；最后根據歷史查詢規律自適應調整樹節點的隱私預算與樹結構參數，以實現流數據的自適應發布.實驗對算法HQ_DPSAP的可行性及有效性進行比較分析，結果表明：算法HQ_DPSAP可有效支持任意區間計數查詢，且具有較低的查詢均方誤差和較高的算法執行效率.

差分隱私；流數據發布；異方差加噪；歷史查詢；自適應算法

當前，許多實際應用需要持續地對流數據進行統計發布，如購物網站需要實時統計物品的銷售額以向用戶推薦熱銷產品，搜索引擎需要統計搜索頻率較高的詞組以根據用戶的部分輸入列出可能要搜索的詞組.這些應用均需統計發布流數據在某種意義下的實時計數值.發布該類統計值在提供科學決策依據的同時，可能泄露有關用戶的個體隱私信息[1].為此，近年來一些研究人員基于差分隱私[2-5]保護模型對該類流數據統計發布問題進行了研究[6-11]，Dwork等人[6]提出分段計數的方法，實現對單條流數據從時刻1到當前時刻t的計數值總和進行連續發布.Chan等人[7]進而提出了利用二叉樹結構，實現了計數值總和連續發布的查詢精度提高和算法效率提升.Cao等人[8]在系統運行前，對預先定義的查詢集合進行統計分析，以實現對特定用戶批次范圍查詢進行回答并優化查詢精度.Bolot等人[9]提出了權重衰減下的差分隱私流數據統計發布方法，對滑動窗口內多種衰敗模式的統計值加權累加和進行統計發布.在文獻[10]中，采用滑動窗機制和劃分等方法，提供了滑動窗口內計數值總和發布和從時刻1開始的計數值總和發布等.

在多條流數據統計發布方面，文獻[11]研究如何在多個事件數據流上回答1個滑動窗查詢.其研究內容關注如何更合理分配滑動窗口內的隱私預算，通過分析數據的平滑度來調整隱私分配策略.Chan等人[12]提出了利用二叉樹結構的動態構建對多條流中具有重要影響力的流進行發布的方法(如在多部電影的點播數據中，獲取本周最熱門電影等).文獻[13]從更一般的查詢形式入手，檢測數據流聚合統計值是否超過閾值，研究通信效率與隱私泄露的關系.

在現實關于單條流數據的應用中，往往需要對發布流數據進行任意區間計數查詢.而在以上研究工作中，雖已從多個角度實現差分隱私流數據發布，但均未專門針對此類查詢進行相關研究.為此，本文擬在滑動窗口下，實現對發布單條流數據提供靈活的任意區間計數查詢，并通過對用戶歷史查詢的分析預測，對隱私預算分配和區間樹構建過程進行自適應調節，以實現發布數據精度提升和發布算法實用性的提高.本文的主要貢獻有3個方面：

1) 針對流數據發布的實時性要求，提出一種在滑動窗口下進行區間樹動態構建的算法；

2) 分析與計算區間樹節點的覆蓋概率，并據此設計隱私預算預分配策略，對動態構建的區間樹節點進行異方差加噪；

3) 通過對查詢區間大小和位置等用戶查詢偏好進行統計與分析，提出一種可自適應調節隱私預算分配與區間樹結構構建的方法，從而有效提高發布數據可用性.

1 相關概念

1.1 差分隱私定義

差分隱私保護是一種強健的隱私保護框架，由于其具有允許數據表中某條記錄發生改變，對查詢結果影響幅度小的特性，使得攻擊者在對除某條記錄外的所有信息都知情的情況下，仍無法獲取到該條記錄中的敏感信息.因此，能夠更有效地保護隱私信息.

在差分隱私保護模型中，對兄弟數據表概念定義如下：

定義1. 兄弟數據表.給定數據表T1,T2，當2個數據表之間只存在1條記錄不同，則稱T1,T2為兄弟數據表.

在兄弟數據表定義基礎上，Dwork給出了ε-差分隱私定義.

定義2.ε-差分隱私[2].給出任意2個兄弟數據表T1,T2，若發布算法A對該對兄弟數據表的所有可能輸出均滿足：

Pr[A(T1)∈O]≤eε×Pr[A(T2)∈O]，

(1)

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

1.2 差分隱私流數據區間計數查詢

Fig. 1 The problem of noise accumulation圖1 噪聲累加問題

定義3. 流數據.流數據為1組順序大量、連續快速到達的數據序列，其具有實時到達、次序獨立，規模隨時間無限增長等特性.

在流數據中用戶區間計數查詢范圍是[l,r](1≤l≤r≤t)，其返回值公式為

(2)

根據定義2，該條件下的查詢模式、噪聲會隨時間t的推移無限累加，使得隱私預算耗盡.分別如圖1、圖2所示：

Fig. 2 The problem of privacy depletion圖2 隱私預算耗盡問題

定義4. 差分隱私區間樹[14].對于給定計數直方圖H={C1,C2,…,Cn}，對H建立差分隱私區間樹T滿足3點特性：

1) 對于所有非葉子節點，其兒子節點數大于等于2.

2) 每個節點x對應于H中的1個區間范圍，表示為[lx,rx]，根節點所代表的區間為[1,n].

使用差分隱私區間樹對靜態數據進行重構，能有效提高數據發布的精度和查詢效率.然而在流數據構建中，差分隱私區間樹有其局限性.

在圖2中，隨著時間t的增長，差分隱私區間樹樹高將不斷升高，并產生新的根節點，從而需要為新的節點分配有效的隱私預算.因此，隨著隱私預算不斷分配，終將導致隱私預算耗盡，降低隱私保護強度.在實際研究工作中，研究人員采用了許多方法，來降低噪聲累加和隱私預算耗盡問題帶來的影響.其中，Chan等人[12]根據實際應用背景，采用滑動窗口對流數據進行發布.滑動窗口既保證實際應用背景中被頻繁訪問的近期數據的發布精度，同時避免了噪聲累加和隱私預算耗盡的問題.

定義5. 滑動窗口下的流數據區間計數查詢.設流數據當前時序為t，流數據序列為S={C1,C2,…,Ct}，用戶可對數據源提出區間計數查詢操作q，區間查詢定義為查詢某段連續時序的數據計數累和，區間查詢的范圍可表示為[lq,rq](t-w

(3)

其相當于對數據庫表S執行查詢：

SelectCount(*) FromSWheretime∈[lq,rq].

滑動窗口W下的流數據發布如圖3所示：

Fig. 3 Streaming data in sliding window圖3 滑動窗口下的流數據發布

對靜態數據進行區間計數查詢時，可采用差分隱私區間樹對數據進行組織表示，現有工作[16]通過合理分配隱私預算，進行異方差加噪，進一步提高查詢精度.異方差加噪同樣適用于滑動窗口下的差分隱私流數據發布.同方差與異方差加噪方式，及其對發布精度的影響，舉例如下：

如圖4(a)，當區間樹總的隱私預算為1.0時，每個節點分配的隱私預算εx=0.5；而圖4(b)中，節點N1分配的隱私預算εx=0.33,它的兒子節點N2，N3，N4的隱私預算εx=0.67.通常情況下，各個樹節點的查詢概率不同.例如查詢區間隨機分布的情況下，節點N2，N3，N4的覆蓋概率高于節點N1，因此，通過設計合理的隱私預設分配策略，對高覆蓋概率的節點添加更少的噪聲，對覆蓋概率低的節點添加更多的噪聲，能夠有效降低整體的查詢誤差.

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

2 基于歷史查詢的差分隱私流數據自適應發布

為實現流數據的自適應發布，首先需結合流數據特性，利用滑動窗口機制動態構建流數據對應的區間樹.

2.1 滑動窗口下的區間樹動態構建

通過在滑動窗口內進行區間樹的動態構建，能夠有效提高流數據發布算法的效率.在文獻[11]中，采用了完全二叉樹結構進行數據的組織表示.如圖5所示：

Fig. 5 Dynamic construction process of interval tree圖5 滑動窗口中的區間樹動態構建過程

在圖5中，滑動窗口大小為|W|，當前時刻為t，滑動窗口內包含2棵不完整的區間樹，深灰色節點為被移出窗口的樹節點，因查詢集合不再覆蓋這部分節點，故標記為過期節點；淺灰度節點為未來將進入窗口的虛擬樹節點，隨著時間t推移，這些節點將在動態構建過程中被激活；白色節點為正處于滑動窗口中的樹節點.

由于圖5中的動態構建過程對樹結構要求較為嚴格，本文針對異方差加噪對樹結構的要求，設計了更具靈活性和可擴展性的區間樹動態構建算法.首先，根據建樹狀態不同，將區間樹分為預構建樹與完成構建樹，定義如下.

定義6. 預構建樹.對于處于滑動窗口的區間樹T,若該樹的部分葉子節點所對應的時刻還未到來，則T稱為預構建樹.如圖6所示：

Fig. 6 Pre-building tree圖6 預構建樹

定義7. 完成構建樹.對于處于滑動窗口中的區間樹T，若該樹所有節點均已完成構建，則稱為完成構建樹，如圖7所示:

Fig. 7 Builded tree圖7 完成構建樹

在流數據發布過程中，當時刻t推移1個單位，若滑動窗口內所有區間樹均已構建完成，則可根據分叉數k和樹高h等參數構建出一棵新的區間樹，并進行隱私預算預分配.如圖8所示:

Fig. 8 Node insertion and pre-building tree圖8 節點插入并建立預構建樹

在圖8中，當插入新節點t時，滑動窗口中T1為完成構建樹，因此，預構建了區間樹T2，并進行隱私預算預分配.

若當前滑動窗口中存在預構建樹，則從樹中找到對應節點位置進行節點插入操作，并根據預分配的隱私預算參數，分配隱私預算，進行加噪；再根據預構建樹結構，完成父節點的遞歸構建操作.具體操作同樣如圖9所示.在圖9中，當插入節點t-1時，在滑動窗口中找到預構建樹T2，將節點插入對應位置并進行加噪，同時，對節點t、節點t+1的父節點進行插入、加噪.插入后的樹結構如圖9所示:

Fig. 9 Insert a node into the pre-building tree圖9 在預構建樹中插入節點

在構建差分隱私區間樹過程中，當新數據流入滑動窗口，將執行節點插入操作，詳細過程如算法1所示.

算法1. 節點插入算法Insert.

輸入：區間樹列表TreeList、節點真實值v；

輸出：更新后的區間樹列表.

步驟1. 判斷TreeList中是否存在預構建樹T，若不存在，則調用歷史查詢分析算法TPCalc，獲得構建參數，創建預構建樹，并調用節點參數計算算法NPC和隱私預算分配算法PBD，進行隱私預算預分配；

步驟2. 從節點回收池獲取節點空間Recx；

步驟3. 從預構建樹中獲取當前節點的位置和隱私預算，進行異方差加噪；

步驟4. 判斷當前預構建樹T是否滿足進一步合并條件，若滿足，則對T進行節點合并操作；

步驟5. 判斷當前樹是否構建完成，若構建完成，標記T為完成構建樹.

由于滑動窗口僅對|W|長度范圍內的數據進行發布，對于超出滑動窗口的樹節點不再提供查詢，故將作為過期節點進行移除.節點刪除過程如算法2所示.

算法2. 節點刪除算法Delete.

輸入：待刪除節點Delx；

輸出：更新后的區間樹列表.

步驟1. 獲取節點Delx，若節點Delx已移出滑動窗口，則將節點Delx刪除并移至回收池；

步驟2. 若存在父節點，獲取父節點father(Delx)，遞歸調用Delete算法.

在樹結構構建過程中，采用節點回收機制提高空間利用率，所刪除的節點重新進入回收池等待重新利用.

動態構建樹結構的插入刪除操作時間復雜度均為O(1)，滿足差分隱私流數據對算法的時間效率要求，并且該算法滿足差分隱私保護要求，能提供有效的區間計數查詢.在實現滑動窗口下的區間樹動態構建的基礎上，即可進一步進行異方差加噪，提高查詢精度.

2.2 節點覆蓋概率計算及隱私預算預分配

在動態構建的區間樹結構上進行異方差加噪前，首先需分析及計算節點的覆蓋概率.以下給出節點覆蓋概率計算的相關定義.

定義8. 節點覆蓋概率.設px為節點x的查詢覆蓋概率，QP(l,r)為區間[l,r]被查詢區間覆蓋的概率，則由定義3可知，節點x若被查詢區間[lq,rq]覆蓋，需滿足2個條件：

1) 節點x本身被查詢區間覆蓋；

2) 節點的父節點不被查詢區間覆蓋.

因此，滿足：

定義9. 查詢覆蓋節點集合.設NodeSet(q)為查詢q所覆蓋的節點集合.同樣由定義6可知，節點集合滿足條件：

NodeSet(q)=
{x|lq≤lx∧rx≤rq∧(lq≤lfx∧rfx≤rq)}.

定義10. 節點誤差期望.由Laplace機制定義可知，當對節點x進行Laplace機制加噪時，該節點的誤差期望為

根據定義8～10，設QC(x)為在查詢全集Q中，節點x被查詢區間覆蓋的次數.即QC(x)=px|Q|.則差分隱私區間樹的整體查詢誤差期望為

根據上述定義和最優化問題的求解，得到以下結論：

結論1. 為最小化區間計數查詢誤差期望，在區間樹節點中隱私預算分配方案需滿足：

εx=kxpsum(x)，

證明.

當x為葉節點時，結論顯然成立.

當x非葉節點時，可通過拉格朗日乘數法構造函數求解該問題：

即：

當x為非葉子節點，對于節點y∈Son(x)，有：

且由約束條件可知：

因此：

令εx=kxpsum(x)，則：

化簡，得：

證畢.

根據結論1，即可在區間樹動態構建過程中，根據節點覆蓋概率計算節點系數，并進行隱私預算預分配，以實現異方差加噪，節點系數計算如算法3所示：

算法3. 節點系數計算NPC.

輸入：待計算區間樹T、區間樹中待計算節點x；

輸出：節點系數kx.

步驟1. 若x為葉節點，kx←1，結束算法；

步驟2. 若x非葉節點：

For eachy∈Son(x)

NPC(T,y)；

End For

節點系數計算完成后，通過算法4進行節點隱私預算分配.

算法4. 隱私預算預分配算法PBD.

輸入：當前待分配節點x，tot=psum(x)；

輸出：最小化查詢誤差期望隱私預算分配方案.

步驟1.εx←kxtot

步驟2. For eachy∈Son(x)

PBD(y,tot-εx)；

End For

在發布算法運行前，預置查詢區間分布為均勻隨機分布，統計節點覆蓋概率，選取樹結構構建參數.由于節點覆蓋概率和構建參數的選取均與發布數據無關，不會造成隱私泄露，算法滿足差分隱私保護要求.

通過在區間樹動態構建過程中進行異方差加噪，有效降低了區間計數查詢的誤差，而通過對用戶歷史查詢的統計分析，算法的發布數據精度仍有進一步的提升空間.

2.3 基于歷史查詢差分隱私流數據算法HQ_DPSAP

在算法4中，將查詢區間分布假定為均勻分布，并以此進行隱私預算分配，而在不同應用場景下，用戶的查詢可能呈現特定規律.通過對查詢區間大小和位置等用戶查詢偏好進行統計與分析，自適應地調整隱私預算分配與樹結構構建，將有效提高發布數據可用性.首先，給出基于歷史查詢概率統計的節點覆蓋概率計算公式：

結論2. 基于歷史查詢概率統計，節點覆蓋概率

證明. 對于節點x，由于隨時間推移，節點x所表示的區間[lx,rx]在滑動窗口W中的相對位置不斷移動.因此，需要對整個移動過程中的覆蓋概率進行統計.

設滑動窗口寬度為|W|，節點x所統計區間的寬度為Lx，則節點x在滑動窗口中的移動步數為|W|-Lx+1.設在每一步中，用戶查詢次數為|Q|，在無父節點時，節點x在全過程中被覆蓋的次數為

因此，在|W|-Lx+1步中節點x在全過程中被覆蓋的概率為

同時，由于當節點x存在父節點時，需去除父區間被覆蓋的情況，因此，節點覆蓋概率為

證畢.

通過結論2，即可在節點覆蓋概率基礎上分析歷史查詢規律，對預構建樹進行隱私預算分配，進一步提高查詢精度.用戶進行區間查詢時，更新歷史查詢統計并返回查詢結果.如算法5所示：

算法5. 區間計數查詢RangeQuery.

輸入：當前查詢節點x、查詢區間[l,r]；

輸出：區間計數統計值ret.

步驟1. 更新查詢區間概率直方圖；

步驟2. 若x節點代表的區間與[l,r]無交集，則：

For eachy∈rootlist

Ifly≤rorry≥l

ret←RangeQuery(y,l,r)；

End If

End For

步驟3. 若x節點代表的區間與[l,r]有交集，則繼續步驟4，否則結束算法；

步驟4. Ifl≤lxandr≥rx

Else

For eachy∈Son(x)

Ifly≤rorry≥l

ret←ret+RangeQuery(y,l,r)；

End If

End For

End If

根據算法5得到的歷史查詢統計結果，即可使用模擬退火算法，迭代尋找新的構樹參數，從而根據用戶查詢特性，自適應地調整區間樹結構，提高查詢精度.樹結構的自適應調整如算法6所示：

算法6. 樹結構的自適應調整TPCalc.

輸入：原構樹參數；

輸出：新構樹參數.

步驟1. 由原構樹參數產生新構樹參數叉數k、樹高h；

步驟2. 利用新構樹參數預構建樹，計算誤差期望；

步驟3. 與舊構樹參數誤差期望對比，若誤差期望更低，則接受新構樹參數；

步驟4. 若誤差期望更高，則以一定概率接受新構樹.

綜合以上算法1～6，可形成如下基于歷史查詢的差分隱私流數據自適應發布算法HQ_DPSAP.

算法7. HQ_DPSAP.

輸入：原始流數據、歷史查詢；

輸出：發布流數據.

步驟1. 初始化產生構樹參數叉數k、樹高h、節點覆蓋概率；

步驟2. 調用算法1(Insert)/算法2(Delete)動態插入/刪除樹節點；

步驟3. 調用過算法3(NPC)進行節點系數計算，算法4(PBD)進行隱私預算預分配，實現異方差加噪；

步驟4. 通過算法5(RangeQuery)實現滑動窗口內任意區間計數查詢，進行歷史查詢統計，自適應地調整隱私預算，樹結構參數；

步驟5. 得到新的隱私預算分配方案，并通過算法6(TPCalc)更新構樹參數，返回步驟2.

基于歷史查詢的差分隱私流數據自適應發布算法流程圖如圖10所示.

Fig. 10 Flow diagram of HQ_DPSAP圖10 HQ_DPSAP算法流程圖

對HQ_DPSAP算法所滿足的ε-差分隱私進行分析.

結論3. HQ_DPSAP算法滿足ε-差分隱私.

證畢.

結論4. HQ_DPSAP算法為線性復雜度.

證明. 在HQ_DPSAP算法中，若入節點時已有預構建樹，則直接從預構建樹中分配已經算好的隱私參數進行加噪，故插入操作復雜度為O(1).

若不存在預構建樹，則需調用TPCalc.該算法使用模擬退火，并只生成1組新解用于樹結構預構建.設新區間樹的葉節點數為|W|，該算法復雜度為O(|W|).由于每|W|個葉節點需構建1次新樹，故均攤復雜度為O(1).

在插入節點的同時需要刪除窗口末尾的1個節點，如果該節點的兄弟節點已被刪完，則遞歸刪除改節點的父節點.在|W|次刪除操作中，每個節點只刪除1次，故均攤復雜度為O(1).

設流數據總長度為n，則HQ_DPSAP算法復雜度為O(n).

證畢.

3 實驗分析

現有基于滑動窗口的流數據發布方法尚無法提供窗口內的任意區間計數查詢，為了檢驗HQ_DPSAP的精度優化效果，本節根據在流數據發布處理過程的不同，設計4種實驗，命名分別為：①SW(BASE)，僅基于滑動窗口，采用同方差加噪方式，不分析歷史查詢且固定為二叉樹結構；②SW(DIFF)，為在SW(BASE)基礎上進行異方差加噪；③SW(DIFF,HIST)，為在前者基礎上，增加對歷史查詢規律的分析統計；④HQ_DPSAP，為本文最終形成的算法：在SW(DIFF,HIST)的基礎上，根據歷史查詢規律，對數據進行異方差加噪和動態調整區間樹結構參數.本節從查詢精度和算法運行效率2個方面分析實驗結果，以驗證本文提出算法的性能.

3.1 實驗環境

實驗在數據集Search Logs，NetTrace，WorldCup98上進行.其數據規模如表1所示.

在實驗中，采用平均方差進行誤差衡量：

(4)

其中，|Q|為查詢集合的大小，q(T)為區間計數查詢的真實計數值，q(T′)為區間計數查詢的加噪發布計數值.為保證實驗結果更具一般性，取算法執行50次的平均值作為實驗結果.

Table1 Three Common Data Set for Different Privacy Algorithm

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

3.2 查詢精度

實驗通過在Search Logs，Nettrace，WorldCup98數據集上進行不同隱私預算下的查詢精度誤差對比分析，并比較異方差加噪與樹結構調整對算法結果的影響.

在現有流數據差分隱私數據發布工作中，為對特定時間狀態發布、多條流聯合統計發布、w事件級別隱私保護等，本文關注滑動窗口下對單條流數據進行區間計數查詢數據發布.由于Search Logs與Nettrace數據集規模較小，采用其數據集長度作為滑動窗口大小.在WorldCup98數據集中，采用1 d的時長(86 400 s)作為滑動窗口大小.

1) 隨機區間不同參數下的查詢誤差對比

隨機生成1 000條長度任意的區間[L,R]，隨機生成的長度范圍在滑動窗口長度內，并在不同隱私參數下，實驗結果如圖11～13所示：

Fig. 11 Comparison of random length queries in Search Logs圖11 數據集Search Logs在隨機任意長度查詢區間下查詢誤差對比

Fig. 12 Comparison of random length queries in Nettrace圖12 數據集Nettrace在隨機任意長度查詢區間下查詢誤差對比

Fig. 13 Comparison of random length queries in WorldCup98圖13 數據集WorldCoup98在隨機任意長度查詢區間下查詢誤差對比

在圖11～13的實驗對比中，隨著隱私預算減小，查詢均方誤差以102的數量級遞增.相比SW(BASE)，由于采用了異方差加噪，SW(DIFF)有效降低查詢誤差，由于查詢是隨機均勻分布的，于是算法SW(DIFF,HIST)增加了對歷史查詢分析，并未對隱私預算產生提升.

2) 特定規律查詢下的誤差對比

在實際場景中，查詢分布可能呈現特殊規律，本節實驗設滑動窗口大小為|W|，根據區間規律分為Small，Middle，Large.其中，Small查詢區間集中于1～0.33|W|；Middle查詢區間集中于0.33|W|～0.67|W|；Large查詢區間集中于0.67|W|～|W|.隱私預算ε=1.0.實驗結果如圖14～16所示:

Fig. 14 Comparison of specific rule queries in Search Logs圖14 數據集Search Logs在特定規律查詢區間下的誤差對比

Fig. 15 Comparison of specific rule queries in Nettrace圖15 數據集Nettrace在特定規律查詢區間下的誤差對比

Fig. 16 Comparison of specific rule queries in WorldCup98圖16 數據集WorldCup98在特定規律查詢區間下的誤差對比

在圖14～16的結果對比中，由于查詢區間分布具備特定規律，SW(DIFF,HIST)對誤差精度提升明顯，在不同規律下均能在異方差加噪的基礎上進一步提升.而算法HQ_DPSAP，通過對歷史查詢區間分布規律的統計分析和異方差加噪與區間樹結構動態構建，能夠有效針對不同的查詢場景進行自適應的調整優化.

3) 在不同區間大小下的查詢誤差對

Fig.17 Comparison of different range queries in Search Logs圖17 數據集Search Logs在不同區間大小下的查詢誤差對比

本節實驗通過隨機生成固定長度的查詢區間，對比分析區間查詢誤差.區間大小分別取20,21，…，213，…，每種長度隨機生成1 000條查詢.對比結果如圖17～19所示.

Fig. 18 Comparison of different range queries in Nettrace圖18 數據集Nettrace在不同區間大小下的查詢誤差對比

Fig. 19 Comparison of different range queries in WorldCup98圖19 數據集WorldCup98在不同區間大小下的查詢誤差對比

從圖17～19可以看出，SW(DIFF,HIST)有效降低了數據發布誤差.由于在大區間查詢時，仍會覆蓋許多小區間，因此優化效果有所降低.而HQ_DPSAP有對區間樹結構調整，使得在大查詢區間也能通過降低樹高等方式降低誤差.

4) 在流數據發布過程中的查詢誤差對比

在流數據發布背景下，用戶查詢區間的分布規律可能會發生變化，本文通過在數據發布過程中，動態改變用戶查詢區間的分布規律，并記錄在流數據發布過程中，隨時間t的增長，查詢誤差發生的變化，用以分析文中算法對用戶查詢區間規律的適應性和提升查詢精度的有效性.實驗結果如圖20所示.

在圖20中，隨著時間的推移(1～7 510 000 s)，查詢區間分布規律由Rand改變至Small，Middle，Large.由于未對歷史查詢概率進行統計與分析，SW(DIFF)算法僅以區間均勻隨機分布為假設，以固定的二叉區間樹結構進行流數據發布，因此，不能很好地適應不同的查詢分布，查詢誤差較大且波動較大.而算法HQ_DPSAP，能夠根據不同的查詢區間，調整區間樹結構、調整隱私預算分配方案，因此，能夠有效降低查詢誤差，并且降低波動使查詢結果更加穩定、可用.

Fig. 20 Comparison of range query in stream data publications in WorldCup98圖20 數據集WorldCup98在流數據發布過程中的查詢誤差對比

綜上實驗分析表明：算法HQ_DPSAP能夠適應不同的應用場景，進行自適應精度優化，有效降低了區間計數查詢誤差.

3.3 算法運行效率

本節通過2個方案對算法運行效率進行對比：

1) 不同隱私參數下對運行效率的影響

使用相同大小的滑動窗口(32 768)，設置不同的隱私參數(1.0，0.1，0.01)，對比結果如圖21所示:

Fig. 21 Different privacy budget effect on efficiency圖21 不同隱私參數下對運行效率的影響

由圖21可知，算法HQ_DPSAP運行時間不是隨隱私預算不同而改變，而是隨著數據集大小增加而增加.

2) 不同滑動窗口大小對運行效率的影響

固定隱私預算εx=1.0，設置不同大小的滑動窗口對比，結果如圖22所示:

Fig. 22 Different range of window effect on efficiency under data set WorldCup98圖22 數據集WorldCoup98下不同滑動窗口大小對運行效率的影響

滑動窗口從28增加到218，從圖22可知，滑動窗口大小對運行時間無明顯影響，與結論2一致，該算法時間復雜度為線性.

綜上所述，算法HQ_DPSAP具有較高的運行效率，滿足流數據實時發布要求.

4 結束語

為有效提高差分隱私流數據發布中的任意區間查詢精度，本文提出了一種基于歷史查詢的差分隱私流數據自適應發布算法HQ_DPSAP.算法通過對用戶歷史查詢的分析，可進行隱私預算與樹結構的自適應調節，從而有效降低區間查詢誤差，提高隱私預算分配靈活性.基于真實數據集的仿真實驗結果表明:HQ_DPSAP算法是有效可行的.

[1]Fung B, Wang Ke, Chen Rui, et al. Privacy-preserving data publishing: A survey of recent developments[J]. ACM Computing Surveys, 2010, 42(4): 2623-2627

[2] Dwork C. Differential privacy[C] //Proc of the 33rd Int Colloquium on Automata, Languages and Programming. Berlin: Springer, 2006: 1-12

[3] Zhou Shuigeng, Li Feng, Tao Yufei, et al. Privacy preservation in database applications: A survey[J]. Chinese Journal of Computers, 2009, 21(5): 847-861 (in Chinese)(周水庚, 李豐, 陶宇飛. 面向數據庫應用的隱私保護研究綜述[J]. 計算機學報, 2009, 21(5): 847-861)

[4] Xiong Ping, Zhu Tianqing, Wang Xiaofeng. A survey on differential privacy and applications[J]. Chinese Journal of Computers, 2014, 37(1): 101-122 (in Chinese)(熊平, 朱天清, 王曉峰. 差分隱私保護及其應用[J]. 計算機學報, 2014, 37(1): 101-122)

[5] Zhang Xiaojian, Meng Xiaofeng. Differential privacy in data publication and analysis[J]. Chinese Journal of Computers, 2014. 37(4): 927-949 (in Chinese)(張嘯劍, 孟小峰. 面向數據發布和分析的差分隱私保護[J]. 計算機學報, 2014, 37(4): 927-949)

[6] Dwork C, Naor M, Pitassi T, et al. Differential privacy under continual observation[C] //Proc of the 42nd ACM Symp on Theory of Computing. New York: ACM, 2010: 715-724

[7] Chan T H H, Shi E, Song D. Private and continual release of statistics[J]. ACM Trans on Information and System Security, 2011, 14(3): 26-38

[8] Cao Jianneng, Xiao Qian, Ghinita G, et al. Efficient and accurate strategies for differentially-private sliding window queries[C] //Proc of the 16th Int Conf on Extending Database Technology. New York: ACM, 2013: 191-202

[9] Bolot J, Fawaz N, Muthukrishnan S, et al. Private decayed predicate sums on streams[C] //Proc of the 16th Int Conf on Extending Database Technology. New York: ACM, 2013: 284-295

[10] Zhang Xiaojian, Meng Xiaofeng. Stream histogram publication method with differential privacy[J]. Journal of Software, 2016, 27(2): 381-393 (in Chinese)(張嘯劍, 孟小峰. 基于差分隱私的流式直方圖發布方法[J]. 軟件學報, 2016, 27(2): 381-393)

[11] Kellaris G, Papadopoulos S, Xiao Xiaokui, et al. Differentially private event sequences over infinite streams[J]. Proceedings of the VLDB Endowment, 2014, 7(12): 1155-1166

[12] Chan T H H, Li Mingfei, Shi E, et al. Differentially private continual monitoring of heavy hitters from distributed streams[C] //Proc of the 12th Int Conf on Privacy Enhancing Technologies. Berlin: Springer, 2012: 140-159

[13] Friedman A, Sharfman I, Keren D, et al. Privacy-Preserving distributed stream monitoring[C] //Proc of the 21st Annual Network and Distributed System Security Symp. Reston, VA: ISOC, 2014: 1-12

[14] Michael H, Vibhor R, Gerome M, et al. Boosting the accuracy of differentially private histograms through consistency[J]. VLDB Endownment, 2010, 3(1): 1021-1032

[15]Dwork C, McSherry F, Nissim K, et al. Calibrating noise to sensitivity in private data analysis[C] //Proc of the 3rd Theory of Cryptography Conf. Berlin: Springer, 2006: 363-385

[16] Kang Jian, Wu Yingjie, Huang Siyong, et al. An algorithm for differentially private histogram publication with non-uniform private budget[J]. Journal of Frontiers of Computer Science & Technology, 2016, 10(6): 786-798 (in Chinese)(康健, 吳英杰, 黃泗勇, 等. 異方差加噪下的差分隱私直方圖發布算法[J]. 計算機科學與探索, 2016, 10(6): 786-798)

AnAlgorithmforDifferentialPrivacyStreamingDataAdaptivePublication

Wu Yingjie, Zhang Liqun, Kang Jian, and Wang Yilei

(CollegeofMathematicsandComputerScience,FuzhouUniversity,Fuzhou350116)

Nowadays, many practical applications need to publish streaming data continuously. Most of existing research works for differential privacy single streaming data publication focus on range accumulation. However, many practical scenarios need to answer arbitrary range counting queries of streaming data. At the same time, there exist specific rules of queries from users, so adaptive analysis and calculation for historical queries should be concerned. To improve the usability of published data, an algorithm HQ_DPASP for differential privacy streaming data adaptive publication based on historical queries is proposed. Combining the characteristics of streaming data, HQ_DPASP firstly uses the sliding window mechanism to construct the differential privacy range tree of the streaming data dynamically. Secondly, by analyzing the coverage probability of tree nodes and calculating the privacy parameters from leaves to root, HQ_DPASP allocates privacy budget from root to leaves and adds non-uniform noise on tree nodes. Finally, the privacy budget of tree nodes and tree’s parameters are adjusted adaptively based on the characteristic of historical queries. Experiments are designed for testing the feasibility and effectiveness of HQ_DPSAP. The results show that HQ_DPSAP is effective in answering arbitrary range counting queries on the published streaming data while assuring low mean squared error of queries and high algorithm efficiency.

differential privacy; streaming data publication; non-uniform noise; historical query; adaptive algorithm

2016-08-02；

2016-11-08

國家自然科學基金項目(61300026)；福建省自然科學基金項目(2014J01230)

This work was supported by the National Natural Science Foundation of China (61300026) and the Natural Science Foundation of Fujian Province of China (2014J01230).

王一蕾(yilei@fzu.edu.cn)

TP391

WuYingjie, born in 1979. PhD and professor. Member of CCF. His main research interests include data mining and data privacy preserving.

ZhangLiqun, born in 1991. Master. His main research interests include data mining and differential privacy.

KangJian, born in 1989. PhD candidate. His main research interests include data mining and differential privacy.

WangYilei, born in 1979. PhD candidate. Her main research interests include recommender systems and data privacy preserving.