PCKV: Locally Differentially Private Correlated Key-Value Data Collection with Optimized Utility

Data collection under local differential privacy (LDP) has been mostly\nstudied for homogeneous data. Real-world applications often involve a mixture\nof different data types such as key-value pairs, where the frequency of keys\nand mean of values under each key must be estimated simultaneously. For\nkey-value data collection with LDP, it is challenging to achieve a good\nutility-privacy tradeoff since the data contains two dimensions and a user may\npossess multiple key-value pairs. There is also an inherent correlation between\nkey and values which if not harnessed, will lead to poor utility. In this\npaper, we propose a locally differentially private key-value data collection\nframework that utilizes correlated perturbations to enhance utility. We\ninstantiate our framework by two protocols PCKV-UE (based on Unary Encoding)\nand PCKV-GRR (based on Generalized Randomized Response), where we design an\nadvanced Padding-and-Sampling mechanism and an improved mean estimator which is\nnon-interactive. Due to our correlated key and value perturbation mechanisms,\nthe composed privacy budget is shown to be less than that of independent\nperturbation of key and value, which enables us to further optimize the\nperturbation parameters via budget allocation. Experimental results on both\nsynthetic and real-world datasets show that our proposed protocols achieve\nbetter utility for both frequency and mean estimations under the same LDP\nguarantees than state-of-the-art mechanisms.\n