Expectation-Maximization Estimation for Key-Value Data Randomized with Local Differential Privacy

This paper studies the local differential privacy (LDP) algorithm for key-value data that are pervasive in big data analysis. One of the state-of-the-arts algorithms, PrivKV, randomizes key-value pairs with a sequence of LDP algorithms. However, most likelihood estimation fails to estimate the statistics accurately when the frequency of the data for particular rare keys is limited. To address the problem, we propose the expectation-maximization-based algorithm designed for PrivKV. Instead of estimating continuous values [ - 1, 1 ] in key-value pairs, we focus on estimating the intermediate variable that contains the encoded binary bit ∈ { 1, - 1 }. This makes the problem tractable to estimate because we have a small set of possible input values and a set of observed outputs. We conduct some experiments using some synthetic data with some known distributions, e.g., Gaussian and power-law and well-known open datasets, MoveLens and Clothing. Our experiment using synthetic data and open datasets shows the robustness of estimation with regards to the size of data and the privacy budgets. The improvement is significant and the MSE of the proposed algorithm is 602.83 × 10 ^{- 4} (41% of PrivKVM).