Hadamard Encoding Based Frequent Itemset Mining under Local Differential Privacy  

作　　者：赵丹 赵素云 陈红 刘睿瑄 李翠平 张晓莹 Dan Zhao;Su-Yun Zhao;Hong Chen;Rui-Xuan Liu;Cui-Ping Li;Xiao-Ying Zhang(Institute of Scientific and Technical Information of China,Beijing 100038,China;Key Laboratory of Data Engineering and Knowledge Engineering(Ministry of Education),School of Information,Renmin University of China,Beijing 100872,China)

机构地区：[1]Institute of Scientific and Technical Information of China,Beijing 100038,China [2]Key Laboratory of Data Engineering and Knowledge Engineering(Ministry of Education),School of Information,Renmin University of China,Beijing 100872,China

出　　处：《Journal of Computer Science & Technology》2023年第6期1403-1422,共20页计算机科学技术学报（英文版）

基　　金：supported by the National Natural Science Foundation of China under Grant Nos.61772537,61772536,62072460,62076245,and 62172424;the National Key Research and Development Program of China under Grant No.2018YFB1004401;Beijing Natural Science Foundation under Grant No.4212022.

摘　　要：Local differential privacy(LDP)approaches to collecting sensitive information for frequent itemset mining(FIM)can reliably guarantee privacy.Most current approaches to FIM under LDP add"padding and sampling"steps to obtain frequent itemsets and their frequencies because each user transaction represents a set of items.The current state-of-the-art approach,namely set-value itemset mining(SVSM),must balance variance and bias to achieve accurate results.Thus,an unbiased FIM approach with lower variance is highly promising.To narrow this gap,we propose an Item-Level LDP frequency oracle approach,named the Integrated-with-Hadamard-Transform-Based Frequency Oracle(IHFO).For the first time,Hadamard encoding is introduced to a set of values to encode all items into a fixed vector,and perturbation can be subsequently applied to the vector.An FIM approach,called optimized united itemset mining(O-UISM),is pro-posed to combine the padding-and-sampling-based frequency oracle(PSFO)and the IHFO into a framework for acquiring accurate frequent itemsets with their frequencies.Finally,we theoretically and experimentally demonstrate that O-UISM significantly outperforms the extant approaches in finding frequent itemsets and estimating their frequencies under the same privacy guarantee.

关 键 词：local differential privacy frequent itemset mining frequency oracle 

分 类 号：TP39[自动化与计算机技术—计算机应用技术]