The Power of Uniform Sampling for $k$-Median
Preprint
Abstract
We study the power of uniform sampling for $k$-Median in various metric spaces. We relate the query complexity for approximating $k$-Median, to a key parameter of the dataset, called the balancedness $β\in (0, 1]$ (with $1$ being perfectly balanced). We show that any algorithm must make $Ω(1 / β)$ queries to the point set in order to achieve $O(1)$-approximation for $k$-Median. This particularly implies existing constructions of coresets, a popular data reduction technique, cannot be query-efficient. On the other hand, we show a simple uniform sample of $\mathrm{poly}(k ε^{-1} β^{-1})$ points suffices for $(1 + ε)$-approximation for $k$-Median for various metric spaces, which nearly matches the lower bound. We conduct experiments to verify that in many real datasets, the balancedness parameter is usually well bounded, and that the uniform sampling performs consistently well even for the case with moderately large balancedness, which justifies that uniform sampling is indeed a viable approach for solving $k$-Median.
Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective ClusteringSIAM Journal on Computing, 2020
- Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension2018
- Coresets-Methods and History: A Theoreticians Design Pattern for Approximation and Streaming AlgorithmsKI - Künstliche Intelligenz, 2017
- Less is more: basic variable neighborhood search heuristic for balanced minimum sum-of-squares clusteringInformation Sciences, 2017
- Data reduction for weighted and outlier-resistant clustering2012
- On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their ApplicationsSIAM Journal on Computing, 2009
- Sublinear‐time approximation algorithms for clustering via random samplingRandom Structures & Algorithms, 2006
- A framework for statistical clustering with constant time approximation algorithms for K-median and K-means clusteringMachine Learning, 2006
- Bounded geometries, fractals, and low-distortion embeddings2004
- A Constant-Factor Approximation Algorithm for the k-Median ProblemJournal of Computer and System Sciences, 2002