Enhancing Scalability of Metric Differential Privacy via Secret Dataset Partitioning and Benders Decomposition

Metric Differential Privacy（mDP）将差分隐私（DP）的概念扩展到数据扰动的新范式。它旨在保护以一般度量空间表示的秘密数据，例如编码为单词嵌入的文本数据或道路网络或网格地图上的地理位置数据。为了在mDP下推导出最优数据扰动机制，一种广泛使用的方法是线性规划（LP），然而，它可能会遭受决策变量的多项式爆炸，使得它在大规模mDP中不实用。 本文的目标是开发一个新的计算框架，以增强基于LP的mDP的可扩展性。考虑到mDP约束在秘密记录之间建立的连接，我们将原始秘密数据集分成各种子集。基于这个分区，我们重新制定了mDP的LP问题，并通过Benders分解来解决它，它由两个阶段组成：（1）主程序来管理跨子集的扰动计算，（2）一组子问题，每个子问题管理子集内的扰动推导。我们在多个数据集上进行了实验，包括道路网络/网格地图中的地理位置数据、文本数据和合成数据，验证了我们提出的机制具有卓越的可扩展性和效率。

本论文旨在解决Metric Differential Privacy (mDP)在大规模数据集中使用线性规划（LP）时，由于决策变量的多项式爆炸而不实用的问题。

通过将原始数据集分成不同的子集，并构建主程序和子问题的Benders Decomposition，重新制定mDP的LP问题，从而提高LP-based mDP的可扩展性。

实验结果表明，该机制具有卓越的可扩展性和效率，适用于多个数据集，包括道路网络/网格地图中的地理位置数据，文本数据和合成数据。

在最近的研究中，其他与mDP相关的论文包括：《Differentially Private k-Means Clustering with Constant Cluster Size》和《The Sparse Vector Technique for Differential Privacy: Complexity and Applications》。