Lune

CCS2025Top-tier venue

PAnDA: Rethinking Metric Differential Privacy Optimization at Scale with Anchor-Based Approximation

Ruiyao Liu, Chenxi Qiu

Abstract

Metric Differential Privacy (mDP) extends the local differential privacy (LDP) framework to metric spaces, enabling more nuanced privacy protection for data such as geo-locations.However, existing mDP optimization methods, particularly those based on linear programming (LP), face scalability challenges due to the quadratic growth in decision variables.In this paper, we propose Perturbation via Anchor-based Distributed Approximation (PAnDA), a scalable two-phase framework for optimizing metric differential privacy (mDP).To reduce computational overhead, PAnDA allows each user to select a small set of anchor records, enabling the server to solve a compact linear program over a reduced domain.We introduce three anchor selection strategies, exponential decay (PAnDA-e), power-law decay (PAnDA-p), and logistic decay (PAnDA-l), and establish theoretical guarantees under a relaxed privacy notion called probabilistic mDP (PmDP).Experiments on real-world geo-location datasets demonstrate that PAnDA scales to secret domains with up to 5,000 records, two times larger than prior LP-based methods, while providing theoretical guarantees for both privacy and utility.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

1 top-tier paper has cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • A Graph-Based Framework for Extending Metric Differential Privacy Mechanisms cites Dynamic Differential Location Privacy with Personalized Error Bounds
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. A Graph-Based Framework for Extending Metric Differential Privacy MechanismsRuiyao Liu, Chenxi QiuCCS 2026

Builds on2

  1. Dynamic Differential Location Privacy with Personalized Error BoundsLei Yu, Ling Liu, Calton PuNDSS 2017 · 100 citations
  2. PAC Privacy: Automatic Privacy Measurement and Control of Data ProcessingHanshen Xiao, Srinivas DevadasCRYPTO 2023 · 7 citations

Related papers

  1. Interpolation-Based Optimization for Enforcing lp-Norm Metric Differential Privacy in Continuous and Fine-Grained DomainsChenxi QiuUSENIX Security 2026 · 3 citations
  2. Smooth Sensitivity for Geo-PrivacyYuting Liang, Ke YiCCS 2024 · 1 citation
  3. Muffliato: Peer-to-Peer Privacy Amplification for Decentralized Optimization and AveragingEdwige Cyffers, Mathieu Even, Aurélien Bellet, Laurent MassouliéNeurIPS 2022 · 39 citations
  4. AAA: an Adaptive Mechanism for Locally Differential Private Mean EstimationFei Wei, Ergute Bao, Xiaokui Xiao, Yin Yang et al.VLDB 2024 · 7 citations
  5. Metric Differential Privacy at the User-Level via the Earth-Mover's DistanceJacob Imola, Amrita Roy Chowdhury, Kamalika ChaudhuriCCS 2024
Dusk over the sea between two cliffs drawn in fine vertical lines