On coresets for k-means and k-median clustering

By Sariel Har-Peled, Soham Mazumdar. 2004

683 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design, 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 Computational Theory and Mathematics

In Computer Graphics and Computer-Aided Design

In Signal Processing

Citations in the corpus

GCR: Gradient Coreset based Replay Buffer Selection for Continual Learning (2021, methodology): “Previous work [28, 29] used coresets for unsupervised learning problems such as K-means & K-medians clustering.”
Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality (2012, methodology): “For any point-set P of size n and query set Q of size n O (1) the algorithm is adaptive with respect to P and Q , with the failure probability of at most 1 /n .”
Training Mixture Models at Scale via Coresets (2017, methodology): “Notably, coresets also imply streaming algorithms for many of these problems (Har-Peled and Mazumdar, 2004; Agarwal et al., 2005; Frahling and Sohler, 2005; Feldman et al., 2007).”
K-variates++: More Pluses in the K-means++ (2016, methodology): “Many local transformations would be eligible for η-stretching probe functions with η small, including local translations, mappings to core-sets (Har-Peled & Mazumdar, 2004), mappings to Voronoi diagram cell centers (Boissonnat et al., 2010), etc. Notice that ineq.”
Coreset-Based Neural Network Compression (2018, background): “Har-Peled and Mazumdar [19] give an alternate solution for coresets that include points not in the original set.”
Core‐sets: An updated survey (2019, methodology): “…problem the cost is the nonsquared distances Composable coresets are important types of coresets that make them especially relevant for handling big or real-time data as explained in the next section (Bentley & Saxe, 1980; Har-Peled & Mazumdar, 2004; Indyk, Mahabadi, Mahdian, & Mirrokni, 2014).”
k-means++: the advantages of careful seeding (2007, background): “Since then, a number of polynomial time approximation schemes have been developed (see [9, 13, 19, 21] and the references therein).”
Locally Private k-Means in One Round (2021, methodology): “To quantify how good is the approximation, it is convenient to use the well-studied notion of coresets (see, e.g., Har-Peled and Mazumdar, 2004), which we recall below.”
Submodularity in Data Subset Selection and Active Learning (2015, methodology): “The second problem is unsupervised subset selection, where the algorithm does not use the labels for selecting data (Wei et al., 2014c; Har-Peled & Mazumdar, 2004).”
GLISTER: Generalization based Data Subset Selection for Efficient and Robust Learning (2020, methodology): “Coreset algorithms have been used for several problems including k-means clustering (Har-Peled and Mazumdar 2004), SVMs (Clarkson 2010) and Bayesian inference (Campbell and Broderick 2018).”
Matrix approximation and projective clustering via volume sampling (2006, methodology): “Other objective functions have also been studied, e. g. sum of distances ( j-median when k = 0, [31, 23 ]) and maximum distance (j-center when k = 0, [10]).”
A unified framework for approximating and clustering data (2011, neutral): “For example, in [28, 10, 21, 23, 19, 24, 31] the starting point for the efﬁcient construction of small ε -coresets for k -median is an efﬁcient bicriteria algorithm for k - median.”
BICO: BIRCH Meets Coresets for k-Means Clustering (2013, neutral): “Streaming algorithms using summaries include [8, 10, 11, 12, 20, 21, 22].”
Fuzzy c-Means Algorithms for Very Large Data (2012, methodology): “Popular samplingbased methods include CLARA [7], CURE [21], and the coreset algorithms [22].”
Private coresets (2009, methodology): “Coresets also imply streaming algorithms for many of these problems [1, 25, 32, 27, 36, 26, 9].”