树索引数据差分隐私预算分配方法

doi:10.11772/j.issn.1001-9081.2018010014

计算机应用 ›› 2018, Vol. 38 ›› Issue (7): 1960-1966.DOI: 10.11772/j.issn.1001-9081.2018010014

树索引数据差分隐私预算分配方法

汪小寒^1,2, 韩慧慧^1,2, 张泽培^1,2, 俞庆英^1,2, 郑孝遥^1,2

1. 安徽师范大学计算机与信息学院, 安徽芜湖 241003;
2. 安徽师范大学网络与信息安全安徽省重点实验室, 安徽芜湖 241003

收稿日期:2018-01-04 修回日期:2018-03-03 出版日期:2018-07-10 发布日期:2018-07-12
通讯作者: 汪小寒
作者简介:汪小寒(1978-),女,安徽枞阳人,副教授,硕士,CCF会员,主要研究方向:智能计算、信息安全;韩慧慧(1992-),女,安徽阜阳人,硕士研究生,主要研究方向:信息安全;张泽培(1996-),男,安徽合肥人,硕士研究生,主要研究方向:信息安全。
基金资助:
国家自然科学基金资助项目（61702010，61772034）；安徽省自然科学基金资助项目（1708085MF156）；安徽师范大学创新基金资助项目（2017XJJ93）。

Differential privacy budget allocation method for data of tree index

WANG Xiaohan^1,2, HAN Huihui^1,2, ZHANG Zepei^1,2, YU Qingying^1,2, ZHENG Xiaoyao^1,2

1. School of Computer and Information, Anhui Normal University, Wuhu Anhui 241003, China;
2. Anhui Provincial Key Laboratory of Network and Information Security, Anhui Normal University, Wuhu Anhui 241003, China

Received:2018-01-04 Revised:2018-03-03 Online:2018-07-10 Published:2018-07-12
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61702010, 61772034), the Natural Science Foundation of Anhui Province (1708085MF156), the Innovation Foundation of Anhui Normal University (2017XJJ93).

摘要/Abstract

摘要： 树索引空间数据进行差分隐私保护时需要产生噪声，针对现有差分隐私预算采取均匀分配方式，普通用户无法个性化选择的问题，提出等差数列分配法和等比数列分配法两种分配隐私预算策略。首先，利用树结构索引空间数据；然后，用户根据隐私保护度的需要和查询精确度的需要，个性化设置相邻两层分配的隐私预算的差值或比值，动态调整隐私预算；最后，隐私预算分配给树的每一层，实现了个性化按需分配方式。理论分析和实验结果表明，与均匀分配方式相比，这两种方法分配隐私预算更加灵活，且等比数列分配法优于等差数列分配法。

关键词: 差分隐私, 隐私预算, 树索引, 等差数列分配法, 等比数列分配法

Abstract: Noise is required in differential privacy protection for spatial data with tree index. Most of the existing differential privacy budget methods adopt uniform allocation, and ordinary users can not personalize their choice. To solve this problem, an arithmetic sequence privacy budget allocation method and a geometric sequence privacy budget allocation method were proposed. Firstly, the spatial data was indexed by tree structure. Secondly, users could personalize the difference or ratio of privacy budgets assigned by two adjacent layers to dynamically adjust the privacy budget according to the needs of privacy protection and query accuracy. Finally, the privacy budget was allocated to each layer of tree to realize personalized and on-demand allocation. Theoretical analysis and experimental results show that these two methods are more flexible in the allocation of privacy budget than the uniform allocation method, and the geometric sequence allocation method is better than the arithmetic sequence allocation method.

Key words: differential privacy, privacy budget, tree index, arithmetic sequence allocation method, geometric sequence allocation method

中图分类号:

TP309.2

汪小寒, 韩慧慧, 张泽培, 俞庆英, 郑孝遥. 树索引数据差分隐私预算分配方法[J]. 计算机应用, 2018, 38(7): 1960-1966.

WANG Xiaohan, HAN Huihui, ZHANG Zepei, YU Qingying, ZHENG Xiaoyao. Differential privacy budget allocation method for data of tree index[J]. Journal of Computer Applications, 2018, 38(7): 1960-1966.

参考文献

[1] 方跃坚,朱锦钟,周文,等.数据挖掘隐私保护算法研究综述[J].信息网络安全,2017(2):6-11.(FANG Y J, ZHU J Z, ZHOU W, et al. A Survey on data mining privacy protection algorithms[J]. Information Network Security, 2017(2):6-11.)
[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] DWORK C, MCSHERRY F, NISSIM K. Calibrating noise to sensitivity in private data analysis[C]//TCC 2006:Proceedings of the Third Conference on Theory of Cryptography, LNCS 3876. Berlin:Springer, 2006:265-284.
[4] REN J, XIONG J B, YAO Z Q, et al. DPLK-means:a novel differential privacy K-means mechanism[C]//DSC 2017:Proceedings of the 2017 IEEE Second International Conference on Data Science in Cyberspace. Piscataway, NJ:IEEE, 2017:133-139.
[5] 任君,熊金波,姚志强.基于差分隐私模型的云数据副本安全控制方案[J].网络与信息安全学报,2017,3(5):38-46.(REN J, XIONG J B, YAO Z Q. Security control scheme for cloud data copy based on differential privacy model[J]. Chinese Journal of Network and Information Security, 2017, 3(5):38-46.)
[6] SIMMONS S, BERGER B. Realizing privacy preserving genome-wide association studies[J]. Bioinformatics, 2016, 32(9):1293-1300.
[7] HAY M, RASTOGI V, MIKLAU G, et al. Boosting the accuracy of differentially private histograms through consistency[J]. Proceedings of the VLDB Endowment, 2009, 3(1/2):1021-1032.
[8] XIAO X, WANG G, GEHRKE J. Differential privacy via wavelet transforms[J]. IEEE Transactions on Knowledge and Data Engineering, 2011, 23(8):1200-1214.
[9] CHEN R, FUNG B C M, DESAI B C. Differentially private transit data publication:a case study on the Montreal transportation system[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM, 2012:213-221.
[10] CHEN R, ACS G, CASTELLUCCIA C. Differentially private sequential data publication via variable-length n-grams[C]//Proceedings of the 2012 ACM Conference on Computer and Communications Security. New York:ACM, 2012:638-649.
[11] CORMODE G, PROCOPIUC C, SRIVASTAVA D, et al. Differentially private spatial decompositions[C]//Proceedings of the 28th International Conference on Data Engineering. Piscataway, NJ:IEEE, 2012:20-31.
[12] ZHANG J D, GHINITA G, CHI Y C. Differentially private location recommendations in geosocial networks[C]//Proceedings of the 28th International Conference on Mobile Data Management. Washington, DC:IEEE Computer Society, 2014:59-68.
[13] WANG J, LIU S, LI Y, et al. Differentially private spatial decompositions for geospatial point data[J]. China Communications, 2016, 13(4):97-107.
[14] GENG Q, VISWANATH P. The optimal noise-adding mechanism in differential privacy[J]. IEEE Transactions on Information Theory, 2016, 62(2):925-951.
[15] DWORK C, ROTH A. The algorithmic foundations of differential privacy[J]. Foundations and Trends in Theoretical Computer Science, 2014, 9(3/4):211-407.

树索引数据差分隐私预算分配方法

Differential privacy budget allocation method for data of tree index

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	陈恒恒, 倪志伟, 朱旭辉, 金媛媛, 陈千. 基于聚类分析的差分隐私高维数据发布方法[J]. 计算机应用, 2021, 41(9): 2578-2585.
[2]	李卓, 宋子晖, 沈鑫, 陈昕. 边缘计算支持下的移动群智感知本地差分隐私保护机制[J]. 计算机应用, 2021, 41(9): 2678-2686.
[3]	金波, 张志勇, 赵婷. 基于差分隐私的社交网络位置近邻查询方法[J]. 计算机应用, 2020, 40(8): 2340-2344.
[4]	涂子璇, 刘树波, 熊星星, 赵晶, 蔡朝晖. 可穿戴设备的数值型流数据差分隐私均值发布[J]. 计算机应用, 2020, 40(6): 1692-1697.
[5]	罗惠雯, 龙士工. 基于用户感兴趣区域的地理不可区分性的位置扰动算法[J]. 计算机应用, 2020, 40(3): 760-764.
[6]	李昆明, 王超迁, 倪巍伟, 鲍晓涵. 基于差分隐私的高精度直方图发布方法[J]. 计算机应用, 2020, 40(11): 3242-3248.
[7]	马方方, 刘树波, 熊星星, 牛晓光. 可穿戴设备数值型敏感数据本地差分隐私保护[J]. 计算机应用, 2019, 39(7): 1985-1990.
[8]	张书旋, 康海燕, 闫涵. 基于Skyline计算的社交网络关系数据隐私保护[J]. 计算机应用, 2019, 39(5): 1394-1399.
[9]	霍峥, 张坤, 贺萍, 武彦斌. 满足本地化差分隐私的众包位置数据采集[J]. 计算机应用, 2019, 39(3): 763-768.
[10]	郑孝遥, 陈冬梅, 刘雨晴, 尤浩, 汪祥舜, 孙丽萍. 基于差分隐私保护的谱聚类算法[J]. 计算机应用, 2018, 38(10): 2918-2922.
[11]	王红, 葛丽娜, 王苏青, 王丽颖, 张翼鹏, 梁竣程. 基于OPTICS聚类的差分隐私保护算法的改进[J]. 计算机应用, 2018, 38(1): 73-78.
[12]	李艳辉, 刘浩, 袁野, 王国仁. 基于差分隐私的频繁序列模式挖掘算法[J]. 计算机应用, 2017, 37(2): 316-321.
[13]	金凯忠, 彭慧丽, 张啸剑. 基于差分隐私的轨迹模式挖掘算法[J]. 计算机应用, 2017, 37(10): 2938-2945.
[14]	宋健, 许国艳, 夭荣朋. 基于差分隐私的数据匿名化隐私保护方法[J]. 计算机应用, 2016, 36(10): 2753-2757.
[15]	林富鹏, 吴英杰, 王一蕾, 孙岚. 差分隐私二维数据流统计发布[J]. 计算机应用, 2015, 35(1): 88-92.