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 information.The 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 domains.However,the low scalability of these three LDP algorithms often limits their application.Specifically,communication and computation strongly affect their effici-ency.Moreover,excessive grouping or sharing of privacy budgets makes the results inaccurate.To address the above-mentioned problems,this study proposes independent channel(IC)and mixed independent channel(MIC),which are efficient LDP protocols for FO with a large domains.We design a flexible method for splitting a large domain to reduce the number of sub-domains.Further,we employ the false positive rate with interaction to obtain an accurate estimation.Numerical 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.

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

Key Laboratory of Data Engineering and Knowledge Engineering of Ministry of Education,Renmin University of China,Beijing 100872,China;School of Information,Renmin University of China,Beijing 100872,China

计算机科学前沿

[1]Dan ZHAO;Suyun ZHAO;Hong CHEN;Ruixuan LIU;Cuiping LI;Wenjuan LIANG-.Efficient protocols for heavy hitter identification with local differential privacy)[J].计算机科学前沿,2022(05):183-193

hitter,effici

Efficient,protocols,heavy,identification,local,differential,privacy,Local,LDP,which,technique,that,employs,unbiased,statistical,estimations,instead,real,data,usually,adopted,collection,can,protect,every,user,prevent,leakage,sensitive,information,segment,pairs,method,SPM,multiple,channel,MCM,prefix,extending,PEM,are,three,known,well,frequency,oracle,FO,large,domains,However,scalability,these,algorithms,often,limits,their,application,Specifically,communication,computation,strongly,affect,Moreover,excessive,grouping,sharing,budgets,makes,results,inaccurate,To,address,above,mentioned,problems,this,study,proposes,independent,mixed,MIC,efficient,We,design,flexible,splitting,reduce,number,sub,Further,false,positive,interaction,obtain,Numerical,experiments,demonstrate,outperforms,existing,solutions,under,same,guarantee,while,small,lowest,cost

0.587719