{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,21]],"date-time":"2026-07-21T09:58:55Z","timestamp":1784627935025,"version":"3.55.0"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2012,12,1]],"date-time":"2012-12-01T00:00:00Z","timestamp":1354320000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-11-1-0392"],"award-info":[{"award-number":["N00014-11-1-0392"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2008411"],"award-info":[{"award-number":["2008411"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["327620-09"],"award-info":[{"award-number":["327620-09"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"name":"BSF","award":["2002282"],"award-info":[{"award-number":["2002282"]}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["52\/03"],"award-info":[{"award-number":["52\/03"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["0830803, 09165174, 1065276, 1118126, and 1136174"],"award-info":[{"award-number":["0830803, 09165174, 1065276, 1118126, and 1136174"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2012,12]]},"abstract":"<jats:p>We investigate variants of Lloyd's heuristic for clustering high-dimensional data in an attempt to explain its popularity (a half century after its introduction) among practitioners, and in order to suggest improvements in its application. We propose and justify a<jats:italic>clusterability<\/jats:italic>criterion for data sets. We present variants of Lloyd's heuristic that quickly lead to provably near-optimal clustering solutions when applied to well-clusterable instances. This is the first performance guarantee for a variant of Lloyd's heuristic. The provision of a guarantee on output quality does not come at the expense of speed: some of our algorithms are candidates for being<jats:italic>faster in practice<\/jats:italic>than currently used variants of Lloyd's method. In addition, our other algorithms are faster on well-clusterable instances than recently proposed approximation algorithms, while maintaining similar guarantees on clustering quality. Our main algorithmic contribution is a novel probabilistic seeding process for the starting configuration of a Lloyd-type iteration.<\/jats:p>","DOI":"10.1145\/2395116.2395117","type":"journal-article","created":{"date-parts":[[2013,1,8]],"date-time":"2013-01-08T15:34:16Z","timestamp":1357659256000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":102,"title":["The effectiveness of lloyd-type methods for the k-means problem"],"prefix":"10.1145","volume":"59","author":[{"given":"Rafail","family":"Ostrovsky","sequence":"first","affiliation":[{"name":"University of California, Los Angeles, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuval","family":"Rabani","sequence":"additional","affiliation":[{"name":"The Hebrew University of Jerusalem, Jerusalem, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leonard J.","family":"Schulman","sequence":"additional","affiliation":[{"name":"California Institute of Technology, Pasadena, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chaitanya","family":"Swamy","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,1,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_2"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 23rd Annual Conference on Neural Information Processing System (NIPS). 10--18","author":"Ailon N.","unstructured":"Ailon , N. , Jaiswal , R. , and Monteleoni , C . 2009. Streaming k-means approximation . In Proceedings of the 23rd Annual Conference on Neural Information Processing System (NIPS). 10--18 . Ailon, N., Jaiswal, R., and Monteleoni, C. 2009. Streaming k-means approximation. In Proceedings of the 23rd Annual Conference on Neural Information Processing System (NIPS). 10--18."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 1st Workshop on High Performance Data Mining.","author":"Alsabti K.","unstructured":"Alsabti , K. , Ranka , S. , and Singh , V . 1998. An efficient k-means clustering algorithm . In Proceedings of the 1st Workshop on High Performance Data Mining. Alsabti, K., Ranka, S., and Singh, V. 1998. An efficient k-means clustering algorithm. In Proceedings of the 1st Workshop on High Performance Data Mining."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2027216.2027217"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1137856.1137880"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1027--1035","author":"Arthur D.","unstructured":"Arthur , D. and Vassilvitskii , S . 2007. k-means&plus;&plus;: the advantages of careful seeding . In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1027--1035 . Arthur, D. and Vassilvitskii, S. 2007. k-means&plus;&plus;: the advantages of careful seeding. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1027--1035."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702416402"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.36"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509947"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1068--1077","author":"Balcan M.","unstructured":"Balcan , M. , Blum , A. , and Gupta , A . 2009. Approximate clustering without the approximation . In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1068--1077 . Balcan, M., Blum, A., and Gupta, A. 2009. Approximate clustering without the approximation. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1068--1077."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 15th International Conference on Machine Learning (ICML). 91--99","author":"Bradley P. S.","unstructured":"Bradley , P. S. and Fayyad , U . 1998. Refining initial points for K-means clustering . In Proceedings of the 15th International Conference on Machine Learning (ICML). 91--99 . Bradley, P. S. and Fayyad, U. 1998. Refining initial points for K-means clustering. In Proceedings of the 15th International Conference on Machine Learning (ICML). 91--99."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1315245.1315306"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS). 378--388","author":"Charikar M.","unstructured":"Charikar , M. and Guha , S . 1999. Improved combinatorial algorithms for the facility location and k-median problems . In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS). 378--388 . Charikar, M. and Guha, S. 1999. Improved combinatorial algorithms for the facility location and k-median problems. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS). 378--388."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1882"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.09.009"},{"key":"e_1_2_1_16_1","first-page":"543","article-title":"Note on grouping","volume":"52","author":"Cox D. R.","year":"1957","unstructured":"Cox , D. R. 1957 . Note on grouping . J. ASA 52 , 543 -- 547 . Cox, D. R. 1957. Note on grouping. J. ASA 52, 543--547.","journal-title":"J. ASA"},{"key":"e_1_2_1_17_1","volume-title":"How fast is k-means&quest","author":"Dasgupta S.","unstructured":"Dasgupta , S. 2003. How fast is k-means&quest ; In Proceedings of the 16th Annual Conference on Computational Learning Theory (COLT) . 735. Dasgupta, S. 2003. How fast is k-means&quest; In Proceedings of the 16th Annual Conference on Computational Learning Theory (COLT). 735."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780550"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1111\/j.2517-6161.1977.tb01600.x","article-title":"Maximum likelihood from incomplete data via the EM algorithm (with discussion)","volume":"39","author":"Dempster A. P.","year":"1977","unstructured":"Dempster , A. P. , Laird , N. M. , and Rubin , D. B. 1977 . Maximum likelihood from incomplete data via the EM algorithm (with discussion) . J. R. Y. Stat. Soc. B 39 , 1 -- 38 . Dempster, A. P., Laird, N. M., and Rubin, D. B. 1977. Maximum likelihood from incomplete data via the EM algorithm (with discussion). J. R. Y. Stat. Soc. B 39, 1--38.","journal-title":"J. R. Y. Stat. Soc. B"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:MACH.0000033113.59016.96"},{"key":"e_1_2_1_21_1","unstructured":"Duda R. O. Hart P. E. and Stork D. G. 2000. Pattern Classification. Wiley-Interscience. Duda R. O. Hart P. E. and Stork D. G. 2000. Pattern Classification. Wiley-Interscience."},{"key":"e_1_2_1_22_1","unstructured":"Effros M. and Schulman L. J. 2004a. Deterministic clustering with data nets. Electronic Tech rep. ECCC TR04-050. Effros M. and Schulman L. J. 2004a. Deterministic clustering with data nets. Electronic Tech rep. ECCC TR04-050."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the International Symposium on Information Theory (ISIT).","author":"Effros M.","unstructured":"Effros , M. and Schulman , L. J . 2004b. Deterministic clustering with data nets . In Proceedings of the International Symposium on Information Theory (ISIT). Effros, M. and Schulman, L. J. 2004b. Deterministic clustering with data nets. In Proceedings of the International Symposium on Information Theory (ISIT)."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622737.1622745"},{"key":"e_1_2_1_25_1","first-page":"768","article-title":"Cluster analysis of multivariate data: Efficiency vs. interpretability of classification","volume":"21","author":"Forgey E.","year":"1965","unstructured":"Forgey , E. 1965 . Cluster analysis of multivariate data: Efficiency vs. interpretability of classification . Biometrics 21 , 768 . Forgey, E. 1965. Cluster analysis of multivariate data: Efficiency vs. interpretability of classification. Biometrics 21, 768.","journal-title":"Biometrics"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Gersho A. and Gray R. M. 1992. Vector quantization and signal compression. Kluwer. Gersho A. and Gray R. M. 1992. Vector quantization and signal compression. Kluwer.","DOI":"10.1007\/978-1-4615-3626-0"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.720541"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007400"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1127-9"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1021\/ci9702858"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/331499.331504"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/950620.950621"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375845"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.03.003"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2002.1017616"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Kaufman L. and Rousseeuw P. J. 1990. Finding Groups in Data. An Introduction to Cluster Analysis. Wiley. Kaufman L. and Rousseeuw P. J. 1990. Finding Groups in Data. An Introduction to Cluster Analysis. Wiley.","DOI":"10.1002\/9780470316801"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.7"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1980.1094577"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. 281--297","author":"MacQueen J.","year":"1967","unstructured":"MacQueen , J. 1967 . Some methods for classification and analysis of multivariate observations . In Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. 281--297 . MacQueen, J. 1967. Some methods for classification and analysis of multivariate observations. In Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. 281--297."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004540010019"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1960.1057548"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the 14th Conference on Uncertainty in Arificial Intelligent (UAI). 386--395","author":"Meila M.","unstructured":"Meila , M. and Heckerman , D . 1998. An experimental comparison of several clustering and initialization methods . In Proceedings of the 14th Conference on Uncertainty in Arificial Intelligent (UAI). 386--395 . Meila, M. and Heckerman, D. 1998. An experimental comparison of several clustering and initialization methods. In Proceedings of the 14th Conference on Uncertainty in Arificial Intelligent (UAI). 386--395."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:MACH.0000033114.18632.e0"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02293907"},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","unstructured":"Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge Univ. Press. Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge Univ. Press.","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250803"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/506147.506149"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.75"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1711"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/312129.312248"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8655(99)00069-0"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.5555\/646680.702322"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335373"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1093-3263(98)00008-4"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380813"},{"key":"e_1_2_1_57_1","first-page":"801","article-title":"Sur la division des corp materiels en parties","author":"Steinhaus H.","year":"1956","unstructured":"Steinhaus , H. 1956 . Sur la division des corp materiels en parties . Bull. Acad. Polon. Sci. C1. III vol IV , 801 -- 804 . Steinhaus, H. 1956. Sur la division des corp materiels en parties. Bull. Acad. Polon. Sci. C1. III vol IV, 801--804.","journal-title":"Bull. Acad. Polon. Sci. C1. III"},{"key":"e_1_2_1_58_1","unstructured":"Tryon R. C. and Bailey D. E. 1970. Cluster Analysis. McGraw-Hill. 147--150. Tryon R. C. and Bailey D. E. 1970. Cluster Analysis. McGraw-Hill. 147--150."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-011-9340-1"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2395116.2395117","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2395116.2395117","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:34:56Z","timestamp":1750239296000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2395116.2395117"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12]]},"references-count":59,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["10.1145\/2395116.2395117"],"URL":"https:\/\/doi.org\/10.1145\/2395116.2395117","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,12]]},"assertion":[{"value":"2010-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-01-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}