The Effectiveness of Lloyd-Type Methods for the k-Means Problem

By Rafail M. Ostrovsky, Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy. IEEE Annual Symposium on Foundations of Computer Science, 2006

529 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Signal Processing

View Paper: https://www.semanticscholar.org/paper/9746726b73fa4b0d4450bc78e6bb04c8ed23efde

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Signal Processing

Citations in the corpus

Learning to Count Leaves in Rosette Plants (2015, methodology): “K-means learns K = 50 centroids, using the K-means++ initialization criterion [29].”
Differentially private subspace clustering (2015, background): “It was introduced in [23] to analyze stability of k-means solutions.”
Differentially Private Clustering in High-Dimensional Euclidean Spaces (2017, background): “For example, these well-separated datasets are amenable to slightly perturbed initialization (Ostrovsky et al., 2012).”
Scalable K-Means++ (2012, methodology): “leads to an O(log k) approximation of the optimum [5], or a constant approximation if the data is known to be wellclusterable [30].”
k-means++: the advantages of careful seeding (2007, methodology): “[24] independently proposed an algorithm that is essentially identical to ours, although their analysis is quite different.”
An Algorithm for Online K-Means Clustering (2014, background): “Yet, only recently some theoretical guaranties were proven for its performance on “well clusterable” inputs [23].”
NP-hardness of Euclidean sum-of-squares clustering (2008, background): “The paper is cited in Arthur and Vassilvitskii (2007), Beringer and Hüllermeier (2006), Cilibrasi et al. (2005), Ostrovsky et al. (2006) as giving a proof that MSSC is NP-hard.”
Contextual Markov Decision Processes (2015, background): “This question may relate to the notion of clusters separability (Ostrovsky et al., 2006) - short trajectories can lead to non-separable models that cannot be learned through clustering.”
Core‐sets: An updated survey (2019, background): “…use larger additive error that may be multiplicative under some assumption on the input (e.g., well clustered; S. Dasgupta & Schulman, 2000; Ostrovsky, Rabani, Schulman, & Swamy, 2006), scaled data (Edwards & Varadarajan, 2005; Har-Peled, 2004), by adding more parameters to the coreset's…”
k-Means for Streaming and Distributed Big Sparse Data (2015, methodology): “Experimental results on real world data-sets and open-code that demonstrate how we applied our coreset to boost the performance of the popular Llooyd’s k-means heuristic [21, 4].”
Smooth sensitivity and sampling in private data analysis (2007, methodology): “[15] introduced a measure of quality of k-SED instances called separation.”