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

arXiv: https://arxiv.org/abs/2405.04344 · HTML: https://mlsanity.com/paper/2405.04344/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 39 references that are in the map.
- First posted on arXiv 7 May 2024.

## Builds on (most cited first, 6 of 6)

- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [Generalised Differential Privacy for Text Document Processing](https://mlsanity.com/paper/1811.10256/) (2018)
- [Leveraging Hierarchical Representations for Preserving Privacy and Utility in Text](https://mlsanity.com/paper/1910.08917/) (2019)
- [Optimal Geo-Indistinguishable Mechanisms for Location Privacy](https://mlsanity.com/paper/1402.5029/) (2014)
- [Constructing elastic distinguishability metrics for location privacy](https://mlsanity.com/paper/1503.00756/) (2015)
- [User Customizable and Robust Geo-Indistinguishability for Location Privacy](https://mlsanity.com/paper/2206.08396/) (2022)

## Built on by (most cited first, 1 of 1)

- [Interpolation-Based Optimization for Enforcing lp-Norm Metric Differential Privacy in Continuous and Fine-Grained Domains](https://mlsanity.com/paper/2601.09946/) (2026)

## Abstract (arXiv)

Metric Differential Privacy (mDP) extends the concept of Differential Privacy (DP) to serve as a new paradigm of data perturbation. It is designed to protect secret data represented in general metric space, such as text data encoded as word embeddings or geo-location data on the road network or grid maps. To derive an optimal data perturbation mechanism under mDP, a widely used method is linear programming (LP), which, however, might suffer from a polynomial explosion of decision variables, rendering it impractical in large-scale mDP. In this paper, our objective is to develop a new computation framework to enhance the scalability of the LP-based mDP. Considering the connections established by the mDP constraints among the secret records, we partition the original secret dataset into various subsets. Building upon the partition, we reformulate the LP problem for mDP and solve it via Benders Decomposition, which is composed of two stages: (1) a master program to manage the perturbation calculation across subsets and (2) a set of subproblems, each managing the perturbation derivation within a subset. Our experimental results on multiple datasets, including geo-location data in the road network/grid maps, text data, and synthetic data, underscore our proposed mechanism's superior scalability and efficiency.