Approximate clustering via core-sets

By Mihai Badoiu, Sariel Har-Peled, Piotr Indyk. Symposium on the Theory of Computing, 2002

478 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Organizational Behavior and Human Resource Management

View Paper: https://www.semanticscholar.org/paper/1fbff0d0d59e28bb8f943efc5b161ff0dbd11be0

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 Computer Vision and Pattern Recognition

In Organizational Behavior and Human Resource Management

Citations in the corpus

Turning big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering (2013, unknown): “According to the webpages [Ice], the datasets obtained are of a projected size of about 10 Teta-Bytes per year.”
Subgradient and sampling algorithms for l1 regression (2005, result): “The approximate hardness of the weighted sample problem is a property analogous to that of “coresets” for other fitting problems.[ BHPI02 , HPV02, AHPVar, BC02] A novelty here is that while most of the known coreset constructions are for problems where the fit involves minimizing a maximum of distan”
Private coresets (2009, background): “Coresets have been the subject of many recent papers [29, 34, 4, 3, 32, 30, 3, 10, 1, 31, 23, 11, 25] and several surveys [1, 14].”
Data stream clustering: A survey (2013, background): “As detailed in Section 3.1, the authors in Ackermann et al. [2012] propose a way of summarizing the data stream by extracting a small set of objects, named coreset [B ¯ adoiu et al. 2002; Agarwal et al. 2004].”
Geometric Approximation via Coresets (2007, methodology): “[BHI02] gave a simple incremental algorithm for computing an ε-approximation to the minimum-enclosing ball of P .”
StreamKM++: A clustering algorithm for data streams (2010, background): “cedure from [11] to obtain a small coreset [3] of the data stream, i.”
Core Vector Machines: Fast SVM Training on Very Large Data Sets (2005, background): “As probabilistic speeedup may not find the furthest point in each iteration,τ may be larger than 2/ε though it can still be bounded by O(1/ε2) (Bădoiu et al., 2002).”
Geometric median in nearly linear time (2016, methodology): “[1] Õ(d · exp(O( −4))) Sampling 2003 Bose et al.”
Matrix approximation and projective clustering via volume sampling (2006, background): “sum of distances (j-median when k = 0, [28, 21]) and maximum distance (j-center when k = 0, [9]).”
Smaller Coresets for k-Median and k-Means Clustering (2005, background): “... be improved to be similar to the k-median bounds? Can one do FPTAS for k-median and k-means (in both k and 1/e)? Currently, we can only compute the (k ,e )-coreset in fully polynomial time, but cannot extract the approximation itself from it. 2. Does a coreset exists for the problems of k-median”
The Effectiveness of Lloyd-Type Methods for the k-Means Problem (2006, background): “Subsequently a succession of algorithms have appeared [39, 4, 11, 15, 16, 21, 30] with varying runtime dependency on n, k and the dimension.”
Random Forests for Big Data (2015, methodology): “One variant relies on subsampling while three others are related to parallel implementations of random forests and involve either various adaptations of bootstrap to Big Data or “divide-and-conquer” approaches.”
Coreset-Based Neural Network Compression (2018, methodology): “Badoiu et al. [4] propose a coreset formulation to cluster points using a subset of the total set of points to generate the optimal solution.”
Fast approximate spectral clustering (2009, methodology): “Examples include [28], who proposed a nonparametric data reduction scheme based on multiscale de nsity stimation, and [5], who proposed a fast algorithm to extract small “core-sets” from the input data, b sed on which(1 + ǫ)-approximation algorithms for thek-center clustering have been developed.”