On coresets for k-means and k-median clustering

DOI10.1145/1007352.1007400zbMATH Open1192.68904OpenAlexW2045964207MaRDI QIDQ3580976FDOQ3580976

Publication date: 15 August 2010

Published in: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1007352.1007400

Recommendations

On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications
Coresets for $(k, \ell ) $-median clustering under the Fréchet distance
Smaller coresets for $k$-median and $k$-means clustering
Smaller coresets for $k$-median and $k$-means clustering
Towards optimal lower bounds for k-median and k-means coresets
A FAST k-MEANS IMPLEMENTATION USING CORESETS
$K$-medoids and other criteria for crisp clustering
scientific article; zbMATH DE number 7760187
A new coreset framework for clustering

Mathematics Subject Classification ID

Applications of statistics (62P99) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Cited In (84)

Streaming with minimum space: an algorithm for covering by two congruent balls
Sublinear‐time approximation algorithms for clustering via random sampling
A Streaming Algorithm for k-Means with Approximate Coreset
An efficient $K$-means clustering algorithm for tall data
Title not available (Why is that?)
Sublinear-time Algorithms
A linear time algorithm for approximate 2-means clustering
Dynamic coresets
Analysis of incomplete data and an intrinsic-dimension Helly theorem
Practical methods for shape fitting and kinetic data structures using coresets
Small space representations for metric min-sum $k$-clustering and their applications
An almost space-optimal streaming algorithm for coresets in fixed dimensions
Title not available (Why is that?)
Clustering with Internal Connectedness
Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering
A $k$-median algorithm with running time independent of data size
Attainable accuracy guarantee for the $k$-medians clustering in [0, 1]
Metric $k$-median clustering in insertion-only streams
Linear-size universal discretization of geometric center-based problems in fixed dimensions
Title not available (Why is that?)
Efficient approximation algorithms for clustering point-sets
Approximate Range Queries for Clustering
Probabilistic $k$-median clustering in data streams
A Family of Unsupervised Sampling Algorithms
Single facility collection depots location problem in the plane
Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics
On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications
Title not available (Why is that?)
Parameterized $k$-clustering: tractability island
A PTAS for k-means clustering based on weak coresets
Accurate Low-Space Approximation of Metric k-Median for Insertion-Only Streams
Compressive statistical learning with random feature moments
Faster algorithms for the constrained $k$-means problem
Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs
Semi-Supervised Algorithms for Approximately Optimal and Accurate Clustering
On some variants of Euclidean $k$-supplier
A quantization framework for smoothed analysis of Euclidean optimization problems
Summary Data Structures for Massive Data
On the $k$-means/median cost function
How to get close to the median shape
Title not available (Why is that?)
Some results on approximate 1-median selection in metric spaces
Aggregation error for location models: Survey and analysis
Facility Location in Dynamic Geometric Data Streams
An Almost Space-Optimal Streaming Algorithm for Coresets in Fixed Dimensions
A simple $D^2$-sampling based PTAS for $k$-means and other clustering problems
Learning big (image) data via coresets for dictionaries
Clustering through continuous facility location problems
Title not available (Why is that?)
Some Estimates on the Discretization of Geometric Center-Based Problems in High Dimensions
Coresets for the Nearest-Neighbor Rule
On coresets for support vector machines
A fast and recursive algorithm for clustering large datasets with $k$-medians
One-dimensional $k$-center on uncertain data
Local Search Yields a PTAS for $k$-Means in Doubling Metrics
Algorithms for k-median Clustering over Distributed Streams
Uniformity of Point Samples in Metric Spaces Using Gap Ratio
Title not available (Why is that?)
An efficient sum query algorithm for distance-based locally dominating functions
A FAST k-MEANS IMPLEMENTATION USING CORESETS
Title not available (Why is that?)
The Euclidean k-Supplier Problem
Lossy kernelization of same-size clustering
Lossy kernelization of same-size clustering
Title not available (Why is that?)
Computational complexity of the problem of choosing typical representatives in a 2-clustering of a finite set of points in a metric space
Data Exploration by Representative Region Selection: Axioms and Convergence
Coresets for Fuzzy K-Means with Applications
On coresets for fair clustering in metric and Euclidean spaces and their applications
Core-Sets: Updated Survey
Coresets for $(k, \ell ) $-median clustering under the Fréchet distance
On the Optimization Models for Automatic Grouping of Industrial Products by Homogeneous Production Batches
Parameterized approximation algorithms and lower bounds for $k$-center clustering and variants
$k$-median/means with outliers revisited: a simple fpt approximation
Approximating ( k,ℓ )-Median Clustering for Polygonal Curves
Cluster analysis: a modern statistical review
Coresets for kernel clustering
Improved Algorithms for Time Decay Streams
Coresets for Discrete Integration and Clustering
Clustering with faulty centers
Streaming Euclidean \textsc{Max-Cut}: dimension vs data reduction
Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering
An efficient sum query algorithm for distance-based locally dominating functions
On the parameterized intractability of determinant maximization

This page was built for publication: On coresets for k-means and k-median clustering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3580976)