Frequency Estimation Mechanisms Under ϵδ-Utility-Optimized Local Differential Privacy

Frequency estimation mechanisms are widely applied in domains such as machine learning and cloud computing, where it is desirable to provide statistical information. As a fundamental operation in these domains, frequency estimation utilizes personal data which contains sensitive information while it is necessary to protect sensitive information from others. Motivated by this, we preserve user's privacy with local differential privacy by obfuscating personal data on the user side. In this paper, we propose frequency estimation mechanisms under utility-optimized local differential privacy (ULDP), which allow the data collector to obtain some non-sensitive values to improve data utility while protecting sensitive values from leaking sensitive information. We propose three frequency estimation mechanisms under $(\epsilon,\delta)$ -ULDP (uRFM-GRR, uRFM-RAPPOR, uRFM-OLH) to preserve user's sensitive information. Our proposed mechanisms protect sensitive data with the same privacy guarantee and they are suitable for different scenarios. Besides, in theory, we compare the estimation errors of our proposed mechanisms with existing LDP based mechanisms and show that ours are lower than theirs. Finally, we conduct experiments on synthetic and real-world datasets to evaluate the performance of the three mechanisms. The experimental results demonstrate that our proposed mechanisms are better than the existing LDP based solutions over the same privacy level, while uRFM-OLH frequently performs the best.