差分隐私二维数据流统计发布

doi:10.11772/j.issn.1001-9081.2015.01.0088

计算机应用 ›› 2015, Vol. 35 ›› Issue (1): 88-92.DOI: 10.11772/j.issn.1001-9081.2015.01.0088

差分隐私二维数据流统计发布

林富鹏, 吴英杰, 王一蕾, 孙岚

福州大学数学与计算机科学学院, 福州350108

收稿日期:2014-08-08 修回日期:2014-09-19 出版日期:2015-01-01 发布日期:2015-01-26
通讯作者: 吴英杰
作者简介:林富鹏(1990-),男,福建三明人,硕士研究生,主要研究方向:数据安全、隐私保护;吴英杰(1979-),男,福建安溪人,副教授,博士,主要研究方向:数据安全、数据挖掘、算法设计;王一蕾(1979-),女,福建福州人,讲师,硕士,主要研究方向:文本挖掘、数据安全、隐私保护;孙岚(1978-),女,陕西西安人,讲师,硕士,主要研究方向:系统优化、数据安全、隐私保护.
基金资助:
国家自然科学基金资助项目(61300026);福建省自然科学基金资助项目(2014J01230).

Differentially private statistical publication for two-dimensional data stream

LIN Fupeng, WU Yingjie, WANG Yilei, SUN Lan

College of Mathematics and Computer Science, Fuzhou University, Fuzhou Fujian 350108, China

Received:2014-08-08 Revised:2014-09-19 Online:2015-01-01 Published:2015-01-26

摘要/Abstract

摘要：

目前关于差分隐私数据流统计发布的研究仅考虑一维数据流,其方法无法直接用于解决二维数据流统计发布中可能存在的隐私泄露问题.针对此问题,首先提出面向固定长度二维数据流的差分隐私统计发布算法——PTDSS算法.该算法通过单次线性扫描数据流,以较低空间消耗计算出满足一定条件的二维数据流元组的统计频度,并经过敏感度分析添加适量的噪声使其满足差分隐私要求;接着在PTDSS算法的基础上,利用滑动窗口机制,设计出面向任意长度二维数据流的差分隐私连续统计发布算法——PTDSS-SW.理论分析与实验结果表明,所提算法可安全地实现二维数据流统计发布的隐私保护,同时统计发布结果的相对误差在10%~95%.

关键词: 数据流, 差分隐私, 统计发布, 滑动窗口, 隐私保护

Abstract:

Current research on statistical publication of differential privacy data stream only considers one-dimensional data stream. However, many applications require privacy protection publishing two-dimensional data stream, which makes traditional models and methods unusable. To solve the issue, firstly, a differential privacy statistical publication algorithm for fixed-length two-dimensional data stream, call PTDSS, was proposed. The tuple frequency of the two-dimensional data stream under certain condition was calculated by a one-time linear scan to the data stream with low-cost space. Basing on the result of sensitivity analysis, a certain amount of noise was added into the statistical results so as to meet the differential privacy requirement. After that, a differential privacy continuous statistical publication algorithm for any length two-dimensional data stream using sliding window model, called PTDSS-SW, was presented. The theoretical analysis and experimental results show that the proposed algorithms can safely preserve the privacy in the statistical publication of two-dimensional data stream and ensure the relative error of the released data in the range of 10% to 95%.

Key words: data stream, differential privacy, statistical publication, sliding window, privacy protection

中图分类号:

TP309.2

林富鹏, 吴英杰, 王一蕾, 孙岚. 差分隐私二维数据流统计发布[J]. 计算机应用, 2015, 35(1): 88-92.

LIN Fupeng, WU Yingjie, WANG Yilei, SUN Lan. Differentially private statistical publication for two-dimensional data stream[J]. Journal of Computer Applications, 2015, 35(1): 88-92.

参考文献

[1] DWORK C. Differential privacy [C]// Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, LNCS 4052. Berlin: Springer, 2006: 1-12.
[2] SWEENEY L. k-Anonymity: a model for protecting privacy [J]. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2002, 10(5): 557-570.
[3] MACHANAVAJJHALA A, GEHRKE J, KIFER D, et al. L-diversity: privacy beyond k-anonymity [C]// Proceedings of the 22nd International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 2006: 24-35.
[4] DWORK C. Differential privacy in new settings [C]// Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia: Society for Industrial and Applied Mathematics, 2010: 174-183.
[5] DWORK C, NAOR M, PITASSI T, et al. Differential privacy under continual observation [C]// Proceedings of the Forty-Second ACM Symposium on Theory of Computing. New York: ACM, 2010: 715-724.
[6] DWORK C, NAOR M, PITASSI T, et al. Pan-private streaming algorithms [C]// Proceedings of the First Symposium on Innovations in Computer Science. Beijing: Tsinghua University Press, 2010: 66-80.
[7] CHAN H T H, SHI E, SONG D. Private and continual release of statistics [C]// Proceedings of the 37th International Colloquium on Automata, Languages and Programming, LNCS 6199. Berlin: Springer, 2010: 405-417.
[8] CAO J, 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. New York: ACM, 2013: 191-202.
[9] SHI E, CHAN H T H, RIEFFEL E G, et al. Privacy-preserving aggregation of time-series data [EB/OL]. [2014-05-28]. https://www.cs.umd.edu/~elaine/docs/ndss2011.pdf.
[10] CHAN H T H, LI M, SHI E, et al. Differentially private continual monitoring of heavy hitters from distributed streams [C]// Proceedings of the 12th International Conference on Privacy Enhancing Technologies, LNCS 7384. Berlin: Springer, 2012: 140-159.
[11] FAN L, XIONG L. An adaptive approach to real-time aggregate monitoring with differential privacy [J]. IEEE Transactions on Knowledge and Data Engineering, 2012, 26(9): 2094-2106.
[12] FAN L, XIONG L. Real-time aggregate monitoring with differential privacy [C]// Proceedings of the 21st ACM International Conference on Information and Knowledge Management. New York: ACM, 2012: 2169-2173.
[13] NY J L, PAPPAS G J. Differentially private Kalman filtering [C]// Proceedings of 2012 50th Annual Allerton Conference on Communication, Control and Computing. Piscataway: IEEE, 2012: 1618-1625.
[14] FAN L, XIONG L. Differentially private anomaly detection with a case study on epidemic outbreak detection [C]// Proceedings of the 2013 IEEE 13th International Conference on Data Mining Workshops. Piscataway: IEEE, 2013: 833-840.
[15] GEHRKE J, KORN F, SRIVASTAVA D. On computing correlated aggregates over continual data stream [C]// Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2001: 13-14.
[16] McSHERRY F. Privacy integrated queries: an extensible platform for privacy-preserving data analysis [C]// Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2009: 19-30.
[17] BABCOCK B, BABU S, DATAR M, et al. Models and issues in data stream systems [C]// Proceedings of the Twenty-First ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. New York: ACM, 2002: 1-16.

差分隐私二维数据流统计发布

Differentially private statistical publication for two-dimensional data stream

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	陈恒恒, 倪志伟, 朱旭辉, 金媛媛, 陈千. 基于聚类分析的差分隐私高维数据发布方法[J]. 计算机应用, 2021, 41(9): 2578-2585.
[2]	李卓, 宋子晖, 沈鑫, 陈昕. 边缘计算支持下的移动群智感知本地差分隐私保护机制[J]. 计算机应用, 2021, 41(9): 2678-2686.
[3]	景兴红, 孙国栋, 何世彪, 廖勇. 基于滑窗滤波和多项式拟合的时变信道估计方法[J]. 计算机应用, 2021, 41(9): 2699-2704.
[4]	尹春勇, 张帼杰. 面向分布式漂移数据流的集成分类模型[J]. 计算机应用, 2021, 41(7): 1947-1955.
[5]	郭帅, 苏旸. 基于数据流的加密流量分类方法[J]. 计算机应用, 2021, 41(5): 1386-1391.
[6]	秦静, 安雯, 季长清, 汪祖民. 无线体域网隐私保护机制研究综述[J]. 计算机应用, 2021, 41(4): 970-975.
[7]	刘向宇, 夏国平, 夏秀峰, 宗传玉, 朱睿, 李佳佳. 个性化时空数据隐私保护[J]. 计算机应用, 2021, 41(3): 643-650.
[8]	张恩, 李会敏, 常键. 可验证的隐私保护k-means聚类方案[J]. 计算机应用, 2021, 41(2): 413-421.
[9]	陈锦宇, 刘兆伟. 基于改进投票证明共识协议的车联网系统[J]. 计算机应用, 2021, 41(1): 170-176.
[10]	马敏耀, 刘卓, 徐艺, 吴恋. 隐私保护整数区间位置关系判定问题[J]. 计算机应用, 2020, 40(9): 2657-2664.
[11]	吕佳玉, 竺智荣, 姚志强. 云计算环境下的双通道数据动态加密策略[J]. 计算机应用, 2020, 40(8): 2268-2273.
[12]	樊仲欣. 基于数据流的聚类趋势分析算法[J]. 计算机应用, 2020, 40(8): 2248-2254.
[13]	金波, 张志勇, 赵婷. 基于差分隐私的社交网络位置近邻查询方法[J]. 计算机应用, 2020, 40(8): 2340-2344.
[14]	马敏耀, 吴恋, 刘卓, 徐艺. 隐私保护整数点和区间关系判定问题[J]. 计算机应用, 2020, 40(7): 1983-1988.
[15]	龙洋洋, 陈玉玲, 辛阳, 豆慧. 基于联盟区块链的安全能源交易方案[J]. 计算机应用, 2020, 40(6): 1668-1673.