EUVIMEDEUVIMED entdecken
Crossref

Differentially Private Universal Coresets for ( α , β ) -Fair k -Median and k -Means Clustering

Iftikhar Ahmad, Wang Zu

Bulletin of Computer and Data Sciences · 30.12.2025 · 6 (4) · 22-38

DOI: 10.71448/bcds2564-2 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Bulletin of Computer and Data Sciences, online erschienen am 30.12.2025. Verfasst von Iftikhar Ahmad und 1 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Fair clustering with ( α , β ) -proportionality constraints requires every cluster to satisfy lower and upper bounds on the representation of each sensitive group. Recent universal-coreset results enable scalable optimization by compressing the dataset into a small weighted subset that preserves constrained clustering costs simultaneously for all center sets and all feasible group-cardinality (coloring) constraints. In many applications, however, the sensitive attributes that motivate fairness constraints also require formal privacy protection, and releasing even a small coreset can leak membership and group information. We propose a modular framework for differentially private universal coresets for (α,β)-fair k-median and k-means in metric and Euclidean spaces. The framework consists of two stages: (i) construct a randomized η/2-universal coreset via random sampling and reweighting; (ii) release a privatized coreset by perturbing only the weight vector using the Gaussian mechanism, followed by post-processing (nonnegativity and mass renormalization). We prove that the released summary is (ε,δ)-differentially private and, with high probability, preserves constrained costs for all (C,M) up to a multiplicative (1±η) factor plus an additive privacy term that depends on the metric diameter bound, coreset size, and an ℓ2 weight-sensitivity parameter. We further extend the method to streaming via merge-and-reduce and analyze privacy under continual observation using advanced composition and amplification-by-subsampling. The resulting DP universal coresets allow multi-query fair clustering and interactive constraint tuning without repeated access to the raw sensitive dataset.

Zitieren

APA

Ahmad, I., & Zu, W. (2025). Differentially Private Universal Coresets for ( α , β ) -Fair k -Median and k -Means Clustering. Bulletin of Computer and Data Sciences, 6(4), 22-38. https://doi.org/10.71448/bcds2564-2

Vancouver

Ahmad I, Zu W. Differentially Private Universal Coresets for ( α , β ) -Fair k -Median and k -Means Clustering. Bulletin of Computer and Data Sciences. 2025;6(4):22-38. doi:10.71448/bcds2564-2

BibTeX
@article{Ahmad2025,
  author = {Ahmad, Iftikhar and Zu, Wang},
  title = {Differentially Private Universal Coresets for ( α , β ) -Fair k -Median and k -Means Clustering},
  journal = {Bulletin of Computer and Data Sciences},
  year = {2025},
  volume = {6},
  number = {4},
  pages = {22--38},
  doi = {10.71448/bcds2564-2}
}
Kostenlos starten →