Fetching the paper…
Reading the bibliography…
The $k$-means algorithm is one of the most widely used clustering heuristics.
Steinhaus, H.: Sur la division des corps matériels en parties. Bulletin de l’Académie Polonaise des Sciences IV(12), 801 – 804 (1956)
1956
Earlier work this paper cites.
Lloyd, S.P.: Least squares quantization in PCM. Bell Laboratories Technical Memorandum (1957), later published as [ 59 ]
1957
Earlier work this paper cites.
MacQueen, J.B.: Some methods for classification and analysis of multivariate observations. In: Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. vol. 1, pp. 281–297. University of California Press (1967)
1967
Earlier work this paper cites.
Hartigan, J.A.: Clustering Algorithms. Wiley (1975)
1975
Earlier work this paper cites.
Lloyd, S.P.: Least squares quantization in PCM. IEEE Transactions on Information Theory 28(2), 129 – 137 (1982)
1982
Earlier work this paper cites.
Selim, S.Z., Ismail, M.A.: k k -means-type algorithms: A generalized convergence theorem and characterization of local optimality. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI) 6(1), 81–87 (January 1984)
1984
Earlier work this paper cites.
Matula, D.W., Shahrokhi, F.: Sparsest cuts and bottlenecks in graphs. Discrete Applied Mathematics 27, 113 – 123 (1990)
1990
Earlier work this paper cites.
Inaba, M., Katoh, N., Imai, H.: Applications of weighted voronoi diagrams and randomization to variance-based k-clustering (extended abstract). In: Symposium on Computational Geometry (SoCG ’94). pp. 332–339 (1994)
1994
Earlier work this paper cites.
Gordon, A.: Null models in cluster validation. In: From data to knowledge : theoretical and practical aspects of classification, data analysis, and knowledge organization, pp. 32 – 44. Springer (1996)
1996
Earlier work this paper cites.
Zhang, T., Ramakrishnan, R., Livny, M.: BIRCH: A New Data Clustering Algorithm and Its Applications . Data Mining and Knowledge Discovery 1(2), 141 – 182 (1997)
1997
Earlier work this paper cites.
Alsabti, K., Ranka, S., Singh, V.: An efficient k k -means clustering algorithm. In: Proceeding of the First Workshop on High-Performance Data Mining (1998)
1998
Earlier work this paper cites.
Judd, D., McKinley, P.K., Jain, A.K.: Large-scale parallel data clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence 20(8), 871–876 (1998)
1998
Earlier work this paper cites.
Dasgupta, S.: Learning mixtures of gaussians. In: FOCS. pp. 634–644 (1999)
1999
Earlier work this paper cites.
Jain, A.K., Murty, M.N., Flynn, P.J.: Data clustering: A review. ACM Computing Surveys 31(3), 264 – 323 (1999)
1999
Earlier work this paper cites.
Pelleg, D., Moore, A.W.: Accelerating exact k -means algorithms with geometric reasoning. In: Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. pp. 277–281 (1999)
1999
Earlier work this paper cites.
Matoušek, J.: On approximate geometric k-clustering. Discrete & Computational Geometry 24(1), 61–84 (2000)
2000
Earlier work this paper cites.
Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and k
2001
Earlier work this paper cites.
Tibshirani, R., Walther, G., Hastie, T.: Estimating the number of clusters in a dataset via the gap statistic. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 63, 411 – 423 (2001)
2001
Earlier work this paper cites.
Kanungo, T., Mount, D.M., Netanyahu, N.S., Piatko, C.D., Silverman, R., Wu, A.Y.: An efficient k-means clustering algorithm: Analysis and implementation. IEEE Transactions on pattern analysis and machine intelligence 24(7), 881–892 (2002)
2002
Earlier work this paper cites.
Dasgupta, S.: How fast is k
2003
Earlier work this paper cites.
Guha, S., Meyerson, A., Mishra, N., Motwani, R., O’Callaghan, L.: Clustering data streams: Theory and practice. IEEE Transactions on Knowledge and Data Engineering 15(3), 515 – 528 (2003)
2003
Earlier work this paper cites.
de la Vega, W.F., Karpinski, M., Kenyon, C., Rabani, Y.: Approximation schemes for clustering problems. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC ’03). pp. 50–58 (2003)
2003
Earlier work this paper cites.
Har-Peled, S., Mazumdar, S.: On coresets for k-means and k-median clustering. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC ’04). pp. 291–300 (2004)
2004
Earlier work this paper cites.
Kanungo, T., Mount, D.M., Netanyahu, N.S., Piatko, C.D., Silverman, R., Wu, A.Y.: A local search approximation algorithm for k k -means clustering. Computational Geometry 28(2-3), 89–112 (June 2004)
2004
Earlier work this paper cites.
Vempala, S., Wang, G.: A spectral algorithm for learning mixture models. J. Comput. Syst. Sci. 68(4), 841–860 (2004)
2004
Earlier work this paper cites.
Achlioptas, D., McSherry, F.: On spectral learning of mixtures of distributions. In: COLT. pp. 458–469 (2005)
2005
Earlier work this paper cites.
Arora, S., Kannan, R.: Learning mixtures of separated nonspherical gaussians. Annals of Applied Probability 20(6) (2005)
2005
Cited alongside, same era.
Banerjee, A., Guo, X., Wang, H.: On the optimality of conditional expectation as a bregman predictor. Information Theory, IEEE Transactions on 51(7), 2664–2669 (2005)
2005
Cited alongside, same era.
Banerjee, A., Merugu, S., Dhillon, I.S., Ghosh, J.: Clustering with bregman divergences. The Journal of Machine Learning Research 6, 1705–1749 (2005)
2005
Cited alongside, same era.
Frahling, G., Sohler, C.: Coresets in dynamic geometric data streams. In: Proceedings of the 37th STOC. pp. 209–217 (2005)
2005
Cited alongside, same era.
Har-Peled, S., Sadri, B.: How fast is the k-means method? In: SODA. pp. 877–885 (2005)
2005
Cited alongside, same era.
2009
Later among the works it cites.
Chen, K.: On coresets for k-median and k-means clustering in metric and euclidean spaces and their applications. SIAM Journal on Computing 39(3), 923–947 (2009)
2009
Later among the works it cites.
Kannan, R., Vempala, S.: Spectral algorithms. Foundations and Trends in Theoretical Computer Science 4(3-4), 157–288 (2009)
2009
Later among the works it cites.
Mahajan, M., Nimbhorkar, P., Varadarajan, K.R.: The planar k-means problem is np-hard. In: WALCOM. pp. 274–285 (2009)
2009
Later among the works it cites.
Manthey, B., Rölin, H.: Improved smoothed analysis of the k-means method. In: Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 461–470. Society for Industrial and Applied Mathematics (2009)
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Arthur, D., Vassilvitskii, S.: How slow is the k
2006
Cited alongside, same era.
Berkhin, P.: A survey of clustering data mining techniques. In: Grouping Multidimensional Data, pp. 25 – 71. Springer (2006)
2006
Cited alongside, same era.
Ostrovsky, R., Rabani, Y., Schulman, L.J., Swamy, C.: The effectiveness of lloyd-type methods for the k-means problem. In: FOCS. pp. 165–176 (2006)
2006
Cited alongside, same era.
Arthur, D., Vassilvitskii, S.: k-means++
2007
Cited alongside, same era.
Dasgupta, S., Schulman, L.J.: A probabilistic analysis of em for mixtures of separated, spherical gaussians. Journal of Machine Learning Research 8, 203–226 (2007)
2007
Cited alongside, same era.
Feldman, D., Monemizadeh, M., Sohler, C.: A ptas for k k -means clustering based on weak coresets. In: Proceedings of the 23rd ACM Symposium on Computational Geometry (SoCG). pp. 11 – 18 (2007)
2007
Cited alongside, same era.
Har-Peled, S., Kushal, A.: Smaller coresets for k-median and k-means clustering. Discrete & Computational Geometry 37(1), 3–19 (2007)
2007
Cited alongside, same era.
2009
Later among the works it cites.
Vattani, A.: k k -means requires exponentially many iterations even in the plane. In: Proceedings of the 25th ACM Symposium on Computational Geometry (SoCG ’09). pp. 324–332. Association for Computing Machinery (2009)
2009
Later among the works it cites.
Ackermann, M.R., Blömer, J.: Bregman clustering for separable instances. In: Proceedings of the 12th Scandinavian Symposium and Workshop on Algorithm Theory (SWAT ’10). pp. 212–223. Springer (2010)
2010
Later among the works it cites.
Ackermann, M.R., Blömer, J., Sohler, C.: Clustering for metric and non-metric distance measures. ACM Transactions on Algorithms 6(4), 59:1–26 (2010), special issue on SODA’08
2010
Later among the works it cites.
Awasthi, P., Blum, A., Sheffet, O.: Stability yields a ptas for k-median and k-means clustering. In: FOCS. pp. 309–318 (2010)
2010
Later among the works it cites.
Belkin, M., Sinha, K.: Toward learning gaussian mixtures with arbitrary separation. In: COLT. pp. 407–419 (2010)
2010
Later among the works it cites.
Belkin, M., Sinha, K.: Polynomial learning of distribution families. In: FOCS. pp. 103–112 (2010)
2010
Later among the works it cites.
Jain, A.K.: Data clustering: 50 years beyond k-means. Pattern Recognition Letters 31(8), 651 – 666 (2010)
2010
Later among the works it cites.
Kalai, A.T., Moitra, A., Valiant, G.: Efficiently learning mixtures of two gaussians. In: STOC. pp. 553–562 (2010)
2010
Later among the works it cites.
Kumar, A., Kannan, R.: Clustering with spectral norm and the k k -means algorithm. In: Proceedings of the 51st Annual Symposium on Foundations of Computer Science (FOCS ’10). pp. 299–308. IEEE Computer Society (2010)
2010
Later among the works it cites.
Kumar, A., Sabharwal, Y., Sen, S.: Linear-time approximation schemes for clustering problems in any dimensions. Journal of the ACM 57(2) (2010)
2010
Later among the works it cites.
Moitra, A., Valiant, G.: Settling the polynomial learnability of mixtures of gaussians. In: FOCS 2010 (2010)
2010
Later among the works it cites.
Ackermann, M.R., Blömer, J., Scholz, C.: Hardness and non-approximability of bregman clustering problems. Electronic Colloquium on Computational Complexity (ECCC) 18(15), 1–20 (2011), http://eccc.uni-trier.de/report/2011/015/ , report no. TR11-015
2011
Later among the works it cites.
Braverman, V., Meyerson, A., Ostrovsky, R., Roytman, A., Shindler, M., Tagiku, B.: Streaming k-means on well-clusterable data. In: SODA. pp. 26–40 (2011)
2011
Later among the works it cites.
Feldman, D., Langberg, M.: A unified framework for approximating and clustering data. In: Proceedings of the 43th Annual ACM Symposium on Theory of Computing (STOC). pp. 569 – 578 (2011)
2011
Later among the works it cites.
Ackermann, M.R., Märtens, M., Raupach, C., Swierkot, K., Lammersen, C., Sohler, C.: Streamkm++: A clustering algorithm for data streams. ACM Journal of Experimental Algorithmics 17, article 2.4, 1–30 (2012)
2012
Later among the works it cites.
Fichtenberger, H., Gillé, M., Schmidt, M., Schwiegelshohn, C., Sohler, C.: BICO: BIRCH Meets Coresets for k-Means Clustering . In: Proceedings of the 21st European Symposium on Algorithms (ESA). pp. 481–492 (2013)
2013
Later among the works it cites.
Manthey, B., Röglin, H.: Worst-case and smoothed analysis of k-means clustering with Bregman divergences. JoCG 4(1), 94–132 (2013)
2013
Later among the works it cites.
Awasthi, P., Charikar, M., Krishnaswamy, R., Sinop, A.K.: The hardness of approximation of euclidean k-means. In: SoCG 2015 (accepted) (2015)
2015
Later among the works it cites.
Hamerly, G., Drake, J.: Accelerating lloyd’s algorithm for k-means clustering. In: Partitional Clustering Algorithms, pp. 41 – 78. Springer (2015)
2015
Later among the works it cites.
Venkatasubramanian, S.: Choosing the number of clusters I-III. http://blog.geomblog.org/p/conceptual-view-of-clustering.html (2010), accessed: 2015-03-30
2015
Later among the works it cites.