2020/12/22 by Vincent Cohen-Addad, Silvio Lattanzi, Cohen-Addad, Vincent +7 · 3 citations
Computer Science · #Advanced Clustering Algorithms Research #Data Management and Algorithms #Data Stream Mining Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #cs.DS #cs.LG
paper · pdf · doi:10.48550/arxiv.2012.11891
arxiv created 2020/12/22 · openalex publication_date 2020/12/22 · arxiv updated 2020/12/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
k-means++ \citearthur2007k is a widely used clustering algorithm that is easy to implement, has nice theoretical guarantees and strong empirical performance. Despite its wide adoption, k-means++ sometimes suffers from being slow on large data-sets so a natural question has been to obtain more efficient algorithms with similar guarantees. In this paper, we present a near linear time algorithm for k-means++ seeding. Interestingly our algorithm obtains the same theoretical guarantees as k-means++ and significantly improves earlier results on fast k-means++ seeding. Moreover, we show empirically that our algorithm is significantly faster than k-means++ and obtains solutions of equivalent quality.