Approximate clustering via core-sets

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximate clustering via core-sets

Full text

Pdf (184 KB)

Source

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

Montreal, Quebec, Canada

SESSION: Session 5A table of contents

Pages: 250 - 257

Year of Publication: 2002

ISBN:1-58113-495-9

Authors

Mihai Bādoiu	MIT Laboratory for Comp. Sci., Cambridge, MA
Sariel Har-Peled	University of Illinois, Urbana, IL
Piotr Indyk	MIT Laboratory for Comp. Sci., Cambridge, MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 77, Citation Count: 39

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/509907.509947 What is a DOI?

ABSTRACT

In this paper, we show that for several clustering problems one can extract a small set of points, so that using those core-sets enable us to perform approximate clustering efficiently. The surprising property of those core-sets is that their size is independent of the dimension.Using those, we present a (1+ &egr;)-approximation algorithms for the k-center clustering and k-median clustering problems in Euclidean space. The running time of the new algorithms has linear or near linear dependency on the number of points and the dimension, and exponential dependency on 1/&egr; and k. As such, our results are a substantial improvement over what was previously known.We also present some other clustering results including (1+ &egr;)-approximate 1-cylinder clustering, and k-center clustering with outliers.

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 , Cecilia M. Procopiuc, Exact and approximation algorithms for clustering, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.658-667, January 25-27, 1998, San Francisco, California, United States
	2	N. Alon , S. Dar , M. Parnas , D. Ron, Testing of clustering, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.240, November 12-14, 2000
	3	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]
	4	Marshall Bern , David Eppstein, Approximation algorithms for geometric problems, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
	5	Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
	6	Lars Engebretsen , Piotr Indyk , Ryan O'Donnell, Derandomized dimensionality reduction with applications, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.705-712, January 06-08, 2002, San Francisco, California
	7	Ashish Goel , Piotr Indyk , Kasturi Varadarajan, Reductions among high dimensional proximity problems, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.769-778, January 07-09, 2001, Washington, D.C., United States
	8	T. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoret. Comput. Sci., 38:293--306, 1985.
	9	M. Grötschel, L. Lovász, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization, volume 2 of Algorithms and Combinatorics. Springer-Verlag, Berlin Heidelberg, 2nd edition, 1988. 2nd edition 1994.
	10	S. Har-Peled, Clustering Motion, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.84, October 14-17, 2001
	11	S. Har-Peled, Approximate Shape Fitting via Linearization, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.66, October 14-17, 2001
	12	P. Indyk, Algorithmic Applications of Low-Distortion Geometric Embeddings, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.10, October 14-17, 2001
	13	P. Indyk and M. Thorup. Approximate 1-median. manuscript, 2000.
	14	Nina Mishra , Dan Oblinger , Leonard Pitt, Sublinear time approximate clustering, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.439-447, January 07-09, 2001, Washington, D.C., United States
	15	R. Ostrovsky , Y. Rabani, Polynomial time approximation schemes for geometric k-clustering, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.349, November 12-14, 2000

CITED BY 41

	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
	Christoph H. Lampert, Kernel Methods in Computer Vision, Foundations and Trends® in Computer Graphics and Vision, v.4 n.3, p.193-285, March 2009
	Petros Drineas , Ravi Kannan, Pass efficient algorithms for approximating large matrices, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	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
	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
	Sariel Har-Peled , Kasturi Varadarajan, High-dimensional shape fitting in linear time, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	Ivor W. Tsang , James T. Kwok , Kimo T. Lai, Core Vector Regression for very large regression problems, Proceedings of the 22nd international conference on Machine learning, p.912-919, August 07-11, 2005, Bonn, Germany
	Timothy M. Chan, Faster core-set constructions and data stream algorithms in fixed dimensions, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	Piyush Kumar , Joseph S. B. Mitchell , E. Alper Yildirim, Approximate minimum enclosing balls in high dimensions using core-sets, Journal of Experimental Algorithmics (JEA), 8, 2003
	Sariel Har-Peled , Soham Mazumdar, On coresets for k-means and k-median clustering, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Hai Yu , Pankaj K. Agarwal , Raghunath Poreddy , Kasturi R. Varadarajan, Practical methods for shape fitting and kinetic data structures using core sets, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	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
	Mihai Bâdoiu , Kenneth L. Clarkson, Smaller core-sets for balls, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Kenneth L. Clarkson, Subgradient and sampling algorithms for l1 regression, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	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
	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
	Yulai Xie , Jack Snoeyink , Jinhui Xu, Efficient algorithm for approximating maximum inscribed sphere in high dimensional polytope, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Esther M. Arkin , Gill Barequet , Joseph S. B. Mitchell, Algorithms for two-box covering, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Taneli Mielikäinen, Frequency-based views to pattern collections, Discrete Applied Mathematics, v.154 n.7, p.1113-1139, 1 May 2006
	Timothy M. Chan, Faster core-set constructions and data-stream algorithms in fixed dimensions, Computational Geometry: Theory and Applications, v.35 n.1, p.20-35, August 2006
	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
	Mihai Bădoiu , Kenneth L. Clarkson, Optimal core-sets for balls, Computational Geometry: Theory and Applications, v.40 n.1, p.14-22, May, 2008
	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
	Bernd Gärtner , Martin Jaggi, Coresets for polytope distance, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark
	Zhaohong Deng , Fu-Lai Chung , Shitong Wang, FRSDE: Fast reduced set density estimator using minimal enclosing ball approximation, Pattern Recognition, v.41 n.4, p.1363-1372, April, 2008
	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
	Aris Anagnostopoulos , Anirban Dasgupta , Ravi Kumar, Approximation algorithms for co-clustering, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada
	Kenneth L. Clarkson, Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.922-931, January 20-22, 2008, San Francisco, California
	Michael J. Todd , E. Alper Yıldırım, On Khachiyan's algorithm for the computation of minimum-volume enclosing ellipsoids, Discrete Applied Mathematics, v.155 n.13, p.1731-1744, August, 2007
	Jair Cervantes , Xiaoou Li , Wen Yu , Kang Li, Support vector machine classification for large data sets via minimum enclosing ball clustering, Neurocomputing, v.71 n.4-6, p.611-619, January, 2008
	Nariankadu D. Shyamalkumar , Kasturi Varadarajan, Efficient subspace approximation algorithms, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.532-540, January 07-09, 2007, New Orleans, Louisiana
	Ilya Mironov , Moni Naor , Gil Segev, Sketching in adversarial environments, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	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
	Bodo Manthey , Heiko Röglin, Improved smoothed analysis of the k-means method, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.461-470, 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
	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
	Fu-Lai Chung , Zhaohong Deng , Shitong Wang, From minimum enclosing ball to fast fuzzy inference system training on large datasets, IEEE Transactions on Fuzzy Systems, v.17 n.1, p.173-184, February 2009
	Donghui Yan , Ling Huang , Michael I. Jordan, Fast approximate spectral clustering, Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, June 28-July 01, 2009, Paris, France