Locally differentially private frequency distribution estimation with relative error optimization  

作　　者：Ning WANGI Yifei LIU Zhigang WANG Zhiqiang WEI Ruichun TANG Peng TANG Ge YU 

机构地区：[1]Cyberspace Institute of Advanced Technology,Guangzhou University,Guangzhou 510006,China [2]School of Computer Science and Technology,Ocean University of China,Qingdao 266100,China [3]Key Laboratory of Cryptologic Technology and Information Security(Ministry of Education),Shandong University,Qingdao 266071,China [4]School of Computer Science and Technology,Northeastern University,Shenyang 110819,China

出　　处：《Frontiers of Computer Science》2024年第5期227-229,共3页计算机科学前沿（英文版）

基　　金：This work was supported by the National Natural Science Foundation of China(Grant Nos.61902365,61902366 and 62002203);the Shandong Provincial Natural Science Foundation(No.ZR2020QF045);the Open Project Program from Key Lab of Cryptologic Technology and Information Security(Ministry of Education);Shandong University,and the Young Scholars Program of Shandong University.

摘　　要：This paper tackles the problem of estimating the frequency distribution on the crowdsourced multidimensional categorical data under local differential privacy(LDP).Although the frequency estimation problem under LDP[1]has attracted a lot of attention in recent years,currently,to our knowledge,the existing works are all devoted to optimizing the absolute error,rather than relative error.Unlike the work for the former,the one targeting at the latter should take the true frequency distribution into consider and design true frequency distribution-sensitive data collection protocol so that the skewed distribution,which involves smaller frequency in high probability,is with less noise.However,it is challenging to fulfill such a requirement,since the true frequency distribution is private information and not available.

关 键 词：DISTRIBUTION ESTIMATION ERROR 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]