# Differential Privacy for Clustering Under Continual Observation

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 33 references that are in the map.
- First posted on arXiv 7 Jul 2023.

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

- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [Differentially Private Clustering: Tight Approximation Ratios](https://mlsanity.com/paper/2008.08007/) (2020)
- [The Price of Differential Privacy under Continual Observation](https://mlsanity.com/paper/2112.00828/) (2021)
- [Almost Tight Error Bounds on Differentially Private Continual Counting](https://mlsanity.com/paper/2211.05006/) (2022)
- [Differentially Private k-Means with Constant Multiplicative Error](https://mlsanity.com/paper/1804.08001/) (2018)
- [Locally Private k-Means in One Round](https://mlsanity.com/paper/2104.09734/) (2021)
- [Differentially Private Histograms under Continual Observation: Streaming Selection into the Unknown](https://mlsanity.com/paper/2103.16787/) (2021)
- [Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets](https://mlsanity.com/paper/2204.04828/) (2022)
- [Differentially Private Algorithms for Graphs Under Continual Observation](https://mlsanity.com/paper/2106.14756/) (2021)
- [Scalable Differentially Private Clustering via Hierarchically Separated Trees](https://mlsanity.com/paper/2206.08646/) (2022)
- [Differentially Private Continual Releases of Streaming Frequency Moment Estimations](https://mlsanity.com/paper/2301.05605/) (2023)
- [A note on differentially private clustering with large additive error](https://mlsanity.com/paper/2009.13317/) (2020)
- [Better Differentially Private Approximate Histograms and Heavy Hitters using the Misra-Gries Sketch](https://mlsanity.com/paper/2301.02457/) (2023)
- [Private Counting of Distinct and k-Occurring Items in Time Windows](https://mlsanity.com/paper/2211.11718/) (2022)
- [Differentially Private Continual Release of Histograms and Related Queries](https://mlsanity.com/paper/2302.11341/) (2023)

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

- [Differentially Private Clustering in Data Streams](https://mlsanity.com/paper/2307.07449/) (2023)
- [Machine Unlearning as Private Retroactive Algorithms](https://mlsanity.com/paper/2609.05329/) (2026)

## Abstract (arXiv)

We consider the problem of clustering privately a dataset in ℝd that undergoes both insertion and deletion of points. Specifically, we give an varepsilon-differentially private clustering mechanism for the k-means objective under continual observation. This is the first approximation algorithm for that problem with an additive error that depends only logarithmically in the number T of updates. The multiplicative error is almost the same as non privately. To do so we show how to perform dimension reduction under continual observation and combine it with a differentially private greedy approximation algorithm for k-means. We also partially extend our results to the k-median problem.