On coresets for k-means and k-median clustering

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On coresets for k-means and k-median clustering

Full text

Pdf (223 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-sixth annual ACM symposium on Theory of computing table of contents

Chicago, IL, USA

SESSION: Session 7B table of contents

Pages: 291 - 300

Year of Publication: 2004

ISBN:1-58113-852-0

Authors

Sariel Har-Peled	University of Illinois, Urbana-Champaign, Urbana, IL
Soham Mazumdar	University of Illinois, Urbana-Champaign, Urbana, IL

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 27, Downloads (12 Months): 157, Citation Count: 30

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1007352.1007400 What is a DOI?

ABSTRACT

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 ε^-d log n), such that one can compute the k-median/means clustering on S instead of on P, and get an (1+ε)-approximation. As a result, we improve the fastest known algorithms for (1+ε)-approximate k-means and k-median. Our algorithms have linear running time for a fixed k and ε. In addition, we can maintain the (1+ε)-approximate k-median or k-means clustering of a stream when points are being only inserted, using polylogarithmic space and update time.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Pankaj K. Agarwal , Sariel Har-Peled , Kasturi R. Varadarajan, Approximating extent measures of points, Journal of the ACM (JACM), v.51 n.4, p.606-635, July 2004 [doi>10.1145/1008731.1008736]
	2	Pankaj K. Agarwal , Cecilia Magdalena Procopiuc , Kasturi R. Varadarajan, Approximation Algorithms for k-Line Center, Proceedings of the 10th Annual European Symposium on Algorithms, p.54-63, September 17-21, 2002
	3	Arnon Amir , Alon Efrat , Piotr Indyk , Hanan Samet, Efficient Regular Data Structures and Algorithms for Location and Proximity Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.160, October 17-18, 1999
	4	Sanjeev Arora, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, Journal of the ACM (JACM), v.45 n.5, p.753-782, Sept. 1998 [doi>10.1145/290179.290180]
	5	Sanjeev Arora , Prabhakar Raghavan , Satish Rao, Approximation schemes for Euclidean k-medians and related problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.106-113, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276718]
	6	Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Y. Wu, An optimal algorithm for approximate nearest neighbor searching fixed dimensions, Journal of the ACM (JACM), v.45 n.6, p.891-923, Nov. 1998 [doi>10.1145/293347.293348]
	7	Vijay Arya , Naveen Garg , Rohit Khandekar , Kamesh Munagala , Vinayaka Pandit, Local search heuristic for k-median and facility location problems, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.21-29, July 2001, Hersonissos, Greece [doi>10.1145/380752.380755]
	8	M. Badoiu and K. L. Clarkson. Optimal core-sets for balls. In Proc. 14th ACM-SIAM Sympos. Discrete Algorithms, pages 801--802, 2003.
	9	Mihai Bādoiu , Sariel Har-Peled , Piotr Indyk, Approximate clustering via core-sets, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509947]
	10	J. L. Bentley and J. B. Saxe. Decomposable searching problems i: Static-to-dynamic transformation. J. Algorithms, 1(4):301--358, 1980.
	11	Moses Charikar , Sudipto Guha, Improved Combinatorial Algorithms for the Facility Location and k-Median Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.378, October 17-18, 1999
	12	Moses Charikar , Sudipto Guha , Éva Tardos , David B. Shmoys, A constant-factor approximation algorithm for the k-median problem (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.1-10, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301257]
	13	W. Fernandez de la Vega , Marek Karpinski , Claire Kenyon , Yuval Rabani, Approximation schemes for clustering problems, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780550]
	14	Tomás Feder , Daniel Greene, Optimal algorithms for approximate clustering, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.434-444, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62255]
	15	Mordecai Golin , Rajeev Raman , Christian Schwarz , Michiel Smid, Simple randomized algorithms for closest pair problems, Nordic Journal of Computing, v.2 n.1, p.3-27, March 1995
	16	T. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoret. Comput. Sci., 38:293--306, 1985.
	17	S. Guha , N. Mishra , R. Motwani , L. O'Callaghan, Clustering data streams, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.359, November 12-14, 2000
	18	S. Har-Peled, Clustering Motion, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.84, October 14-17, 2001
	19	S. Har-Peled, A Replacement for Voronoi Diagrams of Near Linear Size, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.94, October 14-17, 2001
	20	Sariel Har-Peled , Kasturi Varadarajan, Projective clustering in high dimensions using core-sets, Proceedings of the eighteenth annual symposium on Computational geometry, p.312-318, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513440]
	21	Mary Inaba , Naoki Katoh , Hiroshi Imai, Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering: (extended abstract), Proceedings of the tenth annual symposium on Computational geometry, p.332-339, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.178042]
	22	Piotr Indyk, Sublinear time algorithms for metric space problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.428-434, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301366]
	23	P. Indyk. (1+ε)-approximate bi-criterion algorithm for k-median on a stream. In Proc. 36th Annu. ACM Sympos. Theory Comput., 2004.
	24	Kamal Jain , Vijay V. Vazirani, Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.2, October 17-18, 1999
	25	Tapas Kanungo , David M. Mount , Nathan S. Netanyahu , Christine D. Piatko , Ruth Silverman , Angela Y. Wu, A local search approximation algorithm for k-means clustering, Proceedings of the eighteenth annual symposium on Computational geometry, p.10-18, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513402]
	26	Stavros G. Kolliopoulos , Satish Rao, A Nearly Linear-Time Approximation Scheme for the Euclidean kappa-median Problem, Proceedings of the 7th Annual European Symposium on Algorithms, p.378-389, July 16-18, 1999
	27	Moses Charikar , Liadan O'Callaghan , Rina Panigrahy, Better streaming algorithms for clustering problems, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780548]
	28	J. Matousek. On approximate geometric k-clustering. Discrete Comput. Geom., 24:61--84, 2000.
	29	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.

CITED BY 31

	Yoonheui Kim , Victor Lesser , Deepak Ganesan , Ramesh Sitaraman, Cluster-Swap: A Distributed K-median Algorithm for Sensor Networks, Proceedings of the 2009 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology, p.363-370, September 15-18, 2009
	Jie Gao , Michael Langberg , Leonard J. Schulman, Analysis of incomplete data and an intrinsic-dimension Helly theorem, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.464-473, January 22-26, 2006, Miami, Florida
	Piotr Indyk, Algorithms for dynamic geometric problems over data streams, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Kunal Talwar, Bypassing the embedding: algorithms for low dimensional metrics, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Gereon Frahling , Piotr Indyk , Christian Sohler, Sampling in dynamic data streams and applications, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	Sariel Har-Peled , Akash Kushal, Smaller coresets for k-median and k-means clustering, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	Gereon Frahling , Christian Sohler, Coresets in dynamic geometric data streams, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Sariel Har-Peled , Bardia Sadri, How fast is the k-means method?, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Nir Ailon , Bernard Chazelle , Seshadhri Comandur , Ding Liu, Self-improving algorithms, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.261-270, January 22-26, 2006, Miami, Florida
	Amit Deshpande , Luis Rademacher , Santosh Vempala , Grant Wang, Matrix approximation and projective clustering via volume sampling, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1117-1126, January 22-26, 2006, Miami, Florida
	Ke Chen, On k-Median clustering in high dimensions, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1177-1185, January 22-26, 2006, Miami, Florida
	Sariel Har-Peled , Manor Mendel, Fast construction of nets in low dimensional metrics, and their applications, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	Fan Chung Graham, Preface: a brief overview of network algorithms, Journal of Computer and System Sciences, v.72 n.3, p.420-424, May 2006
	Yogish Sabharwal , Sandeep Sen, A linear time algorithm for approximate 2-means clustering, Computational Geometry: Theory and Applications, v.32 n.2, p.159-172, October 2005
	Graham Cormode , Andrew McGregor, Approximation algorithms for clustering uncertain data, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada
	Timothy M. Chan, Dynamic coresets, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA
	Gereon Frahling , Christian Sohler, A fast k-means implementation using coresets, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Pankaj K. Agarwal , Junyi Xie , Jun Yang , Hai Yu, Scalable continuous query processing by tracking hotspots, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	Sariel Har-Peled, How to get close to the median shape, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Sariel Har-Peled, How to get close to the median shape, Computational Geometry: Theory and Applications, v.36 n.1, p.39-51, January 2007
	Dan Feldman , Morteza Monemizadeh , Christian Sohler, A PTAS for k-means clustering based on weak coresets, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea
	Dan Feldman , Amos Fiat , Micha Sharir , Danny Segev, Bi-criteria linear-time approximations for generalized k-mean/median/center, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea
	Pankaj K. Agarwal , Hai Yu, A space-optimal data-stream algorithm for coresets in the plane, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea
	Marcel R. Ackermann , Johannes Blömer , Christian Sohler, Clustering for metric and non-metric distance measures, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.799-808, January 20-22, 2008, San Francisco, California
	David Arthur , Sergei Vassilvitskii, k-means++: the advantages of careful seeding, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1027-1035, January 07-09, 2007, New Orleans, Louisiana
	Anirban Dasgupta , Petros Drineas , Boulos Harb , Ravi Kumar , Michael W. Mahoney, Sampling algorithms and coresets for ℓ_p regression, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.932-941, January 20-22, 2008, San Francisco, California
	Ke Chen, A constant factor approximation algorithm for k-median clustering with outliers, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.826-835, January 20-22, 2008, San Francisco, California
	Marcel R. Ackermann , Johannes Blömer, Coresets and approximate clustering for Bregman divergences, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1088-1097, January 04-06, 2009, New York, New York
	Dan Feldman , Amos Fiat , Haim Kaplan , Kobbi Nissim, Private coresets, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	Robert Benkoczi , Binay K. Bhattacharya , Sandip Das , Jeff Sember, Single facility collection depots location problem in the plane, Computational Geometry: Theory and Applications, v.42 n.5, p.403-418, July, 2009
	Guang Xu , Jinhui Xu, Efficient approximation algorithms for clustering point-sets, Computational Geometry: Theory and Applications, v.43 n.1, p.59-66, January, 2010