Article

Smaller coresets for k-median and k-means clustering

Authors:

Sariel Har-Peled,

Akash KushalAuthors Info & Claims

SCG '05: Proceedings of the twenty-first annual symposium on Computational geometry

Pages 126 - 134

https://doi.org/10.1145/1064092.1064114

Published: 06 June 2005 Publication History

Abstract

In this paper, we show that there exists a (k, ε)-coreset for k-median and k-means clustering of n points in R^d, which is of size independent of n. In particular, we construct a (k, ε)-coreset of size O(k²/ε^d) for k-median clustering, and of size O(k³/ε^d+1) for k-means clustering.

References

[1]

S. Arora. Polynomial time approximation schemes for euclidean tsp and ther geometric problems. J. Assoc. Comput. Mach.,45(5):753--782,Sep 1998.

Digital Library

[2]

S. Arora, P. Raghavan,and S. Rao. Approximation schemes for Euclidean k -median and related problems. In Proc. 30th Annu. ACM Sympos. Theory Comput., pages 106--113,1998.

Digital Library

[3]

M. Bǎdiu, S. Har-Peled,and P.Indyk. Approximate clustering via coresets. In Proc. 34th Annu. ACM Sympos. Theory Comput., pages 250--257, 2002.

Digital Library

[4]

M. Charikar, S. Guha, E. Tardos,and D. B. Shmoys. A constant-factor approximation algorithm for the k -median problem. In Proc. 31st Annu. ACM Sympos. Theory Comput., pages 1--10, 1999.

Digital Library

[5]

W.F.de la Vega,M. Karpinski,C. Kenyon, and Y. Rabani. Approximation schemes for clustering problems. In Proc. 35th Annu. ACM Sympos. Theory Comput., pages 50--58,2003.

Digital Library

[6]

R. G. D wney and M. R. Fellows. Fixed-parameter tractability and completeness i: Basic results. SIAM J. Comput.,24(4): 873--921,1995.

Digital Library

[7]

M. Effros and L. J. Schulman. Deterministic clustering with data nets.Technical Report TR04-085, Elec. Colloq.Comp.Complexity,2003. http://www.eccc.uni-trier.de/eccc-reports/2004/TR04-085/.

[8]

S. Guha,R. M. N. Mishra, and L. O'Callaghan. Clustering data streams.In Proc. 41th Annu. IEEE Sympos. Found. Comput. Sci., pages 359--366,2000.

Digital Library

[9]

S. Har-Peled and S. Mazumdar. Coresets for k -means and k -median clustering and their applications. In Proc. 36th Annu. ACM Sympos. Theory Comput., pages 291--300,2004.

Digital Library

[10]

M. Inaba,N. Katoh,and H.Imai. Applications of weighted voronoi diagrams and randomization to variance-based k -clustering. In Proc. 10th Annu. ACM Sympos. Comput. Geom.,pages 332--339, 1994.

Digital Library

[11]

T. Kanungo, D. M. Mount, N. S. Netanyahu, C. D. Piatk,R. Silverman,and A. Y.Wu. A local search approximation algorithm for k -means clustering. In Proc. 18th Annu. ACM Sympos. Comput. Geom., pages 10--18,2002.

Digital Library

[12]

S. G. Kolliop ulos and S. Rao. A nearly linear-time approximation scheme for the euclidean ? -median problem. In Proc. 7thAnnu. European Sympos. Algorithms pages 378--389,1999.

Digital Library

[13]

A. Kumar,Y. Sabharwal, and S. Sen. Linear time algorithms for clustering problems in any dimension. manuscript,2004.

[14]

J. Matoušek. On approximate geometric k -clustering. Discrete Comput. Geom., 24: 61--84,2000.

[15]

J. Matoušsek.Lectures on Discrete Geometry Springer, 2002.

Digital Library

[16]

R. Mettu and C. G. Plaxton. Optimal time bounds for approximate clustering.In In Proceedings of the 18th Conference on Uncertainty in Artifical Intelligence pages 344--351,2002.

Digital Library

Cited By

Esmailpour ASintos S(2024)Improved Approximation Algorithms for Relational ClusteringProceedings of the ACM on Management of Data10.1145/36958312:5(1-27)Online publication date: 7-Nov-2024
https://dl.acm.org/doi/10.1145/3695831
Khandel PYates AVarbanescu Ade Rijke MPimentel AOosterhuis HBast HXiong C(2024)Distillation vs. Sampling for Efficient Training of Learning to Rank ModelsProceedings of the 2024 ACM SIGIR International Conference on Theory of Information Retrieval10.1145/3664190.3672527(51-60)Online publication date: 2-Aug-2024
https://dl.acm.org/doi/10.1145/3664190.3672527
Chen JChen TXu XZhang JYang YShen H(2024)Coreset Learning-Based Sparse Black-Box Adversarial Attack for Video RecognitionIEEE Transactions on Information Forensics and Security10.1109/TIFS.2023.333355619(1547-1560)Online publication date: 2024
https://doi.org/10.1109/TIFS.2023.3333556
Show More Cited By

Index Terms

Smaller coresets for k-median and k-means clustering
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

On coresets for k-means and k-median clustering
STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing

In this paper, we show the existence of small coresets for the problems of computing k-median and k-means clustering for points in low dimension. In other words, we show that given a point set P in R^d, one can compute a weighted set S ⊆ P, of size O(k ε^-...
A PTAS for k-means clustering based on weak coresets
SCG '07: Proceedings of the twenty-third annual symposium on Computational geometry

Given a point set P ⊆ R^d the k-means clustering problem is to find a set C=(c₁,...,c_k) of k points and a partition of P into k clusters C₁,...,C_k such that the sum of squared errors ∑_i=1^k ∑_{p ∈ C_i} |p -c_i |₂² is minimized. For given centers this cost ...
Smaller Coresets for k-Median and k-Means Clustering

In this paper we show that there exists a $(k,\varepsilon)$-coreset for k-median and k-means clustering of n points in ${\cal R}^d,$ which is of size independent of n. In particular, we construct a $(k,\varepsilon)$-coreset of size $O(k^2/\varepsilon^d)$...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SCG '05: Proceedings of the twenty-first annual symposium on Computational geometry

June 2005

398 pages

ISBN:1581139918

DOI:10.1145/1064092

Program Chairs:
Joe Mitchell
SUNY Stony Brook
,
Günter Rote
Freie Universität Berlin

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SoCG05

Sponsor:

SoCG05: The 21st Annual ACM Symposium on Computational Geometry 2005

June 6 - 8, 2005

Pisa, Italy

Acceptance Rates

SCG '05 Paper Acceptance Rate 41 of 141 submissions, 29%;

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

62
Total Citations
View Citations
643
Total Downloads

Downloads (Last 12 months)38
Downloads (Last 6 weeks)6

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Esmailpour ASintos S(2024)Improved Approximation Algorithms for Relational ClusteringProceedings of the ACM on Management of Data10.1145/36958312:5(1-27)Online publication date: 7-Nov-2024
https://dl.acm.org/doi/10.1145/3695831
Khandel PYates AVarbanescu Ade Rijke MPimentel AOosterhuis HBast HXiong C(2024)Distillation vs. Sampling for Efficient Training of Learning to Rank ModelsProceedings of the 2024 ACM SIGIR International Conference on Theory of Information Retrieval10.1145/3664190.3672527(51-60)Online publication date: 2-Aug-2024
https://dl.acm.org/doi/10.1145/3664190.3672527
Chen JChen TXu XZhang JYang YShen H(2024)Coreset Learning-Based Sparse Black-Box Adversarial Attack for Video RecognitionIEEE Transactions on Information Forensics and Security10.1109/TIFS.2023.333355619(1547-1560)Online publication date: 2024
https://doi.org/10.1109/TIFS.2023.3333556
Dandolo EMazzetto APietracaprina APucci G(2024)MapReduce Algorithms for Robust Center-Based Clustering in Doubling MetricsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2024.104966(104966)Online publication date: Aug-2024
https://doi.org/10.1016/j.jpdc.2024.104966
Du JShi QZhou JOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Sequential subset matching for dataset distillationProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3669072(67487-67504)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3669072
Ma ZGao DYang SWei XGong Y(2023)Dataset Condensation via Expert Subspace ProjectionSensors10.3390/s2319814823:19(8148)Online publication date: 28-Sep-2023
https://doi.org/10.3390/s23198148
Esfandiari HMirrokni VZhong PAgrawal KShun J(2023)Brief Announcement: Streaming Balanced ClusteringProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3558481.3591318(311-314)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3558481.3591318
Hoang NDang T(2023)Enhancing Big Data Conversion Validation with Alpha-Lightweight CoresetSN Computer Science10.1007/s42979-023-02206-04:6Online publication date: 14-Oct-2023
https://doi.org/10.1007/s42979-023-02206-0
Hoang NDang T(2022)Alpha Lightweight Coreset for k-Means Clustering2022 16th International Conference on Ubiquitous Information Management and Communication (IMCOM)10.1109/IMCOM53663.2022.9721770(1-8)Online publication date: 3-Jan-2022
https://doi.org/10.1109/IMCOM53663.2022.9721770
Bhattacharya AFreund YJaiswal R(2022)On the k-means/median cost functionInformation Processing Letters10.1016/j.ipl.2022.106252177(106252)Online publication date: Aug-2022
https://doi.org/10.1016/j.ipl.2022.106252
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents