PrivSPM： frequent sequential pattern mining algorithm under local differential privacy

doi:10.11772/j.issn.1001-9081.2022091365

Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (7): 2057-2064.DOI: 10.11772/j.issn.1001-9081.2022091365

Special Issue: 第39届CCF中国数据库学术会议(NDBC 2022)

• The 39th CCF National Database Conference (NDBC 2022) • Previous Articles Next Articles

PrivSPM： frequent sequential pattern mining algorithm under local differential privacy

Shuo HUANG, Yanhui LI(), Jianqiu CAO

School of Information Science and Engineering，Chongqing Jiaotong University，Chongqing 400074，China

Received:2022-09-12 Revised:2022-11-15 Accepted:2022-11-21 Online:2023-07-20 Published:2023-07-10
Contact: Yanhui LI
About author:HUANG Shuo， born in 1998， M. S. candidate. His research interests include data privacy， differential privacy.
LI Yanhui， born in 1989， Ph. D.， lecturer. Her research interests include data privacy， differential privacy， big data analysis.
CAO Jianqiu， born in 1967， M. S.， professor. His main research interests include graphics and image processing， information visualization， traffic informatization， intelligent control.
Supported by:
National Natural Science Foundation of China(62002036);Opening Project of Shanghai Key Laboratory of Integrated Administration Technologies for Information Security(AGK2020006);Natural Science Foundation of Chongqing(cstc2021jcyj-msxmX0859);Science and Technology Research Program of Chongqing Municipal Education Commission(KJQN202000707)

本地化差分隐私下的频繁序列模式挖掘算法PrivSPM

黄硕, 李艳辉(), 曹建秋

重庆交通大学信息科学与工程学院，重庆 400074

通讯作者: 李艳辉
作者简介:黄硕（1998—），男，河南漯河人，硕士研究生，主要研究方向：数据隐私、差分隐私；
李艳辉（1989—），女，黑龙江齐齐哈尔人，讲师，博士，主要研究方向：数据隐私、差分隐私、大数据分析；
曹建秋（1967—），男，湖南益阳人，教授，硕士，主要研究方向：图形图像处理、信息可视化、交通信息化、智能控制。
基金资助:
国家自然科学基金资助项目(62002036);上海市信息安全综合管理技术研究重点实验室开放课题(AGK2020006);重庆市自然科学基金资助项目(cstc2021jcyj-msxmX0859);重庆市教育委员会科学技术研究项目(KJQN202000707)

Abstract

Abstract:

Sequential data may contain a lot of sensitive information， so that directly mining frequent patterns of sequential data would carry significant risk to privacy of individuals. By resisting attackers with any background knowledge， Local Differential Privacy （LDP） can provide more comprehensive protection for sensitive information. Due to the inherent sequentiality and high-dimensionality， it is challenging to mine frequent sequential patterns with the application of LDP. To tackle this problem， a top-k frequent sequential pattern mining algorithm satisfying ε-LDP， called PrivSPM， was proposed. In this algorithm， filling and sampling technologies， adaptive frequency estimation algorithm and frequent item prediction technology were integrated to construct candidate item. Based on the new domain， an exponential mechanism based strategy was employed to perturb the user data， and the final frequent sequential patterns were identified by combining the frequency estimation algorithm. Theoretical analysis proves that the proposed algorithm satisfies ε-LDP. Experimental results on three real datasets demonstrate that PrivSPM algorithm performs better than the comparison algorithm on True Positive Rate （TPR） and Normalized Cumulative Rank （NCR）， and can improve the accuracy of mined results effectively.

Key words: Local Differential Privacy (LDP), privacy protection, frequent sequential pattern mining, exponential mechanism, data mining

摘要：

序列数据中可能包含大量敏感信息，因此直接对序列数据的频繁模式进行挖掘存在泄露用户隐私信息的风险。本地化差分隐私（LDP）能够抵御具有任意背景知识的攻击者，可以对敏感信息提供更全面的保护。序列数据内在序列性和高维度的特点为LDP应用于频繁序列模式挖掘带来了挑战。为解决这个问题，提出一种满足ε-LDP的top-k频繁序列模式挖掘算法PrivSPM。该算法结合填充和采样技术、自适应频率估计算法与频繁项预测技术来构造候选集；基于新域，利用基于指数机制的策略对用户数据进行扰动，并结合频率估计算法识别最终的频繁序列模式。理论分析证明了该算法满足ε-LDP。在3个真实数据集上的实验结果表明，PrivSPM算法在纳真率（TPR）和归一化累积排名（NCR）上明显高于对比算法，能有效提高挖掘结果的准确度。

关键词: 本地化差分隐私, 隐私保护, 频繁序列模式挖掘, 指数机制, 数据挖掘

CLC Number:

TP311.13

Shuo HUANG, Yanhui LI, Jianqiu CAO. PrivSPM： frequent sequential pattern mining algorithm under local differential privacy[J]. Journal of Computer Applications, 2023, 43(7): 2057-2064.

黄硕, 李艳辉, 曹建秋. 本地化差分隐私下的频繁序列模式挖掘算法PrivSPM[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2057-2064.

Figures/Tables 7

Tab. 1 Description of three datasets

数据集名称	$\| D B \|$	$\| X \|$	Avg（ $s$ ）
kosarak	990 002	41 270	8.1
MSNBC	989 818	17	4.7
retail	88 162	16 479	11.3

Tab. 1 Description of three datasets

数据集名称	$\| D B \|$	$\| X \|$	Avg（ $s$ ）
kosarak	990 002	41 270	8.1
MSNBC	989 818	17	4.7
retail	88 162	16 479	11.3

Fig. 1 Candidate item identification on kosarak dataset

Fig. 2 Candidate item identification on retail dataset

Fig. 3 Changes in TPR when k=30

Fig. 4 Changes in NCR when k=30

Fig. 5 Changes in Err when k=3

Fig. 6 Influence of k on utility on kosarak dataset

References 32

1	AGRAWAL R， SRIKANT R. Mining sequential patterns ［C］// Proceedings of the 11th International Conference on Data Engineering. Piscataway： IEEE， 1995： 3-14.
2	叶青青，孟小峰，朱敏杰，等. 本地化差分隐私研究综述［J］. 软件学报， 2018， 29 （7）： 1981-2005.
	YE Q Q， MENG X F， ZHU M J， et al. Survey on local differential privacy［J］. Journal of Software， 2018， 29 （7）： 1981-2005.
3	SWEENEY L. k-Anonymity： a model for protecting privacy［J］. International Journal of Uncertainty， Fuzziness and Knowledge-Based Systems， 2002， 10 （5）： 557-570. 10.1142/s0218488502001648
4	GANTA S R， KASIVISWANATHAN S P， SMITH A. Composition attacks and auxiliary information in data privacy ［C］// Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2008： 265-273. 10.1145/1401890.1401926
5	WONG R C W， FU A W C， WANG K， et al. Can the utility of anonymized data be used for privacy breaches？［J］. ACM Transactions on Knowledge Discovery from Data， 2011， 5 （3）： No.16. 10.1145/1993077.1993080
6	DWORK C. Differential privacy ［C］// Proceedings of the 2006 International Colloquium on Automata， Languages， and Programming， LNCS 4052. Berlin： Springer， 2006： 1-12.
7	XIA H H， HUANG W C， XIONG Y， et al. Mining frequent sequential patterns with local differential privacy［J］. International Journal of Network Security， 2021， 23 （5）： 817-829.
8	WANG T， HU Z. Local differential privacy-based frequent sequence mining［J］. Journal of King Saud University — Computer and Information Sciences， 2022， 34 （6 Pt B）： 3591-3601. 10.1016/j.jksuci.2022.04.013
9	SRIKANT R， AGRAWAL R. Mining sequential patterns： generalizations and performance improvements ［C］// Proceedings of the 1996 International Conference on Extending Database Technology， LNCS 1057. Berlin： Springer， 1996： 1-17.
10	ZAKI M J. SPADE： an efficient algorithm for mining frequent sequences［J］. Machine Learning， 2001， 42 （1/2）： 31-60.
11	FOURNIER-VIGER P， GOMARIZ A， CAMPOS M， et al. Fast vertical mining of sequential patterns using co-occurrence information ［C］// Proceedings of the 2014 Pacific-Asia Conference on Knowledge Discovery and Data Mining， LNCS 8443. Cham： Springer， 2014： 40-52.
12	BONOMI L， XIONG L. A two-phase algorithm for mining sequential patterns with differential privacy ［C］// Proceedings of the 22nd ACM International Conference on Information and Knowledge Management. New York： ACM， 2013： 269-278. 10.1145/2505515.2505553
13	CHENG X， SU S， XU S， et al. Differentially private maximal frequent sequence mining［J］. Computers and Security， 2015， 55： 175-192. 10.1016/j.cose.2015.08.005
14	XU S Z， CHENG X， SU S， et al. Differentially private frequent sequence mining［J］. IEEE Transactions on Knowledge and Data Engineering， 2016， 28 （11）： 2910-2926. 10.1109/tkde.2016.2601106
15	李艳辉，刘浩，袁野，等. 基于差分隐私的频繁序列模式挖掘算法［J］. 计算机应用， 2017， 37 （2）： 316-321， 340. 10.11772/j.issn.1001-9081.2017.02.0316
	LI Y H， LIU H， YUAN Y， et al. Frequent sequence pattern mining with differential privacy［J］. Journal of Computer Applications， 2017， 37 （2）： 316-321， 340. 10.11772/j.issn.1001-9081.2017.02.0316
16	WARNER S L. Randomized response： a survey technique for eliminating evasive answer bias［J］. Journal of the American Statistical Association， 1965， 60 （309）： 63-69. 10.1080/01621459.1965.10480775
17	ERLINGSSON Ú， PIHUR V， KOROLOVA A. RAPPOR： randomized aggregatable privacy-preserving ordinal response ［C］// Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security. New York： ACM， 2014： 1054-1067. 10.1145/2660267.2660348
18	BASSILY R， SMITH A. Local， private， efficient protocols for succinct histograms ［C］// Proceedings of the 47th Annual ACM Symposium on Theory of Computing. New York： ACM， 2015： 127-135. 10.1145/2746539.2746632
19	WANG T H， BLOCKI J， LI N H， et al. Locally differentially private protocols for frequency estimation ［C］// Proceedings of the 26th USENIX Security Symposium. Berkeley： USENIX Association， 2017： 729-745.
20	WANG T H， LI N H， JHA S. Locally differentially private heavy hitter identification［J］. IEEE Transactions on Dependable and Secure Computing， 2021， 18 （2）： 982-993. 10.1109/tdsc.2019.2927695
21	ZHAO D， ZHAO S Y， CHEN H， et al. Efficient protocols for heavy hitter identification with local differential privacy［J］. Frontiers of Computer Science， 2022， 16 （5）： No.165825. 10.1007/s11704-021-0412-y
22	YE Q Q， HU H B， MENG X F， et al. PrivKV： key-value data collection with local differential privacy ［C］// Proceedings of the 2019 IEEE Symposium on Security and Privacy. Piscataway： IEEE， 2019： 317-331. 10.1109/sp.2019.00018
23	NGUYÊN T T， XIAO X K， YANG Y， et al. Collecting and analyzing data from smart device users with local differential privacy［EB/OL］. （2016-06-16）［2021-09-27］. .
24	GU X L， LI M， CHENG Y Q， et al. PCKV： locally differentially private correlated key-value data collection with optimized utility ［C］// Proceedings of the 29th USENIX Security Symposium. Berkeley： USENIX Association， 2020： 967-984.
25	QIN Z， YANG Y， YU T， et al. Heavy hitter estimation over set-valued data with local differential privacy ［C］// Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. New York： ACM， 2016： 192-203. 10.1145/2976749.2978409
26	WANG S W， HUANG L S， NIE Y W， et al. PrivSet： set-valued data analyses with locale differential privacy ［C］// Proceedings of the 2018 IEEE Conference on Computer Communications. Piscataway： IEEE， 2018： 1088-1096. 10.1109/infocom.2018.8486234
27	WANG S W， QIAN Y Q， DU J C， et al. Set-valued data publication with local privacy： tight error bounds and efficient mechanisms［J］. Proceedings of the VLDB Endowment， 2020， 13 （8）： 1234-1247. 10.14778/3389133.3389140
28	WANG T H， LI N H， JHA S. Locally differentially private frequent itemset mining ［C］// Proceedings of the 2018 IEEE Symposium on Security and Privacy. Piscataway： IEEE， 2018： 127-143. 10.1109/sp.2018.00035
29	AFROSE S， HASHEM T， ALI M E. Frequent itemsets mining with a guaranteed local differential privacy in small datasets ［C］// Proceedings of the 33rd International Conference on Scientific and Statistical Database Management. New York： ACM， 2021： 232-236. 10.1145/3468791.3468807
30	LIU H J， CUI L W， MA X B， et al. Frequent itemset mining of user's multi-attribute under local differential privacy［J］. Computers， Materials & Continua， 2020， 65 （1）： 369-385. 10.32604/cmc.2020.010987
31	LI N H， QARDAJI W， SU D. On sampling， anonymization， and differential privacy or， k-anonymization meets differential privacy ［C］// Proceedings of the 7th ACM Symposium on Information， Computer and Communications Security. New York： ACM， 2012： 32-33. 10.1145/2414456.2414474
32	WANG N， XIAO X， YANG Y， et al. PrivSuper： a superset-first approach to frequent itemset mining under differential privacy［C］// Proceedings of the 2017 IEEE 33rd International Conference on Data Engineering. Piscataway： IEEE， 2017： 809-820. 10.1109/icde.2017.131

[1]	Huanhuan LI, Tianqiang HUANG, Xuemei DING, Haifeng LUO, Liqing HUANG. Public traffic demand prediction based on multi-scale spatial-temporal graph convolutional network [J]. Journal of Computer Applications, 2024, 44(7): 2065-2072.
[2]	Xuebin CHEN, Zhiqiang REN, Hongyang ZHANG. Review on security threats and defense measures in federated learning [J]. Journal of Computer Applications, 2024, 44(6): 1663-1672.
[3]	Yao DONG, Yixue FU, Yongfeng DONG, Jin SHI, Chen CHEN. Survey of incomplete multi-view clustering [J]. Journal of Computer Applications, 2024, 44(6): 1673-1682.
[4]	Peiqian LIU, Shuilian WANG, Zihao SHEN, Hui WANG. Location privacy protection algorithm based on trajectory perturbation and road network matching [J]. Journal of Computer Applications, 2024, 44(5): 1546-1554.
[5]	Gaimei GAO, Jin ZHANG, Chunxia LIU, Weichao DANG, Shangwang BAI. Privacy protection scheme for crowdsourced testing tasks based on blockchain and CP-ABE policy hiding [J]. Journal of Computer Applications, 2024, 44(3): 811-818.
[6]	Haifeng MA, Yuxia LI, Qingshui XUE, Jiahai YANG, Yongfu GAO. Attribute-based encryption scheme for blockchain privacy protection [J]. Journal of Computer Applications, 2024, 44(2): 485-489.
[7]	Keshuai YANG, Youxi WU, Meng GENG, Jingyu LIU, Yan LI. Top-k high average utility sequential pattern mining algorithm under one-off condition [J]. Journal of Computer Applications, 2024, 44(2): 477-484.
[8]	Yifan WANG, Shaofu LIN, Yunjiang LI. Highway free-flow tolling method based on blockchain and zero-knowledge proof [J]. Journal of Computer Applications, 2024, 44(12): 3741-3750.
[9]	Yiting WANG, Wunan WAN, Shibin ZHANG, Jinquan ZHANG, Zhi QIN. Linkable ring signature scheme based on SM9 algorithm [J]. Journal of Computer Applications, 2024, 44(12): 3709-3716.
[10]	Jing LIANG, Wunan WAN, Shibin ZHANG, Jinquan ZHANG, Zhi QIN. Traceability storage model of charity system oriented to master-slave chain [J]. Journal of Computer Applications, 2024, 44(12): 3751-3758.
[11]	Peng FANG, Fan ZHAO, Baoquan WANG, Yi WANG, Tonghai JIANG. Development， technologies and applications of blockchain 3.0 [J]. Journal of Computer Applications, 2024, 44(12): 3647-3657.
[12]	Rui GAO, Xuebin CHEN, Zucuan ZHANG. Dynamic social network privacy publishing method for partial graph updating [J]. Journal of Computer Applications, 2024, 44(12): 3831-3838.
[13]	Miao JIA, Zhongyuan YAO, Weihua ZHU, Tingting GAO, Xueming SI, Xiang DENG. Progress and prospect of zero-knowledge proof enabling blockchain [J]. Journal of Computer Applications, 2024, 44(12): 3669-3677.
[14]	Xuebin CHEN, Changsheng QU. Overview of backdoor attacks and defense in federated learning [J]. Journal of Computer Applications, 2024, 44(11): 3459-3469.
[15]	Hui ZHOU, Yuling CHEN, Xuewei WANG, Yangwen ZHANG, Jianjiang HE. Deep shadow defense scheme of federated learning based on generative adversarial network [J]. Journal of Computer Applications, 2024, 44(1): 223-232.

PrivSPM： frequent sequential pattern mining algorithm under local differential privacy

本地化差分隐私下的频繁序列模式挖掘算法PrivSPM

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 32

Related Articles 15

Recommended Articles

Metrics