- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies private coreset construction for Euclidean clustering under concentrated geo-privacy (CGP). It develops algorithms for the minimum enclosing ball, k-center, and general (k,z)-clustering problems by incorporating noisy distance queries and private point releases into existing geometric coreset techniques. The paper provides privacy and approximation guarantees and evaluates the proposed methods on synthetic and real-world datasets.
Critical strengths
+. The paper addresses a meaningful problem. Constructing coresets under local privacy constraints is challenging because perturbations may disrupt the geometric structure required for clustering.
+. The framework covers several important clustering problems, including MEB, k-center, and general (k,z)-clustering. The combination of CGP mechanisms with geometric coreset constructions is reasonable, and the paper provides corresponding theoretical guarantees.
+. The experiments show consistent privacy–utility trends, and the supplementary material includes additional evaluations of coreset size and the number of clusters.
Critical weaknesses
-. In Algorithm 5 of the supplementary material, the correction weight assigned to a reference center is not guaranteed to be nonnegative. In particular, a sampled point with a small sampling probability may receive a sufficiently large importance weight to make the correction weight negative. This appears inconsistent with Definition 2.2, which requires nonnegative coreset weights, and may affect the validity of Theorem 4.3. The authors should clarify how this situation is prevented or handled.
-. The theoretical analysis of the general (k,z)-clustering construction needs further justification. In particular, the proof of Lemma 4.2 does not provide sufficient details on how the private residual estimates and assignments preserve the required sensitivity bound. Moreover, the k-center coreset size is stated as O(k/γ) in the introduction and Appendix B.2, but O(k/γ²) in Theorem 3.9. These issues should be clarified.
-. The practical significance of the theoretical guarantees is not sufficiently demonstrated. The privacy-induced additive errors may be substantial under certain parameter settings, but their impact is not systematically analyzed. The experiments also involve relatively small, low-dimensional datasets and do not directly evaluate the exhaustive k-center refinement or the k-median construction. Further evidence on scalability and computational costs would strengthen the results.
Questions for authors
Q1. How does Algorithm 5 ensure nonnegative coreset weights, and can the authors provide a more detailed justification of Lemma 4.2?
Q2. Which k-center coreset-size bound is intended, and how should the additive-error guarantees be interpreted relative to the standard coreset definitions?
Q3. How do the theoretical error bounds and computational costs behave under larger datasets and higher dimensions?