Smaller Coresets for k-Median and k-Means Clustering

By Sariel Har-Peled, Akash M. Kushal. 2005

345 citations recorded by the source corpus.

In this paper we show that there exists a $(k,\varepsilon)$-coreset for k-median and k-means clustering of n points in ${\cal R}^d,$ which is of size independent of n. In particular, we construct a $(k,\varepsilon)$-coreset of size $O(k^2/\varepsilon^d)$ for k-median clustering, and of size $O(k^3/\varepsilon^{d+1})$ for k-means clustering.

Subfields: Computer Graphics and Computer-Aided Design, Computer Networks and Communications, Signal Processing

How researchers see this paper

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

In Computer Graphics and Computer-Aided Design

In Computer Networks and Communications

In Signal Processing

Citations in the corpus

Dataset Distillation (2018, background): “Similarly, core-set construction (Tsang et al., 2005; Har-Peled & Kushal, 2007; Bachem et al., 2017; Sener & Savarese, 2018) and instance selection (Olvera-López et al., 2010) methods aim to select a subset of the entire training data, such that models trained on the subset will perform as well as…”
Geometric median in nearly linear time (2016, background): “[4] Õ(n) Assuming d, −1 = O(1) 2005 Har-Peled and Kushal [12] Õ(n+ poly( −1)) Assuming d = O(1) 2011 Feldman and Langberg [10] Õ(nd+ poly(d, −1)) Coreset 2013 Chin et al.”
Towards Total Recall in Industrial Anomaly Detection (2021, background): “Coresets have seen longstanding usage in fundamental kNN and kMeans approaches [22] or mixture models [19] by ﬁnding subsets that best approximate the structure of some available set and allow for approximate solution ﬁnding with notably reduced cost [1,9].”
Universal ε-approximators for integrals (2010, background): “,ck(x) = min1≤i≤k ‖x− ci‖(2) For these families, various algorithms, some randomized [19, 18, 10] and some deterministic [14], provide a measure ν of small support such that ∫ f dν ∈ (1± ε) ∫ f dμ for all f ∈ F .”
k-Means for Streaming and Distributed Big Sparse Data (2015, methodology): “The first coresets for k-means [15, 14] were based on partitioning the data into cells, and take a representative point from each cell to the coreset, as is done in hashing or Hough transform [5].”
Core‐sets: An updated survey (2019, background): “For example, for k -means, the coreset may be a subset of R d but not a subset of P (e.g., Har-Peled & Kushal, 2005; Rosman, Volkov, Feldman, Fisher III, & Rus, 2014).”
Active Learning for Convolutional Neural Networks: A Core-Set Approach (2017, methodology): “For specific learning algorithms, there are methods like core-sets for SVM (Tsang et al., 2005) and core-sets for k-Means and k-Medians (Har-Peled & Kushal, 2005).”
Dimensionality Reduction for k-Means Clustering and Low Rank Approximation (2014, methodology): “As mentioned, there has been an enormous amount of work on exact and approximate k-means clustering algorithms [28, 31, 32, 3, 25].”
A unified framework for approximating and clustering data (2011, positive): “This improves on previous results in [27, 10, 31], where the construction of ε-coresets of size O(k3ε−d−1), O(k2dε−2 log n), and Õ(d2k3ε−2), is respectively presented.”
From Quantity to Quality: Boosting LLM Performance with Self-Guided Data Selection for Instruction Tuning (2023, neutral): “This approach finds its effectiveness in SVM learning (Tsang et al., 2005), k-means (Har-Peled and Kushal, 2005), logistic regression (Munteanu et al., 2018).”
Dataset Distillation by Matching Training Trajectories (2022, methodology): “Similar to dataset distillation, coreset [1, 4, 13, 34, 41] and instance selection [28] aim to select a subset of the entire training dataset, where training on this small subset achieves good performance.”
Scalable Training of Mixture Models via Coresets (2011, neutral): “…that maps a mixture model θ into a tuple y = (s, w, µ̃,W ) where w is a k-tuple of nonnegative weights w̃1, . . . , w̃k summing to 1, s = s1, . . . , sk ⊆ R2d is a set of k d-dimensional subspaces that are weighted by weights W1, · · · ,Wk > 0, and µ̃ = µ̃1, · · · , µ̃k ∈ R2d is a set of k means.”
Geometric Approximation via Coresets (2007, methodology): “Using a more involved construction, Har-Peled and Kushal [HK04] showed that for both kmedian and k-means clustering, one can construct a coreset whose size is independent of the size of the input point set.”
Private coresets (2009, methodology): “Such coresets were introduced by Har-Peled and Mazumdar [32], and successive improvements were given in [31, 11].”
Local Search Methods for k-Means with Outliers (2017, background): “We can then formally define the notion of a coreset [21].”
Selection Via Proxy: Efficient Data Selection For Deep Learning (2019, background): “Core-set selection attempts to find a representative subset of points to speed up learning or clustering; such as k-means and k-medians [Har-Peled and Kushal, 2007], SVM [Tsang et al.”
BICO: BIRCH Meets Coresets for k-Means Clustering (2013, neutral): “Streaming algorithms using summaries include [8, 10, 11, 12, 20, 21, 22].”