现有基于树结构的差分隐私流数据统计发布方法未能充分利用统计查询可能存在的特定分布规律而进一步提升发布流数据的精度，为此，该文提出滑动窗口下基于异方差加噪的差分隐私流数据发布算法。首先动态构建滑动窗口内流数据对应的差分隐私区间树；其次根据统计查询分布规律计算树节点的覆盖概率，据此对树节点的隐私预算及树结构参数进行调整，以实现异方差加噪；最后，针对异方差加噪后区间树节点值可能不满足一致性约束的问题，设计实时的一致性调节策略。实验结果表明：与同类算法相比，该算法具有较高的查询精度及算法效率。
Most existing methods for differential privacy streaming data statistical release based on tree structures cannot take advantage of the special probability distributions in statistical queries. This study presents an algorithm that further boosts the accuracy of the released streaming data for differential privacy streaming data publication with non-uniform private budgets using sliding windows. After constructing the differential privacy range tree for the streaming data within the sliding window, the algorithm calculates the coverage probability of the tree nodes according to the probability distribution of the statistical queries and then adds non-uniform noise to the tree nodes based on the adjusted privacy budget of the tree nodes and a tree structure parameter. Finally, several real-time adjustment policies are designed to ensure that the node values on any path from the root to the leaves satisfy a consistency constraint. Tests show that the algorithm guarantees better statistical query accuracy and has higher algorithm efficiency than traditional algorithms.
[1] FUNG B C M, WANG K, CHEN R, et al. Privacy-preserving data publishing:A survey of recent developments[J]. ACM Computing Surveys, 2010, 42(4):14.
[2] DWORK C, NAOR M, PITASSI T, et al. Differential privacy under continual observation[C]//Proceedings of the 42nd ACM Symposium on Theory of Computing. Cambridge, Massachusetts, New York, USA:ACM, 2010:715-724.
[3] 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):1-24.
[4] CAO J N, XIAO Q, 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:ACM, 2013:191-202.
[5] 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:ACM, 2013:284-295.
[6] 张啸剑, 孟小峰. 基于差分隐私的流式直方图发布方法[J]. 软件学报, 2016,27(2):381-393.ZHANG X J, MENG X F. Streaming histogram publication method with differential privacy[J]. Journal of Software, 2016, 27(2):381-393.(in Chinese)
[7] KELLARIS G, PAPADOPOULOS S, XIAO X K, et al. Differentially private event sequences over infinite streams[J]. Proceedings of the VLDB Endowment, 2014, 7(12):1155-1166.
[8] CHAN T H H, LI M F, SHI E, et al. Differentially private continual monitoring of heavy hitters from distributed streams[C]//Proceedings of the 12th International Symposium on Privacy Enhancing Technologies. Vigo, Spain:Springer, 2012:140-159.
[9] WANG J, ZHU R B, LIU S B. A differentially private unscented Kalman filter for streaming data in IoT[J]. IEEE Access, 2018, 6:6487-6495.
[10] CHEN Y, MACHANAVAJJHALA A, HAY M, et al. PeGaSus:Data-adaptive differentially private stream processing[C]//Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. Dallas, Texas, USA:ACM, 2017:1375-1388.
[11] DWORK C. Differential privacy[C]//Proceedings of the 33rd International Colloquium on Automata, Languages and Programming. Venice, Italy:Springer, 2006:1-12.
[12] DWORK C, MCSHERRY F, NISSIM K, et al. Calibrating noise to sensitivity in private data analysis[C]//Proceedings of the 3rd Theory of Cryptography Conference on Theory of Cryptography. New York, USA:Springer, 2006:265-284.
[13] 周水庚, 李丰, 陶宇飞, 等. 面向数据库应用的隐私保护研究综述[J]. 计算机学报, 2009, 32(5):847-861.ZHOU S G, LI F, TAO Y F, et al. Privacy preservation in database application:A survey[J]. Chinese Journal of Computers, 2009, 32(5):847-861.(in Chinese)
[14] 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.
[15] 康健, 吴英杰, 黄泗勇, 等. 异方差加噪下的差分隐私直方图发布算法[J]. 计算机科学与探索, 2016, 10(6):786-798.KANG J, WU Y J, HUANG S Y, et al. Algorithm for differential privacy histogram publication with non-uniform private budget[J]. Journal of Frontiers of Computer Science and Technology, 2016, 10(6):786-798. (in Chinese)
