MGD: A Utility Metric for Private Data Publication
MGD: A Utility Metric for Private Data Publication
复制标题
DOI：
10.1145/3491371.3491385
复制
发表时间：
2021-12
期刊：
影响因子：
--
通讯作者：
Zitao Li;Trung Dang;Tianhao Wang;Ninghui Li
中科院分区：
文献类型：
--
作者：
Zitao Li;Trung Dang;Tianhao Wang;Ninghui Li
差分隐私已被公认为保护用户数据隐私的最流行的技术之一。在DP下利用私有数据的一种常见方式是获取输入数据集并合成一个新的数据集，该数据集在满足DP的同时保留了输入数据集的特征。在隐私保护的强度和最终输出的效用之间总是存在权衡：更强的隐私保护需要更大的随机性，因此输出通常具有更大的方差，并且可能远非最优。在本文中，我们总结了我们为NIST“A Better Meter Stick for Differential Privacy”竞赛[26]提出的度量标准，边际差异（MGD），用于测量合成数据集的效用。我们的指标基于推土机距离。我们在我们的度量中引入了新的功能，使其不受DP上下文中不可避免的一些小的随机噪声的影响，但更侧重于显着差异。我们表明，我们的度量可以更好地反映范围查询错误相比，其他现有的度量。为了解决推土机距离计算量大的问题，提出了一种基于最小费用流的高效计算方法。
Differential privacy has been accepted as one of the most popular techniques to protect user data privacy. A common way for utilizing private data under DP is to take an input dataset and synthesize a new dataset that preserves features of the input dataset while satisfying DP. A trade-off always exists between the strength of privacy protection and the utility of the final output: stronger privacy protection requires larger randomness, so the outputs usually have a larger variance and can be far from optimal. In this paper, we summarize our proposed metric for the NIST “A Better Meter Stick for Differential Privacy” competition [26], MarGinal Difference (MGD), for measuring the utility of a synthesized dataset. Our metric is based on earth mover distance. We introduce new features in our metric so that it is not affected by some small random noise that is unavoidable in the DP context but focuses more on the significant difference. We show that our metric can reflect the range query error better compared with other existing metrics. We introduce an efficient computation method based on the min-cost flow to alleviate the high computation cost of the earth mover’s distance.