We study the theoretical and practical runtime limits of k-means and k-median
clustering on large datasets. Since effectively all clustering methods are
slower than the time it takes to read the dataset, the fastest approach is to
quickly compress the data and perform the clustering on the compressed
representation. Unfortunately, there is no universal best choice for
compressing the number of points - while random sampling runs in sublinear time
and coresets provide theoretical guarantees, the former does not enforce
accuracy while the latter is too slow as the numbers of points and clusters
grow. Indeed, it has been conjectured that any sensitivity-based coreset
construction requires super-linear time in the dataset size. We examine this
relationship by first showing that there does exist an algorithm that obtains
coresets via sensitivity sampling in effectively linear time - within
log-factors of the time it takes to read the data. Any approach that
significantly improves on this must then resort to practical heuristics,
leading us to consider the spectrum of sampling strategies across both real and
artificial datasets in the static and streaming settings. Through this, we show
the conditions in which coresets are necessary for preserving cluster validity
as well as the settings in which faster, cruder sampling strategies are
sufficient. As a result, we provide a comprehensive theoretical and practical
blueprint for effective clustering regardless of data size. Our code is
publicly available and has scripts to recreate the experiments.

研究在大型数据集上 k-means 和 k-median 聚类的理论和实际运行限制，通过快速压缩数据并在压缩表示上进行聚类，提供了有效聚类的理论和实践蓝图。

聚类大数据的收敛时间与准确度权衡

Settling Time vs. Accuracy Tradeoffs for Clustering Big Data

$\renewcommand{\Re}{{\rm I\!\hspace{-0.025em} R}}
\newcommand{\eps}{{\varepsilon}} \newcommand{\Coreset}{{\mathcal{S}}} $ In this
paper, we show the existence of small coresets for the problems of computing
$k$-median and $k$-means clustering for points in low dimension. In other
words, we show that given a point set $P$ in $\Re^d$, one can compute a
weighted set $\Coreset \subseteq P$, of size $O(k \eps^{-d} \log{n})$, such
that one can compute the $k$-median/means clustering on $\Coreset$ instead of
on $P$, and get an $(1+\eps)$-approximation.
As a result, we improve the fastest known algorithms for
$(1+\eps)$-approximate $k$-means and $k$-median clustering. Our algorithms have
linear running time for a fixed $k$ and $\eps$. In addition, we can maintain
the $(1+\eps)$-approximate $k$-median or $k$-means clustering of a stream when
points are being only inserted, using polylogarithmic space and update time.

该研究的主要内容是利用 coreset 技术提高 k-means 和 k-median 聚类的近似算法，并且可以在流式数据中保持聚类结果。