基于矩陣機制的差分隱私連續數據發布方法*

5. if div

7. wend

8.λk←λk×() 1-αt;

9. return λk

通過算法4的步驟6可知，每次迭代過程都會將div除以2。因此，算法4的時間復雜度為O(lg N)。

基于上述理論，本文提出了完整的快速對角陣優化算法，如算法5所示。該算法利用?lowbit(t )代替ct對算法進行了優化，達到空間重復利用的效果，進一步提高效率。

算法5快速對角陣優化算法

輸入：連續發布的上限T∈2m-1，數據增量ai,1≤i≤T；隱私預算ε

1. for t=1 to T do //循環每次發布過程

2.p←lb(lowbit(t)) ;

8. while k>0

9.q←lb(lowbit(k)) ;

10.λk←coef(k,m)

13.k←k-lowbit(k) ;

14. wend

15. end for

4.4優化效果分析

4. For i=1 to p-1 do ?i=0 ;

5.λt←coef(t,m) ; //由算法4計算系數

針對本文提出的FDA算法，將通過分析對優化前后的均方誤差進行對比，從而對優化效果進行評估。

考慮數據量N=2m-1的情況。根據遞推公式（20），定量求出優化后均方誤差erropt；同時，結合定理2與矩陣B的性質，可推導出優化前的均方誤差errorg遞推式：

根據式（20）及（21），本文分別求出在不同規模下兩者的均方誤差。同時求出了它們均方誤差之比r=errorg/errFDA來表示優化策略的優化效果。結果如圖1所示。

通過兩者的對比可以發現，無論多大規模的數據量，優化后方法的均方誤差總是低于優化前的方法。說明了優化后的數據精確性取得了較大的改善。而從圖1（b）可以發現，它們之間的均方誤差之比呈單調遞增曲線。說明了隨N取值越大FDA算法的效果越好。

Fig.1 Comparison before and after improvement圖1　改進前后的比較

5　實驗

為了測試FDA算法的效果，本文主要在差分隱私下對數據發布的精確度進行分析。首先，將前言中提到了一種數據連續發布的樸素方法[15]與FDA算法進行比較，以此來論證本文方法是有效的。其次，將FDA算法與基于二叉樹的次數受限的連續數據發布方法（BM）[15]進行對比，以說明本文方法能夠提高數據連續發布問題的精確性。由于靜態數據發布問題是數據連續發布問題的一種特例，FDA算法也能應用于靜態數據發布。為了說明FDA算法在靜態數據發布領域也是有效的，本文將其應用于靜態數據發布，與現有比較成熟的基于一致性優化區間樹方法（Boost）和小波變換方法（Privelet）進行對比。

很顯然，本文涉及的隱私保護模型發布數據的精確性與實際數據具有相對獨立性。為了能進行更大規模的實驗測試，本文主要采用虛擬數據進行實驗，同時結合各個方法已有的理論分析，以保證實驗的準確性。本次實驗的環境為奔騰雙核CPUT4200 2.00 GHz的計算機。實驗所使用的語言為C++和Matlab。由于實驗過程中ε的取值不會對實驗結果產生重大影響，實驗中都統一將ε設置為1。即滿足1-差分隱私。另外，為了確保實驗結果符合實際的誤差期望，均進行了500次重復實驗，然后取平均值作為最終的實驗結果。

5.1FDA算法與樸素方法

本實驗對比了FDA算法和樸素方法的效果。該實驗模擬數據規模為4 095的數據集對兩者進行對比。實驗結果如圖2及圖3所示。圖2分別用藍線和紅線展示了FDA算法和樸素方法每次發布數據的均方誤差結果。圖3則分別展示了它們之間的均方誤差之比r=errsimple/errFDA以體現兩者之間的效果差距。該比值越高說明FDA算法與樸素方法比較的效果越好。

Fig.2 Effect of simple method and FDA圖2　樸素方法與FDA算法的效果

由圖2可發現樸素方法所產生的均方誤差以直線方式增長；而FDA算法產生的均方誤差隨著更新次數的增長呈上下波動的現象，均方誤差并不隨著更新次數的增長而增長。其結果經過一段時間的數據發布，樸素方法由于均方誤差增長過快而失去可用性，而FDA算法仍維持在一個可控范圍內。圖3表明了當更新次數增多時，樸素方法在發布初期誤差更低，而在數據發布達到一定次數后，FDA算法的誤差則遠低于樸素方法。進一步觀察實驗結果可知，它們之間效果好壞的分割點大約在400次數據發布前后。

Fig.3 Proportion of error between simple method and FDA圖3　樸素方法與FDA算法的均方誤差比

5.2FDA算法與二叉樹方法

本實驗對二叉樹方法與FDA算法的效果進行了對比，并采用與上一個實驗相同的數據集進行實驗，效果如圖4～圖6所示。圖4是利用二叉樹方法進行數據連續發布時的均方誤差；圖5是FDA算法所產生的均方誤差；圖6則取兩者之間的均方誤差之比r=errBM/errFDA以比較它們之間的效果。

由圖6可以看出在絕大多數情況下，FDA算法所發布的數據比BM方法更加精確。這說明了相比于BM方法，FDA算法在精確性上取得了較大的提高。由圖可知，FDA算法相比于BM方法精確性的提高集中在2至4倍之間，最高可達6倍。而分別比較圖6和圖5可知，通過FDA算法發布的數據產生的均方誤差更加集中，而BM方法發布的數據波動幅度較大。這從側面說明了FDA算法發布的數據更加穩定。

Fig.4 Effect of BM method圖4　BM方法的效果

Fig.5 Effect of FDA圖5　FDA算法的效果

Fig.6 Proportion of error between BM method and FDA圖6　BM方法與FDA算法的均方誤差比

5.3與靜態數據發布方法對比

本實驗對FDA算法與兩種靜態發布方法（Boost，Privelet）進行對比。實驗采用的虛擬數據為離線數據，數據集規模為N=2m，m=1,2,…,25；而FDA算法則減少一個數據點進行實驗以符合算法本身的要求。本文主要描述了差分隱私下的數據連續發布問題，因此在對比時采用的查詢為前N項和。為保證實驗結果盡可能反映真實情況，本文結合文獻[7-8，21]的相關理論分析進行驗證。實驗結果如圖7和圖8。圖7用一般坐標系以及指數坐標系表示三者的均方誤差。而在圖8中，分別就區間樹方法以及小波變換方法所產生的均方誤差與FDA算法的均方誤差做比較，求出不同規模數據下，它們與FDA算法的均方誤差之比。

由圖7可以看出，小波變換方法和區間樹方法所產生的均方誤差相當，且都低于FDA算法。然而，從圖8可以看出，FDA算法在靜態數據發布領域與這兩者之間的精確性差距是有限的，并且穩定在一定的數值范圍內。從圖中可以看出，FDA算法的精確性大約為其他兩種方法的0.625倍。這說明了FDA算法在靜態數據發布領域也能有效地發布數據，但是在發布的精確性方面并不如專門發布靜態數據的方法。

Fig.7 Comparison of three methods圖7　3種方法實驗結果對比

Fig.8 Proportion of error of static release methods and FDA圖8　FDA與靜態發布方法的均方誤差比

6　總結

本文描述了FDA算法，它可以快速并精確地處理差分隱私下的數據連續發布問題。通過理論分析和實驗比較，FDA算法極大地改善了現有的連續數據發布方法的精確性，并且具有發布大規模數據的能力。然而，在靜態數據發布領域，FDA算法目前還未能超越已有的成熟方法。說明FDA算法在一定程度上還有進一步提高的空間。

同時，FDA算法是針對一般連續數據發布問題提出的改進方法，因此該算法可以進一步應用于數據連續發布算法的拓展性問題上，從而進一步提高這些方法的效果，比如基于滑動窗口的流數據保護問題[22]、衰減累加的隱私保護問題[23]、無限數據流問題[24]等。而這也說明了本文提出的FDA算法具有較強的應用價值。

References:

[1] De Montjoye Y A, Hidalgo C A, Verleysen M, et al. Unique in the crowd: the privacy bounds of human mobility[R]. 2013.

[2] 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.

[3] Dwork C. Differential privacy: a survey of results[C]// LNCS 4978: Proceedings of the 5th International Conference on Theory and Applications of Models of Computation, Xi’an, China, Apr 25-29, 2008. Berlin, Heidelberg: Springer, 2008: 1-19.

[4] Dwork C, Lei Jing. Differential privacy and robust statistics[C]//Proceedings of the 41st Annual ACM Symposium on Theory of Computing, Bethesda, USA, May 31-Jun 2, 2009. New York, USA: ACM, 2009: 371-380.

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

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

[7] 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/2): 1021-1032.

[8] Xiao Xiaokui, Wang Guozhang, Gehrke J. Differential Privacy via Wavelet Transforms[J]. IEEE Transactions on Knowledge and Data Engineering, 2011, 23(8): 1200-1214.

[9] Cormode G, Procopiuc C, Srivastava D, et al. Differentially private spatial decompositions[C]//Proceedings of the 2012 IEEE 28th International Conference on Data Engineering, Washington, USA, Apr 1- 5, 2012. Piscataway, USA: IEEE, 2012: 20-31.

[10] Qardaji W, Yang Weining, Li Ninghui. Differentially private grids for geospatial data[C]//Proceedings of the 2013 IEEE 29th International Conference on Data Engineering, Brisbane, Australia, Apr 8- 12, 2013. Piscataway, USA: IEEE, 2013: 757-768.

[11] Smith A. Privacy-preserving statistical estimation with optimal convergence rates[C]//Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, San Jose, USA, Jun 6-8, 2011. New York, USA:ACM, 2011: 813-822.

[12] Zhang Jun, Zhang Zhenjie, Xiao Xiaokui, et al. Functional mechanism: regression analysis under differential privacy[J]. Proceedings of the VLDB Endowment, 2012, 5(11): 1364-1375.

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

[14] Machanavajjhala A, Kifer D, Gehrke J, et al. l-diversity: privacy beyond k- anonymity[J]. ACM Transactions on Knowledge Discovery from Data, 2007, 1(1): 3.

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

[16] Li Chao, Hay M, Rastogi V, et al. Optimizing linear counting queries under differential privacy[C]//Proceedings of the 29th ACM SIGMOD- SIGACT- SIGART Symposium on Principles of Database Systems, Indianapolis, USA, Jun 6-11, 2010. New York, USA: ACM, 2010: 123-134.

[17] Yuan Ganzhao, Zhang Zhenjie, Winslett M, et al. Lowrank mechanism: optimizing batch queries under differential privacy[J]. Proceedings of the VLDB Endowment, 2012, 5(11): 1352-1363.

[18] 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.

[19] Fenwick P M. A new data structure for cumulative frequency tables[J]. Software: Practice and Experience, 1994, 24(3): 327-336.

[20] Boyd S, Vandenberghe L. Convex optimization[M]. Cambridge, UK: Cambridge University Press, 2004.

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

[22] Cao Jianneng, Xiao Qian, Ghinita G, et al. Efficient and accurate strategies for differentially-private sliding window queries[C]//Proceedings of the 16th International Conference on Extending Database Technology, Genoa, Italy, Mar 18-22, 2013. New York, USA:ACM, 2013: 191-202.

[23] Bolot J, Fawaz N, Muthukrishnan S, et al. Private decayed predicate sums on streams[C]//Proceedings of the 16th International Conference on Database Theory, Genoa, Italy, Mar 18-22, 2013. New York, USA: ACM, 2013: 284-295.

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

CAI Jianping was born in 1990. He is an M.S. candidate at College of Mathematics and Computer Science, Fuzhou University. His research interest is differential privacy.

蔡劍平（1990—），男，福建漳州人，福州大學數學與計算機科學學院碩士研究生，主要研究領域為差分隱私。

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

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

WANG Xiaodong was born in 1957. He received the M.S. degree from Fuzhou University in 1985. Now he is a professor at Fuzhou University. His research interests include data structures, design and analysis of algorithms, etc.

王曉東（1957—），男，1985年于福州大學獲得碩士學位，現為福州大學教授，主要研究領域為數據結構、算法設計與分析等。

Method Based on Matrix Mechanism for Differential Privacy Continual Data Release?

CAI Jianping, WU Yingjie+, WANG Xiaodong
College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350116, China

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

CAI Jianping, WU Yingjie, WANG Xiaodong. Method based on matrix mechanism for differential privacy continual data release. Journal of Frontiers of Computer Science and Technology, 2016, 10(4): 481-494.

Abstract:The vast majority of the literature on differential privacy algorithms focuses on one time static release of datasets, while many applications of data analysis involve the continual data release. This paper proposes a method based on matrix mechanism for differential privacy continual data release. The key idea of the proposed method is to firstly construct the strategy matrix of the continual data release problem using the binary indexed tree, and then optimize the strategy matrix to boost the accuracy of the published data. After that, aiming at the high time complexity of existing optimization algorithm based on matrix mechanism, this paper puts forward a fast diagonal matrix optimization algorithm (FDA) with O(lg N) time complexity, which can be applied to the situation of large-scale continuous data publishing effectively. This paper compares and analyzes FDA and the traditional algorithms on the accuracy of the released data by experiments. The experimental results show that FDAis effective and feasible.

Key words:differential privacy; matrix mechanism; binary indexed tree; continual data release

文獻標志碼：A

中圖分類號：TP309.2

doi:10.3778/j.issn.1673-9418.1507074