Efficient protocols for heavy hitter identification with local differential privacy

作     者：Dan ZHAO Suyun ZHAO Hong CHEN Ruixuan LIU Cuiping LI Wenjuan LIANG Dan ZHAO;Suyun ZHAO;Hong CHEN;Ruixuan LIU;Cuiping LI;Wenjuan LIANG

作者机构：Key Laboratory of Data Engineering and Knowledge Engineering of Ministry of EducationRenmin University of ChinaBeijing 100872China School of InformationRenmin University of ChinaBeijing 100872China 

出 版 物：《Frontiers of Computer Science》 (中国计算机科学前沿（英文版）)

年 卷 期：2022年第16卷第5期

页      面：193-203页

核心收录：

学科分类：0839[工学-网络空间安全] 08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：This work was supported by the National Key R&D Program of China(2018YFB1004401) the National Natural Science Foundation of China(NSFC)(Grant Nos.61772537,61772536,62072460,and 62076245) Beijing Natural Science Foundation(4212022) 

主　　题：local differential privacy frequency oracle heavy hitter 

摘      要：Local differential privacy(LDP),which is a technique that employs unbiased statistical estimations instead of real data,is usually adopted in data collection,as it can protect every user’s privacy and prevent the leakage of sensitive *** segment pairs method(SPM),multiple-channel method(MCM)and prefix extending method(PEM)are three known LDP protocols for heavy hitter identification as well as the frequency oracle(FO)problem with large ***,the low scalability of these three LDP algorithms often limits their ***,communication and computation strongly affect their ***,excessive grouping or sharing of privacy budgets makes the results *** address the abovementioned problems,this study proposes independent channel(IC)and mixed independent channel(MIC),which are efficient LDP protocols for FO with a large *** design a flexible method for splitting a large domain to reduce the number of ***,we employ the false positive rate with interaction to obtain an accurate *** experiments demonstrate that IC outperforms all the existing solutions under the same privacy guarantee while MIC performs well under a small privacy budget with the lowest communication cost.