{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T12:04:19Z","timestamp":1776773059897,"version":"3.51.2"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"7","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,3]]},"abstract":"<jats:p>\n            Over half a century old and showing no signs of aging,\n            <jats:italic>k<\/jats:italic>\n            -means remains one of the most popular data processing algorithms. As is well-known, a proper initialization of\n            <jats:italic>k<\/jats:italic>\n            -means is crucial for obtaining a good final solution. The recently proposed\n            <jats:italic>k<\/jats:italic>\n            -means++ initialization algorithm achieves this, obtaining an initial set of centers that is provably close to the optimum solution. A major downside of the\n            <jats:italic>k<\/jats:italic>\n            -means++ is its inherent sequential nature, which limits its applicability to massive data: one must make\n            <jats:italic>k<\/jats:italic>\n            passes over the data to find a good initial set of centers. In this work we show how to drastically reduce the number of passes needed to obtain, in parallel, a good initialization. This is unlike prevailing efforts on parallelizing\n            <jats:italic>k<\/jats:italic>\n            -means that have mostly focused on the post-initialization phases of\n            <jats:italic>k<\/jats:italic>\n            -means. We prove that our proposed initialization algorithm\n            <jats:italic>k<\/jats:italic>\n            -means|| obtains a nearly optimal solution after a logarithmic number of passes, and then show that in practice a constant number of passes suffices. Experimental evaluation on real-world large-scale data demonstrates that\n            <jats:italic>k<\/jats:italic>\n            -means|| outperforms\n            <jats:italic>k<\/jats:italic>\n            -means++ in both sequential and parallel settings.\n          <\/jats:p>","DOI":"10.14778\/2180912.2180915","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"622-633","source":"Crossref","is-referenced-by-count":489,"title":["Scalable k-means++"],"prefix":"10.14778","volume":"5","author":[{"given":"Bahman","family":"Bahmani","sequence":"first","affiliation":[{"name":"Stanford University, Stanford, CA"}]},{"given":"Benjamin","family":"Moseley","sequence":"additional","affiliation":[{"name":"University of Illinois, Urbana, IL"}]},{"given":"Andrea","family":"Vattani","sequence":"additional","affiliation":[{"name":"University of California, San Diego, CA"}]},{"given":"Ravi","family":"Kumar","sequence":"additional","affiliation":[{"name":"Yahoo! Research, Sunnyvale, CA"}]},{"given":"Sergei","family":"Vassilvitskii","sequence":"additional","affiliation":[{"name":"Yahoo! Research, New York, NY"}]}],"member":"320","published-online":{"date-parts":[[2012,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972900.16"},{"key":"e_1_2_1_2_1","first-page":"10","volume-title":"NIPS","author":"Ailon N.","year":"2009","unstructured":"N. Ailon , R. Jaiswal , and C. Monteleoni . Streaming k-means approximation . In NIPS , pages 10 -- 18 , 2009 . N. Ailon, R. Jaiswal, and C. Monteleoni. Streaming k-means approximation. In NIPS, pages 10--18, 2009."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-009-5103-0"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1137856.1137880"},{"key":"e_1_2_1_5_1","first-page":"1027","volume-title":"SODA","author":"Arthur D.","year":"2007","unstructured":"D. Arthur and S. Vassilvitskii . k-means++: The advantages of careful seeding . In SODA , pages 1027 -- 1035 , 2007 . D. Arthur and S. Vassilvitskii. k-means++: The advantages of careful seeding. In SODA, pages 1027--1035, 2007."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989425"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140442"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-28349-8_2"},{"key":"e_1_2_1_9_1","first-page":"9","volume-title":"KDD","author":"Bradley P. S.","year":"1998","unstructured":"P. S. Bradley , U. M. Fayyad , and C. Reina . Scaling clustering algorithms to large databases . In KDD , pages 9 -- 15 , 1998 . P. S. Bradley, U. M. Fayyad, and C. Reina. Scaling clustering algorithms to large databases. In KDD, pages 9--15, 1998."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5120\/2969-3975"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772715"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242610"},{"key":"e_1_2_1_13_1","first-page":"137","volume-title":"OSDI","author":"Dean J.","year":"2004","unstructured":"J. Dean and S. Ghemawat . MapReduce: Simplified data processing on large clusters . In OSDI , pages 137 -- 150 , 2004 . J. Dean and S. Ghemawat. MapReduce: Simplified data processing on large clusters. In OSDI, pages 137--150, 2004."},{"key":"e_1_2_1_14_1","first-page":"245","volume-title":"Workshop on Large-Scale Parallel KDD Systems, SIGKDD","author":"Dhillon I. S.","year":"2000","unstructured":"I. S. Dhillon and D. S. Modha . A data-clustering algorithm on distributed memory multiprocessors . In Workshop on Large-Scale Parallel KDD Systems, SIGKDD , pages 245 -- 260 , 2000 . I. S. Dhillon and D. S. Modha. A data-clustering algorithm on distributed memory multiprocessors. In Workshop on Large-Scale Parallel KDD Systems, SIGKDD, pages 245--260, 2000."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020515"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/360402.360419"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2003.1198387"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276312"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1058150.1058157"},{"key":"e_1_2_1_20_1","volume-title":"Inequalities","author":"Hardy G. H.","year":"1988","unstructured":"G. H. Hardy , J. E. Littlewood , and G. Polya . Inequalities . Cambridge University Press , 1988 . G. H. Hardy, J. E. Littlewood, and G. Polya. Inequalities. Cambridge University Press, 1988."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/331499.331504"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8655(00)00131-8"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.03.003"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873677"},{"key":"e_1_2_1_25_1","volume-title":"Clustering algorithms for spatial databases: A survey","author":"Kolatch E.","year":"2000","unstructured":"E. Kolatch . Clustering algorithms for spatial databases: A survey , 2000 . Available at www.cs.umd.edu\/~kolatch\/papers\/SpatialClustering.pdf. E. Kolatch. Clustering algorithms for spatial databases: A survey, 2000. Available at www.cs.umd.edu\/~kolatch\/papers\/SpatialClustering.pdf."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.7"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989505"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2006.31"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2004.25"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.75"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772862"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-011-9340-1"},{"key":"e_1_2_1_33_1","volume-title":"Hadoop: The Definitive Guide","author":"White T.","year":"2009","unstructured":"T. White . Hadoop: The Definitive Guide . O'Reilly Media , 2009 . T. White. Hadoop: The Definitive Guide. O'Reilly Media, 2009."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-007-0114-2"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/235968.233324"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10665-1_71"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2180912.2180915","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:12:22Z","timestamp":1672222342000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2180912.2180915"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,3]]},"references-count":36,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2012,3]]}},"alternative-id":["10.14778\/2180912.2180915"],"URL":"https:\/\/doi.org\/10.14778\/2180912.2180915","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,3]]}}}