面向频繁模式挖掘的差分隐私保护研究综述

doi:10.3969/j.issn.1000-436x.2014.10.023

Abstract

Abstract:

Frequent pattern mining is an exploratory problem in the field of data mining.However,directly releasing the discovered frequent patterns and the corresponding true supports may reveal the individuals’ privacy.The state-of-the-art solution for this problem is differential privacy,which offers a strong degree of privacy protection by adding noise.Firstly,the theoretical basis of differential privacy was introduced.Then,three representative frequent pattern mining methods under differential privacy were summarized and compared in detail.Finally,some future research directions were discussed.

Key words: differential privacy, privacy protection, frequent pattern, data mining

Li-ping DING,Guo-qing LU. Survey of differential privacy in frequent pattern mining[J]. Journal on Communications, 2014, 35(10): 200-209.

Figures/Tables 9

步骤	PT-Exp策略	PT-Lap策略
1	以概率 $\Pr [p] \propto \exp (\frac{ε n}{4 k} \hat{f} (p))$ 从C中无放回执行k次选择操作得到top-k频繁项集	对C 中所有项集添加大小为Lap(4k/εn)拉普拉斯噪音后重新获取top-k频繁项集
2	对k个项集的真实计数分别添加大小为Lap(2k/εn)拉普拉斯噪音	对 k 个项集的真实计数分别添加大小为Lap(2k/εn) 拉普拉斯噪音

方法名称	主要技术	主要优点	主要缺点	ε分配	算法性能
STM-Full	前缀树划分	支持多维数据依赖计数查询；精度高	忽视轨迹时间戳信息，实用性差；前缀树冗余	拉普拉斯机制；ε线性分配	O (\|D\|\|L\|)
Prefix-Hybrid	混合粒度前缀树划分	支持多维数据依赖计数查询；精度高	忽视轨迹时间戳信息，实用性差；前缀树冗余	拉普拉斯机制；ε划分为两份，混合分配	O (\|D\|\|L\|)
N-gram	变长N-gram模型	支持多维数据依赖计数查询；精度高	容易受到序列维度影响；有一定信息丢失	拉普拉斯机制；ε自适应分配	O (\|D\|\|L\|)
PT-Sample	数据变换和推理求精	支持频繁前缀树和序列模式挖掘；精度高	数据变换过程中存在信息丢失	拉普拉斯机制；ε划分为两份，混合分配	$O ({\| D ‖ L \|}^{h_{\max} + 1})$

References 43

[1]	HAN J , KAMBER M , PEI J . Data Mining:Concepts and Techniques[M]. Morgan kaufmann, 2006.
[2]	DWORK C . Differential privacy[A]. Proc of the 33rd International Colloquium on Automata,Languages and Programming[C]. Berlin:Spinger-Verlag, 2006.
[3]	熊平, 朱天清, 王晓峰 . 差分隐私保护及其应用[J]. 计算机学报, 2014,37(1): 101-122. XIONG P , ZHU T Q , WANG X F . A survey on differential privacy and applications[J]. Chinese Journal of Computers, 2014,37(1): 101-122.
[4]	张啸剑, 孟小峰 . 面向数据发布和分析的差分隐私保护研究综述[J]. 计算机学报, 2014,37(4): 927-949. ZHANG X J , MENG X F . Differential privacy in data publication and analysis[J]. Chinese Journal of Computers, 2014,37(4): 927-949.
[5]	BLUM A , DWORK C , McSHERRY F ,et al. Practical privacy:the SuLQ framework[A]. Proc of the 24th ACM SIGMOD International Conference on Management of Data/Principles of Database Systems[C]. NewYork: ACM Press, 2005. 128-138.
[6]	BLUM A , LIGETT K , ROTH A . A Learning theory approach to non-interactive database privacy[A]. Proc of the 40th Annual ACM Symposium on Theory of Computing(STOC)[C]. Victoria,British Columbia,Canada, 2008. 351-360.
[7]	DWORK C . A firm foundation for private data analysis[J]. Communications of the ACM, 2011,54(1): 86-95.
[8]	NGUYEN H H , KIM J , KIM Y . Differential privacy in practice[J]. Journal of Computing Science and Engineering, 2013,7(3): 177-186.
[9]	DWORK C , MCSHERRY F , NISSIM K ,et al. Calibrating noise to sensitivity in private data analysis[A]. TCC[C]. 2006. 265-284.
[10]	MCSHERRY F , TALWAR K . Mechanism design via differential privacy[A]. FOCS[C]. 2007. 94-103.
[11]	DWORK C , NAOR M , VADHAN S . The privacy of the analyst and the power of the state[A]. 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS)[C]. 2012. 400-409.
[12]	GHOSH A , ROUGHGARDEN T , SUNDARARAJAN M . Universally utility-maximizing privacy mechanisms[A]. Proceedings of the 41st Annual ACM Symposium on Theory of Computing[C]. ACM, 2009. 351-360.
[13]	LI C , HAY M , RASTOGI V ,et al. Optimizing linear counting queries under differential privacy[A]. Proceedings of the 29th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems[C]. 2010. 123-134.
[14]	ZHANG J , ZHANG Z , XIAO X ,et al. Functional mechanism:regression analysis under differential privacy[J]. Proceedings of the VLDB Endowment, 2012,5(11): 1364-1375.
[15]	MCSHERRY F . Privacy integrated queries:an extensible platform for privacy-preserving data analysis WWW[A]. SIGMOD Conference[C]. 2009. 19-30.
[16]	KIFER D , MACHANAVAJJHALA A . No free lunch in data privacy[A]. Proceedings of the 2011 ACM SIGMOD International Conference on Management of data[C]. 2011. 193-204.
[17]	AGRAWAL R , SRIKANT R . Fast algorithms for mining association rules[A]. Proc 20th Int Conf Very Large Data Bases[C]. 1994. 487-499.
[18]	HAN J , PEI J , YIN Y . Mining frequent patterns without candidate generation[J]. ACM SIGMOD Record, 2000,29(2): 1-12.
[19]	BHASKAR R , LAXMAN S , SIMTH A ,et al. Discovering frequent patterns in sensitive data[A]. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (SIGKDD)[C]. Washington,DC,USA, 2010. 503-512.
[20]	LI N , QARDAJI W , SU D ,et al. Privbasis:frequent itemset mining with differential privacy[A]. Proceedings of the 38th Conference of Very Large Databases (VLDB)[C]. Istanbul,Turkey, 2012. 1340-1351.
[21]	张啸剑, 王淼, 孟小峰 . 差分隐私保护下一种精确挖掘 top-k 频繁模式方法[J]. 计算机研究与发展, 2014,51(1): 104-114. ZHANG X J , WANG M , MENG X J . An accurate method for mining top-k frequent pattern under differential privacy[J]. Journal of Computer Research and Develoment, 2014,51(1): 104-114.
[22]	ZENG C , NAUGHTON J , CAI J . Y:On differentially private frequent itemset mining[J]. PVLDB, 2012,6(1): 25-36.
[23]	CHEN R , MOHAMMED N , FUNG B C M ,et al. Publishing set-valued data via differential privacy[A]. Proceedings of the 37th Conference of Very Large Databases(VLDB)[C]. Seattle,Washington,USA, 2011. 1087-1098.
[24]	HAN X , WANG M , ZHANG X ,et al. Differentially private top-k query over MapReduce[A]. Proceedings of the 4th International Workshop on Cloud Data Management[C]. 2012. 25-32.
[25]	AGRAWAL R , SRIKANT R . Mining sequential patterns[A]. Proceedings of the 11th International Conference on Data Engineering IEEE[C]. 1995. 3-14.
[26]	CHEN R , FUNG B , DESAI B C . Differentially private trajectory data publication[EB/OL]. . 2020.
[27]	CHEN R,áCS G , CASTELLUCCIA C . Differentially private sequential data publication via variable-length n-grams[A]. CCS[C]. 2012. 638-649.
[28]	BONOMI L , XIONG L , CHEN R ,et al. Frequent grams based embedding for privacy preserving record linkage[A]. CIKM[C]. 2012. 1597-1601.
[29]	BONOMI L , XIONG L . A two-phase algorithm for mining sequential patterns with differential privacy[A]. CIKM[C]. 2013. 269-278.
[30]	BONOMI L . Mining frequent patterns with differential privacy[J]. PVLDB, 2013,6(12): 1422-1427.
[31]	CHEN R , FUNG B , DESAI B C ,et al. Differentially private transit data publication:a case study on the montreal transportation system[A]. Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C]. ACM, 2012: 213-221.
[32]	HAN J , CHENG H , XIN D ,et al. Frequent pattern mining:current status and future directions[J]. Data Mining and Knowledge Discovery, 2007,15(1): 55-86.
[33]	SHEN ET , YU T . Mining frequent graph patterns with differential privacy[A]. KDD[C]. 2013. 545-553.
[34]	DWORK C , KENTHAPADI K , MCSHERRY F ,et al. Our Data,Ourselves:Privacy Via Distributed Noise Generation[M]. Springer Berlin Heidelberg, 2006. 486-503.
[35]	FRIEDMAN A , SCHUSTER A . Data mining with differential privacy[A]. Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C]. ACM, 2010. 493-502.
[36]	MOHAMMED N , CHEN R , FUNG B ,et al. Differentially private data release for data mining[A]. Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C]. 2011. 493-501.
[37]	NISSIM K , RASKHODNIKOVA S , SMITH A . Smooth sensitivity and sampling in private data analysis[A]. Proceedings of the 39th Annual ACM Symposium on Theory of Computing[C]. 2007. 75-84.
[38]	李杨, 郝志峰, 温雯 . 差分隐私保护 k-means 聚类方法研究[J]. 计算机科学, 2013,40(3): 287-290. LI Y , HAO ZF , WEN W . Research on differential privacy preserving k-means clustering[J]. Computer Science, 2013,40(3): 287-290.
[39]	GUPTA A , LIGETT K , MCSHERRY F ,et al. Differentially private combinatorial optimization[A]. Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms.Society for Industrial and Applied Mathematics[C]. 2010. 1106-1125.
[40]	MOHAN P , THAKURTA A , SHI E ,et al. GUPT:privacy preserving data analysis made easy[A]. Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data[C]. 2012. 349-360.
[41]	HO S S , RUAN S . Differential privacy for location pattern mining[A]. Proceedings of the 4th ACM SIGSPATIAL International Workshop on Security and Privacy in GIS and LBS {SPRINGL)[C]. Chicago,IL,USA, 2011. 17-24.
[42]	HO S S . Preserving privacy for moving objects data mining[A]. 2012 IEEE International Conference on Intelligence and Security Informatics (ISI)[C]. 2012. 135-137.
[43]	ROY I , SETTY S T V , KILZER A ,et al. Airavat:security and privacy for MapReduce[A]. Proceedings of the 7th USENIX Conference on Networked Systems Design and Implementation[C]. USENIX Association, 2010. 20-20.

Metrics

Recommended 0

No Suggested Reading articles found!

方法名称	主要技术	主要优点	主要缺点	ε分配	算法性能
TF	截断频率	实现简单，精度高	处理较大k值或l时性能与效率比较差；未考虑记录本身长度带来的影响	指数机制、拉普拉斯机制；ε均分为2份，平均分配	O (k′\|D\|)
PrivBasis	θ-基映射	性能和效率优于TF	难以兼顾隐私保护与模式可用性的不足；未考虑记录本身长度带来的影响	拉普拉斯机制；ε平均分配	O (w\|D\|)
DP-topkP	一致性约束	一致性约束输出结果，精度较高	处理较大k值或l性能与效率比较差；未考虑记录本身长度带来的影响	指数机制、拉普拉斯机制；ε被划分为2份，平均分配	O (k′\|D\|)
SmartTrunc	事务截断	规约数据集，精度高	扩展性比较差	拉普拉斯机制；ε平均分配	O(\|D\|\|L\|)
DiffPart	分类树划分	发布精度高，扩展性高	仅支持计数查询；没有考虑不同项之间的语义关联	拉普拉斯机制；ε均分为2份，自适应分配	O (\|D\|\|L\|)
DiffMR	一致性约束	支持MapReduce分布式查询，实现简单	只支持简单计数查询；处理较大k值或l时性能与效率比较差	指数机制、拉普拉斯机制；ε线性分配	O (k′\|D\|)

Survey of differential privacy in frequent pattern mining

RichHTML

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

Figures/Tables 9

References 43

Related Articles 15

Metrics

Recommended 0

[1]	Xindi MA, Qinghua LI, Qi JIANG, Zhuo MA, Sheng GAO, Youliang TIAN, Jianfeng MA. Byzantine-robust federated learning over Non-IID data [J]. Journal on Communications, 2023, 44(6): 138-153.
[2]	Tao FENG, Liqiu CHEN, Junli FANG, Jianming SHI. Blockchain data sharing scheme based on localized difference privacy and attribute-based searchable encryption [J]. Journal on Communications, 2023, 44(5): 224-233.
[3]	Shengxing YU, Zekai CHEN, Zhong CHEN, Ximeng LIU. DAGUARD: distributed backdoor attack defense scheme under federated learning [J]. Journal on Communications, 2023, 44(5): 110-122.
[4]	Baiji HU, Xiaojuan ZHANG, Yuancheng LI, Rongxin LAI. Multi-function supported privacy protection data aggregation scheme for V2G network [J]. Journal on Communications, 2023, 44(4): 187-200.
[5]	Ming XU, Baojun ZHANG, Yiming WU, Chenduo YING, Ning ZHENG. Cyber attacks and privacy protection distributed consensus algorithm for multi-agent systems [J]. Journal on Communications, 2023, 44(3): 117-127.
[6]	Shufen ZHANG, Yanling DONG, Jingcheng XU, Haoshi WANG. AdaBoost algorithm based on target perturbation [J]. Journal on Communications, 2023, 44(2): 198-209.
[7]	Lingtao TANG, Di WANG, Shengyun LIU. Data augmentation scheme for federated learning with non-IID data [J]. Journal on Communications, 2023, 44(1): 164-176.
[8]	Chengsheng YUAN, Qiang GUO, Zhangjie FU. Copyright protection algorithm based on differential privacy deep fake fingerprint detection model [J]. Journal on Communications, 2022, 43(9): 181-193.
[9]	Hanyi WANG, Xiaoguang LI, Wenqing BI, Yahong CHEN, Fenghua LI, Ben NIU. Multi-level local differential privacy algorithm recommendation framework [J]. Journal on Communications, 2022, 43(8): 52-64.
[10]	Xuewang ZHANG, Zhihong LI, Jinzhao LIN. Privacy protection scheme based on fair blind signature and hierarchical encryption for consortium blockchain [J]. Journal on Communications, 2022, 43(8): 131-141.
[11]	Yong ZHANG, Dandan LI, Lu HAN, Xiaohong HUANG. Privacy-protected crowd-sensed data trading algorithm [J]. Journal on Communications, 2022, 43(5): 1-13.
[12]	Jifeng WANG, Guofeng WANG. Research on ciphertext search and sharing technology in edge computing mode [J]. Journal on Communications, 2022, 43(4): 227-238.
[13]	Huamin FENG, Rui SHI, Feng YUAN, Yanjun LI, Yang YANG. Efficient strong privacy protection and transferable attribute-based ticket scheme [J]. Journal on Communications, 2022, 43(3): 63-75.
[14]	Haiyan KANG, Yuanrui JI. Research on federated learning approach based on local differential privacy [J]. Journal on Communications, 2022, 43(10): 94-105.
[15]	Zhongping ZHANG, Sen LI, Weixiong LIU, Shuxia LIU. Outlier detection algorithm based on fast density peak clustering outlier factor [J]. Journal on Communications, 2022, 43(10): 186-195.