Supporting Both Range Queries and Frequency Estimation with Local Differential Privacy
Supporting Both Range Queries and Frequency Estimation with Local Differential Privacy
复制标题
DOI：
10.1109/cns.2019.8802778
复制
发表时间：
2019-06
期刊：
影响因子：
--
通讯作者：
Xiaolan Gu;Ming Li;Yang Cao;Li Xiong
中科院分区：
文献类型：
--
作者：
Xiaolan Gu;Ming Li;Yang Cao;Li Xiong
局部差异隐私（LDP）提供了可证明的隐私保护数据收集没有可信的数据服务器的假设。满足LDP或其变体的现有机制或者仅考虑来自一组用户的聚集查询（例如，频率估计）或单个用户的单独查询（例如，范围查询）。然而，在复杂的现实分析应用中，希望同时支持这两种类型的查询。在本文中，我们解决的挑战，私人回答范围查询，并提供频率估计在同一时间具有高效用。我们开发了一种数据扰动机制，该机制被证明满足局部d-隐私（具有距离度量的LDP的广义版本），并且对于同位查询（特定类型的范围查询）具有最佳效用。然后，我们利用反演方法的频率估计使用的扰动数据。我们分析了该估计方法的理论均方误差（MSE），并展示了与LDP下另一种现有估计方法的关系。在合成和真实位置数据集上的实验结果验证了理论分析的正确性，并表明该机制在范围查询和频率估计方面都比现有机制具有更好的实用性。
Local Differential Privacy (LDP)provides provable privacy protection for data collection without the assumption of the trusted data server. Existing mechanisms that satisfy LDP or its variants either only consider aggregate queries from a group of users (e.g., frequency estimation)or individual queries for a single user (e.g., range queries). However, in complex real-world analytics applications, it is desirable to support both types of queries at the same time. In this paper, we tackle the challenge of privately answering range queries and providing frequency estimation at the same time with high utility. We develop a data perturbation mechanism, which is proved to satisfy local d-privacy (a generalized version of LDP with distance metric)and have optimal utility for the co-location query (a specific type of range query). Then, we utilize an inversion approach for frequency estimation using the perturbed data. We analyze the theoretical Mean Square Error (MSE)of this estimation method and show the relationship to another existing estimation method under LDP. The results on both synthetic and real-world location datasets validate the correctness of our theoretical analysis and show that the proposed mechanism has better utility for both range queries and frequency estimation than the state-of-the-art mechanisms.