Department of Computer Science, Aarhus University, Denmark
<EMAIL_ADDRESS>Research Fund Denmark (DFF) Sapere
Aude Research Leader grant No 1051-00106B.Department of Computer Science,
Aarhus University,
Denmarkomar@cs.au.dkhttps://orcid.org/0000-0002-0042-5231Innovation Fund
Denmark under grant agreement No 0153-00233A. Chris Schwiegelshohn and Omar
Ali Sheikh-Omar [500]Theory of computation Data compression [300]Information
systems Clustering Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz
Herman 4 30th Annual European Symposium on Algorithms (ESA 2022) ESA 2022 ESA
2022 September 5–9, 2022 Berlin/Potsdam, Germany 244 61

# An Empirical Evaluation of $k$-Means Coresets

Chris Schwiegelshohn  Omar Ali Sheikh-Omar

###### Abstract

Coresets are among the most popular paradigms for summarizing data. In
particular, there exist many high performance coresets for clustering problems
such as $k$-means in both theory and practice. Curiously, there exists no work
on comparing the quality of available $k$-means coresets.

In this paper we perform such an evaluation. There currently is no algorithm
known to measure the distortion of a candidate coreset. We provide some
evidence as to why this might be computationally difficult. To complement
this, we propose a benchmark for which we argue that computing coresets is
challenging and which also allows us an easy (heuristic) evaluation of
coresets. Using this benchmark and real-world data sets, we conduct an
exhaustive evaluation of the most commonly used coreset algorithms from theory
and practice.

###### keywords:

coresets, $k$-means coresets, evaluation, benchmark

###### category:

##  1 Introduction

The design and analysis of scalable algorithms has become an important
research area over the past two decades. This is particularly important in
data analysis, where even polynomial running time might not be enough to
handle proverbial _big data_ sets. One of the main approaches to deal with the
scalability issue is to compress or sketch large data sets into smaller, more
manageable ones. The aim of such compression methods is to preserve the
properties of the original data, up to some small error, while significantly
reducing the number of data points.

Among the most popular and successful paradigms in this line of research are
_coresets_ [42]. Informally, given a data set $A$, a coreset $\Omega\subset A$
with respect to a given set of queries $Q$ and query function $f:A\times
Q\rightarrow\mathbb{R}_{\geq 0}$ approximates the behaviour of $A$ for all
queries up to some multiplicative distortion $D$ via $\sup_{q\in
Q}\max\left(\frac{f(\Omega,q)}{f(A,q)},\frac{f(A,q)}{f(\Omega,q)}\right)\leq
D.$ Coresets have been applied to a number of problems such as computational
geometry [2, 9], linear algebra [32, 36], and machine learning [38, 43]. But
the by far most intensively studied and arguably most successful applications
of the coreset framework is the $k$-clustering problem.

Here we are given $n$ points $A$ with (potential unit) weights
$w:A\rightarrow\mathbb{R}_{\geq 0}$ in some metric space with distance
function dist and aim to find a set of $k$ centers $C$ such that

$\text{cost}_{A}(C):=\frac{1}{n}\sum_{p\in A}\min_{c\in
C}w(p)\cdot\text{dist}^{z}(p,c)$

is minimized. The most popular variant of this problem is probably the
$k$-means problem in $d$-dimensional Euclidean space where $z=2$ and
$\text{dist}(x,y)=\sqrt{\sum_{i=1}^{d}(x_{i}-y_{i})^{2}}$.

A $(k,\varepsilon)$-coreset is now a subset $\Omega\subset A$ with weights
$w:\Omega\rightarrow\mathbb{R}_{\geq 0}$ such that for any set of $k$ centers
$C$

$\sup_{C}\max\left(\frac{\text{cost}_{A}(C)}{\text{cost}_{\Omega}(C)},\frac{\text{cost}_{\Omega}(C)}{\text{cost}_{A}(C)}\right)\leq
1+\varepsilon.$ (1)

The coreset definition in Equation 1 provides an upper bound for the
distortion of all candidate solutions i.e., all possible sets of $k$ centers.
A _weak coreset_ is a relaxed guarantee that holds for optimal or nearly
optimal clusterings of $A$ instead of all clusterings.

In a long line of work spanning the last 20 years [4, 8, 10, 16, 17, 21, 22,
28, 27, 29, 31, 8, 35, 46], the size of coresets has been steadily improved
with the current state of the art yielding a coreset with
$\tilde{O}(k\varepsilon^{-2}\cdot\min(d,k,\varepsilon^{-2}))$ points for a
distortion $D\leq(1+\varepsilon)$ due to [13]111We use $\tilde{O}(x)$ to hide
$\log^{c}x$ terms for any constant $c$..

While we have a good grasp of the theoretical guarantees of these algorithms,
our understanding of the empirical performance is somewhat lacking. There
exist a number of coreset implementations, but it is usually difficult to
assess which implementation summarizes the data best. To accurately evaluate a
given coreset, we would need to come up with a $k$ clustering $C$ which
results in a maximal distortion. Solving this problem is likely difficult:
related questions such as deciding whether a 3-dimensional point set $A$ is an
$\varepsilon$-net of a set $B$ with respect to convex ranges is co-NP hard
[26]. It is similarly co-NP hard to decide whether a point set $A$ is a _weak
coreset_ of a point set $B$ (see Proposition B.1 in the appendix).

Due to this difficulty, a common heuristic for evaluating coresets is as
follows [1, 24]. First, compute a coreset $\Omega$ with the available
algorithm(s) using some input data $A$. Then, run an optimization algorithm on
$\Omega$ to compute a $k$ clustering. The _best_ coreset algorithm is
considered to be the one which yields a clustering with the smallest cost.

This practice has substantial drawbacks. The first is that this evaluation
method conflates the two separate tasks of coreset construction and
optimization. It is important to note that the first step of virtually all
coreset algorithms is a low-cost (bicriteria) constant factor approximation,
i.e. a solution with $\beta\cdot k$ clusters that costs at most
$\alpha\cdot\text{OPT}$, where OPT is the cost of an optimal $k$ clustering.
Given that this initial solution has an $\alpha$ approximation to the cost, a
routine calculation shows that the additive error of the coreset, i.e. the
maximum difference $\left|\text{cost}_{A}(C)-\text{cost}_{B}(C)\right|$ over
all solutions $C$ is at most $O(\alpha)\cdot\text{cost}_{A}(C)$. In
particular, in the case that the initial bicriteria approximation has
$\alpha\ll 2$, which is not too difficult to achieve with more than $k$
centers, any $\gamma$ approximation algorithm will find solutions with
approximation factor $O(\gamma+\alpha)\cdot\text{OPT}$. In particular, the
distortion may be unbounded, for example if $B$ only consists of the $k$
centers, while simply returning $B$ itself yields a low cost clustering. Thus,
it is difficult to measure coreset quality in this way.

The second drawback is that this practice will mainly measure the performance
of the optimization algorithm, rather than the performance of the coreset
algorithms. During its execution it might simply not consider any solution
with high distortion. For example, if the approximation factor $\gamma$ of the
solution returned by the algorithm is large then this solution (as well as any
even higher cost solution considered during the algorithm’s execution) will
have a low distortion.

The third drawback of this evaluation method is that it does not consider the
main use cases of coresets, nor the full power of their guarantee. Indeed, if
speeding up the computation of an optimization algorithm, one would hardly
need a strong coreset; approximating the cost of every candidate solution, as
weaker coreset definitions (or indeed a bicriteria approximation) would be
suitable as well. A coreset’s main and most powerful feature is
_composability_ , i.e. given two disjoint point sets $X$ and $Y$, the union of
a coreset of $X$ and a coreset of $Y$ is a coreset. Composability is what
enables coresets to scale to massively parallel computation models and enables
simple streaming algorithms via the merge and reduce technique. To which
degree a coreset is composable is generally not a property of an optimal
clustering of the point set, as optimal solutions $C_{X}$ of $X$ or $C_{Y}$ of
$Y$ may have little in common with an optimal solution of $X\cup Y$.

The purpose of this study is to systematically evaluate the quality of various
coreset algorithms for $k$-means. As such, we develop a new evaluation
procedure which estimates the distortion of coreset algorithms. On real-world
data sets, we observe that while the evaluated coreset algorithms are
generally able to find solutions with comparable costs, there is a stark
difference in their distortions. This shows that differences between
optimization and compression are readily observable in practice.

As a complement to our evaluation procedure on real-world data sets, we
propose a benchmark framework for generating synthetic data sets. We argue why
this benchmark has properties that results in hard instances for all known
coreset constructions. We also show how to efficiently estimate the distortion
of a candidate coreset on the benchmark.

##  2 Coreset Algorithms

Though the algorithms vary in details, coreset constructions come in one of
the following two flavours:

  1. 1.

Movement-based constructions: Such algorithms compute a coreset $\Omega$ with
$T$ points given some input point set $A$ such that
$\text{cost}_{\Omega}(C)\ll\text{OPT}$, where OPT is the cost of an optimal
$k$-means clustering of $A$. The coreset guarantee then follows as a
consequence of the triangle inequality. These algorithms all have an
exponential dependency on the dimension $d$, and therefore have been overtaken
by sampling-based methods. Nevertheless, these constructions are more robust
to various constrained clustering formulations [30, 45] and continue to be
popular. Examples from theory include [25, 28].

  2. 2.

Importance sampling: Points are sampled proportionate to their impact on the
cost of any given candidate solution. The idealized distribution samples
proportionate to the sensitivity which for a point $p$ is defined as
$sens(p):=\sup_{C}\frac{\min_{c\in
C}\text{dist}^{2}(p,c)}{\text{cost}_{A}(C)}$ and weighted by their inverse
sampling probability. The sensitivities are hard to compute exactly but much
work exists on how to find other distributions with very similar properties.
In terms of theoretical performance, sensitivity sampling has largely replaced
movement-based constructions, see for example [21, 35].

Of course, there exist algorithms that draw on techniques from both, see for
example [17]. In what follows, we will survey implementations of various
coreset constructions that we will evaluate later.

StreamKM++ [1]: The popular $k$-means++ algorithm [3] computes a set of
centers $K$ by iteratively sampling a point $p$ in $A$ proportionate to
$\min_{q\in K}\text{dist}^{2}(p,q)$ and adding it to $K$. The procedure
terminates once the desired number of centers has been reached. The first
center is typically picked uniformly at random. The StreamKM++ paper runs the
$k$-means++ algorithms for $T$ iterations, where $T$ is the desired coreset
size. At the end, every point $q$ in $K$ is weighted by the number of points
in $A$ closest to it. While the construction has elements of importance
sampling, the analysis is largely movement-based. The provable bound required
for the algorithm to compute a coreset is $O\left(\frac{k\log
n}{\delta^{d/2}\varepsilon^{d}}\cdot\log^{d/2}\frac{k\log
n}{\delta^{d/2}\varepsilon^{d}}\right)$. Despite its simplicity, its running
time compares unfavourably to all other constructions.

BICO [24]: BICO combines the very fast, but poor quality clustering algorithm
BIRCH [49] with the movement-based analysis from [25, 28]. The clustering is
organized by way of a hierarchical decomposition: When adding a point $p$ to
one of the coreset points $\Omega$ at level $i$, it first finds the closest
point $q$ in $\Omega$. If $p$ is too far away from $q$, a new cluster is
opened with center at $p$. Otherwise $p$ is either added to the same cluster
as $q$, or, if adding $p$ to $q$’s cluster increases the clustering cost
beyond a certain threshold, the algorithm attempts to add $p$ to the child-
clusters of $q$. The procedure then continues recursively. The provable bound
required for the algorithm to compute a coreset is
$O\left(k\varepsilon^{-d-2}\log n\right)$.

Ray Maker [27]: The algorithm computes an initial solution with $k$ centers
which is a constant factor approximation of the optimal clustering. Around
each center, $O(1/\epsilon^{d-1})$ random rays are created which span the
hyperplane. Next, each point $p\in A$ is snapped to its closest ray resulting
in a set of one-dimensional points associated with each ray. Afterwards, a
coreset is created for each ray by computing an optimal 1D clustering with
$k^{2}/\epsilon^{2}$ centers and weighing each center by the number of points
in each cluster. The final coreset is composed of the coresets computed for
all the rays. The provable bound required for the algorithm to compute a
coreset is $O(k^{3}\cdot\varepsilon^{-d-1})$. The algorithm has recently
received some attention due to its applicability to the fair clustering
problem [30].

Sensitivity Sampling [21]: The simplest implementation of sensitivity sampling
first computes an $(O(1),O(1))$ bicriteria approximation222An $(\alpha,\beta)$
bicriteria approximation computes an $\alpha$ approximation using $\beta\cdot
k$ many centers., for example by running $k$-means++ for $2k$ iterations [48].
Let $K$ be the $2k$ clustering thus computed and let $K_{i}$ be an arbitrary
cluster of $K$ with center $q_{i}$. Subsequently, the algorithm picks points
proportionate to
$\frac{\text{dist}^{2}(p,q)}{\text{cost}_{K_{i}}(\\{q_{i}\\})}+\frac{1}{|K_{i}|}$
and weighs any point by its inverse sampling probability. Let $|\hat{K_{i}}|$
be the estimated number of points in the sample. Finally, the algorithm weighs
each $q_{i}$ by $(1+\varepsilon)\cdot|K_{i}|-|\hat{K_{i}}|$. The provable
bound required for the algorithm to compute a coreset is
$\tilde{O}\left(kd\varepsilon^{-4}\right)$ ([21]),
$\tilde{O}\left(k\varepsilon^{-6}\right)$ ([31]), or
$\tilde{O}\left(k^{2}\varepsilon^{-4}\right)$ ([8]).

Group Sampling [17]: First, the algorithm computes an $O(1)$ approximation (or
a bicriteria approximation) $K$. Subsequently, the algorithm preprocesses the
input into groups such that (1) for any two points $p,p^{\prime}\in K_{i}$,
their cost is identical up to constant factors and (2) for any two clusters
$K_{i},K_{j}$, their cost is identical up to constant factors. In every group,
Group Sampling now samples points proportionate to their cost. The authors of
[17] show that there always exist a partitioning into $\log^{2}1/\varepsilon$
groups. Points not contained in a group are snapped to their closest center
$q$ in $K$. $q$ is weighted by the number of points snapped to it. The
provable bound required for the algorithm to compute a coreset is
$\tilde{O}\left(k\varepsilon^{-2}\min(d,k,\varepsilon^{-2})\right)$ ([13]).
While this improves over sensitivity sampling, it is generally slower and not
as easy to implement.

Finally, we note that some of the more popular algorithms in theory have not
been mentioned here. For example, Chen’s [10] construction is particularly
popular among theoreticians. The Group Sampling algorithm by [17] is an
extension and improvement of Chen’s method. Thus, the performance of Group
Sampling is also indicative of Chen’s algorithm.

#### Dimension Reduction

Finally, we also combine coreset constructions with a variety of dimension
reduction techniques. Starting with [19], a series of results [4, 5, 6, 7, 12,
18, 22, 23, 34, 39, 46] explored the possibility of using dimension reduction
methods for $k$-clustering, with a particular focus on principal component
analysis (PCA) and random projections. The seminal paper by Feldman, Schmidt,
and Sohler [22] was the first to use dimension reduction to obtain smaller
coresets for $k$-means. Movement-based coresets in particular often have an
exponential dependency on the dimension, which can be alleviated with some
form of dimension reduction, both in theory [45] and in practice [33]. There
are essentially two main dimension reduction techniques for coresets.

Principal Component Analysis: Feldman, Schmidt, and Sohler [22] showed that
projecting an input $A$ onto the first $O(k/\varepsilon^{2})$ principal
components is a coreset. This coreset still consists of $n$ points, but they
now lie in low dimension. The analysis was subsequently tightened by [12] and
extended to other center-based cost functions by [46]. Although its target
dimension is generally worse than those based on random projections and
terminal embeddings, there is nevertheless reasons for using PCA regardless:
It removes noise and thus may make it easier to compute a high quality
coreset. For more applications of PCA to $k$-means clustering, we refer to

Terminal Embeddings: Given a set of points $A$ in $\mathbb{R}^{D}$, a terminal
embedding $f:\mathbb{R}^{D}\rightarrow\mathbb{R}^{d}$ preserves the pairwise
distance between any point $p\in A$ and any point $q\in\mathbb{R}^{D}$ up to a
$(1\pm\varepsilon)$ factor. The statement is related to the famous Johnson-
Lindenstrauss lemma but it is stronger as it does not apply to only the
pairwise distances of $A$. Nevertheless, the same target dimension is
sufficient. Terminal embeddings were studied by [11, 20, 37, 44], with
Narayanan and Nelson [44] achieving an optimal target dimension of
$O(\varepsilon^{-2}\log n)$, where $n$ is the number of points. We note that
terminal embeddings, combined with an iterative application of the coreset
construction from [8], can reduce the target dimension to a factor
$\tilde{O}(\varepsilon^{-2}\log k)$. This is mainly of theoretical interest,
as in practice the deciding factor wrt the target dimension is the precision,
rather than dependencies on $\log n$ and $\log k$. For applications to
coresets, we refer to [4, 17, 31]. For an empirical evaluation of random
projections, which form the basis of all known terminal embeddings, we refer
to Venkatsubramanian and Wang [47].

##  3 Benchmark Construction

In this section, we describe our benchmark. We start by describing the aims of
the benchmark, followed by giving the construction. Our aim is to generate a
data set containing many clusterings with the following properties.

  1. 1.

The benchmark has many clusterings that, in a well defined sense, are highly
dissimilar. Specifically, we want the overlap between any two clusters of
different clusterings to be small.

  2. 2.

The different clusterings have very similar and low cost. This ensures that
despite the solutions being different in terms of composition and center
placement, a good coreset has to consider them equally regarding distortion.

  3. 3.

The clusterings are induced by a minimal cost assignment of input points to a
set of centers in $\mathbb{R}^{d}$. This final property ensures that the
coreset guarantee has to apply to these clusterings.

To generate the benchmark, we now use the following construction. The
benchmark has a parameter $\alpha$ which controls the number of points and
dimensions of the generated data instance. For a given value of $k$, the
benchmark instance consists of $n=k^{\alpha}$ points and $d=\alpha\cdot k$
dimensions, i.e. we will construct and $n\times d$ matrix $A$ where every row
corresponds to an input point and every column corresponds to one of the
dimensions.

Let $\mathds{1}_{k}$ be the $k$-dimensional all-one vector and $v_{i}^{1}$ be
the $k$-dimensional vector with entries
$(v_{i}^{1})_{j}=\begin{cases}-\frac{1}{k}&\text{if }i\neq j\\\
\frac{k-1}{k}&\text{if }i=j\end{cases}$. For $\ell\leq\alpha$, recursively
define the $k^{\ell}$ dimensional vector
$v_{i}^{\ell}=v_{i}^{\ell-1}\otimes\mathds{1}_{k}$, where $\otimes$ denotes
the Kronecker product, i.e.
$v_{i}^{\ell-1}\otimes\mathds{1}_{k}=\begin{bmatrix}(v_{i}^{\ell-1})_{1}\cdot\mathds{1}_{k}\\\
(v_{i}^{\ell-1})_{2}\cdot\mathds{1}_{k}\\\ \vdots\\\
(v_{i}^{\ell-1})_{1}\cdot\mathds{1}_{k}\end{bmatrix}$. Finally, set the $t$-th
column of $A$, for $t=a\cdot k+b$, $a\in\\{0,\ldots\alpha-1\\}$ and
$b\in\\{1,\ldots k\\}$, to be $\mathds{1}_{k^{\alpha-a+1}}\otimes
v_{b}^{a+1}$.

To get a better feel for the construction, we have given two small example
instances for $k=2$ and $k=3$ in Figue Figure 1.

$\begin{bmatrix}\frac{1}{2}&-\frac{1}{2}&\frac{1}{2}&-\frac{1}{2}&\frac{1}{2}&-\frac{1}{2}\\\
-\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&-\frac{1}{2}&\frac{1}{2}&-\frac{1}{2}\\\
\frac{1}{2}&-\frac{1}{2}&-\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&-\frac{1}{2}\\\
-\frac{1}{2}&\frac{1}{2}&-\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&-\frac{1}{2}\\\
\frac{1}{2}&-\frac{1}{2}&\frac{1}{2}&-\frac{1}{2}&-\frac{1}{2}&\frac{1}{2}\\\
-\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&-\frac{1}{2}&-\frac{1}{2}&\frac{1}{2}\\\
\frac{1}{2}&-\frac{1}{2}&-\frac{1}{2}&\frac{1}{2}&-\frac{1}{2}&\frac{1}{2}\\\
-\frac{1}{2}&\frac{1}{2}&-\frac{1}{2}&\frac{1}{2}&-\frac{1}{2}&\frac{1}{2}\\\
\end{bmatrix}\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\begin{bmatrix}\frac{2}{3}&-\frac{1}{3}&-\frac{1}{3}&\frac{2}{3}&-\frac{1}{3}&-\frac{1}{3}\\\
-\frac{1}{3}&\frac{2}{3}&-\frac{1}{3}&\frac{2}{3}&-\frac{1}{3}&-\frac{1}{3}\\\
-\frac{1}{3}&-\frac{1}{3}&\frac{2}{3}&\frac{2}{3}&-\frac{1}{3}&-\frac{1}{3}\\\
\frac{2}{3}&-\frac{1}{3}&-\frac{1}{3}&-\frac{1}{3}&\frac{2}{3}&-\frac{1}{3}\\\
-\frac{1}{3}&\frac{2}{3}&-\frac{1}{3}&-\frac{1}{3}&\frac{2}{3}&-\frac{1}{3}\\\
-\frac{1}{3}&-\frac{1}{3}&\frac{2}{3}&-\frac{1}{3}&\frac{2}{3}&-\frac{1}{3}\\\
\frac{2}{3}&-\frac{1}{3}&-\frac{1}{3}&-\frac{1}{3}&-\frac{1}{3}&\frac{2}{3}\\\
-\frac{1}{3}&\frac{2}{3}&-\frac{1}{3}&-\frac{1}{3}&-\frac{1}{3}&\frac{2}{3}\\\
-\frac{1}{3}&-\frac{1}{3}&\frac{2}{3}&-\frac{1}{3}&-\frac{1}{3}&\frac{2}{3}\\\
\end{bmatrix}$ Figure 1: Benchmark construction for $k=2$ and $\alpha=3$
(left) and $k=3$ and $\alpha=2$ (right).

#### Properties of the Benchmark

We now summarize the key properties of the benchmark. To this end, we require
a few notions. Let $A$ be the input matrix. We slightly abuse notation and
refer to $A_{i}$ as both the $i$th point as well as the $i$th row of the
matrix $A$. For a clustering $\mathcal{C}=\\{C_{1},\ldots,C_{k}\\}$, we define
that the $n\times k$ indicator matrix $\tilde{X}$ induced by $\mathcal{C}$ via
$\tilde{X}_{i,j}=\begin{cases}1&\text{if }A_{i}\in C_{j}\\\
0&\text{else.}\end{cases}$ Furthermore, we will also use the $n\times k$
normalized clustering matrix $X$ defined as
$X_{i,j}=\begin{cases}\frac{1}{\sqrt{|C_{i}|}}&\text{if }A_{i}\in C_{j}\\\
0&\text{else.}\end{cases}$ We also recall the following lemma which will allow
us to express the $k$-means cost of a clustering $\mathcal{C}$ with optimally
chosen centers in terms of the cost of $X$ and $A$.

######  Lemma 3.1 (Folklore).

Let $A$ be an arbitrary set of points and let $\mu(A)=\frac{1}{|A|}\sum_{p\in
A}p$ be the mean. Then $\sum_{p\in
A}\|p-c\|^{2}=|A|\cdot\|\mu(A)-c\|^{2}+\sum_{p\in A}\|p-\mu(A)\|^{2}$ for any
point $c$.

This lemma proves that for any given cluster $C_{j}$, the mean is the optimal
choice of center. We also note that any two distinct columns of $X$ are
orthogonal. Furthermore $\frac{1}{n}\mathbf{1}\mathbf{1}^{T}A$ copies the mean
into every entry of $A$. Combining these two observations, we see that the
matrix $XX^{T}A$ maps the $i$th row of $A$ onto the mean of the cluster it is
assigned to. Finally, define the Frobenius norm of an $n\times d$ $A$ by
$\|A\|_{F}=\sqrt{\sum_{i=1}^{n}\sum_{j=1}^{d}A_{i,j}^{2}}$. Then the $k$-means
cost of the clustering $\mathcal{C}$ is precisely $\|A-XX^{T}A\|_{F}^{2}.$

We also require the following distance measure on clusterings as proposed by
Meila [40, 41]. Given two clusterings $\mathcal{C}$ and
$\mathcal{C^{\prime}}$, the $k\times k$ confusion matrix $M$ is defined as
$M_{i,j}=|C_{i}\cap C^{\prime}_{j}|.$ Furthermore for the indicator matrices
$\tilde{X}$ and $\tilde{X}^{\prime}$ induced by $\mathcal{C}$ and
$\mathcal{C^{\prime}}$ we have the identity
$M=\tilde{X}^{T}{\tilde{X}^{\prime}}$. Denote by $\Pi_{k}$ the set of all
permutations over $k$ elements. Then the distance between $\mathcal{C}$ and
$\mathcal{C^{\prime}}$ is defined as
$d(\mathcal{C},\mathcal{C^{\prime}})=1-\frac{1}{n}\underset{\pi\in\Pi_{k}}{\max}\sum_{i=1}^{k}M_{i,\pi(i)}.$
Observe that for clusters that are identical, their distance is $0$. The
maximum distance between any two $k$ clusterings is always $\frac{k-1}{k}$.

The solutions we consider are given as follows. For the columns $a\cdot
k+1,\ldots(a+1)\cdot k$, we define the clustering
$\mathcal{C}^{a}=\\{C_{1}^{a},\ldots C_{k}^{a}\\}$ with $A_{i}\in C_{j}^{a}$
if and only if $A_{i,j}>0$. Let $\tilde{X}^{a}$ and $X^{a}$ denote the
indicator matrix and clustering matrix, respectively, as induced by
$\mathcal{C}^{a}$. These clusterings satisfy the properties we stated at the
beginning of this section, that is:

  1. 1.

The distance between these clustering is $1-\frac{1}{k}$, i.e. it is
maximized.

  2. 2.

The clusterings have equal cost and the centers in each clustering have equal
cost.

  3. 3.

The clusterings are induced by a set of centers in $\mathbb{R}^{d}$.

#### Benchmark Evaluation

We now describe how we use the benchmark to measure the distortion of a
coreset. Assume for now that the coresets are subsets of the original input
points. The extension to coresets that do not consist of input points is
described at the end of this section.

Consider the clustering $\mathcal{C}^{a}=\\{C_{1}^{a},\ldots C_{k}^{a}\\}$ for
some $a$ and let $\Omega$ with weights $w:\Omega\rightarrow\mathbb{R}_{\geq
0}$ be the coreset and let $\delta>0$ be a parameter. Note that there are
$\alpha$ many such clusterings, for each value of $a$. We use
$w(C_{i}^{a}\cap\Omega):=\sum_{p\in C_{i}^{a}\cap\Omega}w(p)$ to denote the
mass of points of $C_{i}^{a}$ in $\Omega$. For every cluster $C_{i}^{a}$ with
$w(C_{i}^{a}\cap\Omega)\geq|C_{i}|(1-\delta)$, we place a center at
$\mu(C_{i}^{a})$. Conversely, if
$w(C_{i}^{a}\cap\Omega)<|C_{i}^{a}|(1-\delta)$, we do not place a center at
$\mu(C_{i}^{a})$. We call such clusters _deficient_. Let $\mathcal{S}$ be the
centers of these deficient clusters.

We now compare the cost as computed on the coreset and the true cost of
$\mathcal{S}$. Due to Lemma 3.1 and the fact that all clusters have equal
cost, we may write for any deficient cluster $C_{i}^{a}$
$\text{cost}_{C_{i}^{a}}(\mathcal{S})=\text{cost}_{C_{j}^{a}}(\\{\mu(C_{j}^{a})\\})+k^{\alpha-1}\|\mu(C_{j}^{a})-\mu(C_{h}^{a})\|_{2}^{2}$,
where $C_{h}^{a}$ is a non-deficient cluster. Thus, the cost is
$\text{cost}_{C_{i}^{a}}(\mathcal{S})\approx\left(1+\frac{2}{\alpha}\right)\cdot\text{cost}_{C_{j}^{a}}(\\{\mu(C_{j}^{a})\\}).$

Conversely, the cost on the coreset is

$\displaystyle\text{cost}_{\Omega\cap
C_{i}^{a}}(\mathcal{S})\approx\frac{w(C_{i}^{a}\cap\Omega)}{\text{cost}_{C_{j}^{a}}(\\{\mu(C_{j}^{a})\\})}\left(1+\frac{2}{\alpha}\right)\cdot\text{cost}_{C_{j}^{a}}(\\{\mu(C_{j}^{a})\\}).$

Thus for each deficient clustering individually, the distortion will be close
to $\frac{k^{\alpha-1}}{w(C_{i}^{a}\cap\Omega)}\geq\frac{1}{1-\varepsilon}$.
If there are many deficient clusters, then this will also be the overall
distortion. For all possible (suitably discretized) thresholds for deficiency,
i.e. all values of $\delta$, we can now identify the clustering
$\mathcal{C}^{a}$ with a maximum number of deficient clusters and use the
aforementioned construction to get a lower bound on the distortion.

To extend this evaluation to coresets where the points are not part of the
input, we consider a point $p\in\Omega$ to be in $C_{i}^{a}$ if it is closer
to $\mu(C_{i}^{a})$ than to to $\mu(C_{j}^{a})$.

##  4 Experiments

In this section, we present how we evaluated different algorithms. First, we
propose our evaluation procedure which gauges the quality of coresets. Then,
we describe the data sets used for the empirical evaluation and our
experimental setup. Finally, we detail the outcome of the experiments and our
interpretation of the results.

### Evaluation Procedure

Accurately evaluating a $k$-means coreset of a real-world data set requires
constructing a solution (a set of $k$ centers) which results in a maximal
distortion. Finding such a solution, however, is difficult. Instead, we can
estimate the quality of a given coreset by finding meaningful candidate
solutions.

A first attempt can be to randomly generate candidate solutions. It is not
readily apparent how to define a distribution of meaningful solutions from
which to sample. One could, for instance, generate $k$ random points inside
the convex hull or the minimum enclosing ball (MEB) of a coreset $\Omega$.
Convex hulls in high dimensions are infeasible to compute, so we sample a
center by choosing random convex combination of the centers of the initial
bicriteria approximation computed for every coreset. A better way to generate
candidate solutions turns out to be $k$-means++, where we sample $k$ points
with respect to the $k$-means++ distribution and use the resulting centers as
a solution (see Appendix F in the appendix). The main advantage of this
approach is that $k$-means++ can uncover natural cluster structures in the
data, which uniform sampling generally does not. For all variants, we
generated $5$ candidate solutions, where the candidate solution with the
largest distortion being a lower bound for the true distortion of the coreset.

Given the usefulness of evaluating coresets on real-world data sets, it can be
tricky to gauge the general performance of coreset algorithms using only a
small selection of data sets. For this reason, we used our benchmark to
complement the evaluation on real-world data sets. The benchmark accomplishes
two important tasks. First, the benchmark allows us to quickly find a bad
solution because both good and bad clusterings are known a priori. It is
unclear how to find bad clusterings for real-world data sets. Second, it is
easier to make a fair comparison of different coreset constructions because
the benchmark is known to generate hard instances for all known coreset
algorithms. This cannot be said for real-world data sets. For the benchmark,
we computed the distortion following the evaluation procedure described in
Section 3.

Every randomized coreset construction was repeated $10$ times. We aggregated
the reported maximum distortions for every run by taking the average over all
$10$ evaluations. It is important to not aggregate the distortions here by
taking the maximum over all runs: If one run of the coreset algorithm fails
but the others succeed, then such an aggregation predicts far worse distortion
than what we could typically expect.

| Data points | Dimensions
---|---|---
Caltech | 3,680,458 | 128
Census | 2,458,285 | 68
Covertype | 581,012 | 54
NYTimes | 500,000 | 102,660
Tower | 4,915,200 | 3
Table 1: The sizes of the real-world datasets used for the experimental evaluation $k$ | $\alpha$ | Data points | Dimensions
---|---|---|---
10 | 6 | 1,000,000 | 60
20 | 5 | 3,200,000 | 100
30 | 4 | 810,000 | 120
40 | 4 | 2,560,000 | 160
Table 2: The parameter values and the sizes of the benchmark instances used
for the experimental evaluation.

### Data sets

We conducted experiments on five real-world data sets Census, Covertype,
Tower, Caltech, NYTimes, and four instances of our benchmark. Benchmark
instances were generated to match approximately the sizes of the real-world
data sets. The sizes of the considered data sets are given in Table 1.

The Census333https://archive.ics.uci.edu/ml/datasets/US+Census+Data+(1990)
dataset is a small subset of the Public Use Microdata Samples from 1990 US
census. It consists of demographic information encoded as 68 categorical
attributes of 2,458,285 individuals.

Covertype444https://archive.ics.uci.edu/ml/datasets/covertype is comprised of
cartographic descriptions and forest cover type of four wilderness areas in
the Roosevelt National Forest of Northern Colorado in the US. It consists of
581,012 records, 54 cartographic variables and one class variable. Although
Covertype was originally made for classification tasks, it is often used for
clustering tasks by removing the class variable [1].

The data set with the fewest number of dimensions is
Tower555http://homepages.uni-paderborn.de/frahling/coremeans.html. This data
set consists of 4,915,200 rows and 3 features as it is a 2,560 by 1,920
picture of a tower on a hill where each pixel is represented by a RGB color
value.

Inspired by [24], Caltech was created by computing SIFT features from the
images in the
Caltech101666http://www.vision.caltech.edu/Image_Datasets/Caltech101/ image
database. This database contains pictures of objects partitioned into 101
categories. Disregarding the categories, we concatenated the 128-dimensional
SIFT vectors from each image into one large data matrix with 3,680,458 rows
and 128 columns.

NYTimes777https://archive.ics.uci.edu/ml/datasets/bag+of+words is a dataset
composed of the bag-of-words (BOW) representations of 300,000 news articles
from The New York Times. The vocabulary size of the text collection is
102,660. Due to the BOW encoding, NYTimes has a very large number of
dimensions and is highly sparse. To make processing feasible, we reduced the
number of dimensions to 100 using terminal embeddings.

### Preprocessing & Experimental Setup

To understand how denoising effects the quality of the outputted coresets, we
applied Principal Component Analysis (PCA) on Caltech, Census, Covertype, and
NYTimes by using the $k$ singular vectors corresponding to the largest
singular values. We did not perform any preprocessing on Tower due to its low
dimensionality.

We followed the same experimental procedure with respect to the choice of
parameter values for the algorithms as prior works [1, 24]. For the target
coreset size $T$, we experimented with $T=mk$ for $m=\\{50,100,200,500\\}$. On
Caltech, Census, Covertype, and NYTimes, we used values $k$ in
$\\{10,20,30,40,50\\}$, while for Tower we used larger cluster sizes
$k\in\\{20,40,60,80,100\\}$. On the benchmark, we used
$k\in\\{10,20,30,40\\}$.

We implemented Sensitivity Sampling, Group Sampling, Ray Maker, and StreamKM++
in C++. The source code can be found on
GitHub888https://github.com/sheikhomar/eval-k-means-coresets. For BICO, we
used the authors’ reference implementation999https://ls2-www.cs.tu-
dortmund.de/grav/en/bico. The source code was compiled with gcc 9.3.0. The
experiments were performed on a machine with Intel Core i9 10940X 3.3GHz
14-Core and 2x DDR4 PC3200 128GB RAM.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

Figure 2: The average distortions of the evaluated coreset algorithms with
coreset size $T=200k$ on five real-world data sets and on four benchmark
instances. Black bars indicate standard deviations. Notice that the axis is
non-linear as otherwise the bars for Sensitivity Sampling and Group Sampling
would disappear on the plots as their distortions are close to 1.

### Outcome of Experiments

We observed that in the majority of our experiments, varying the coreset sizes
does not significantly change the performance profiles of individual
algorithms when comparing them against each other. Therefore, in the following
sections, we focus on a cross-section of the experiments where $m=200$ i.e.,
coreset sizes $T=200k$. For numerical results including variances of all the
experiments and tables containing distortions, costs and running times, we
refer to Appendix C, Appendix D and Appendix E in the appendix.

In Figure 2, we summarized the distortions of the experiments with coreset
sizes $T=200k$. All five algorithms are matched on the Tower dataset. The
worst distortions across the algorithms are close to 1, and performance
between the algorithms is negligible. The performance difference between
sampling-based and movement-based methods become more pronounced as the number
of dimensions increase. On Covertype with its 54 features, Ray Maker performs
the worst followed by BICO and Group Sampling while Sensitivity Sampling and
StreamKM++ perform the best. Differences in performance are more noticeable on
Census, Caltech, and NYTimes where methods based on importance sampling
perform much better. Sensitivity Sampling and Group Sampling perform the best,
StreamKM++ come in second while BICO and Ray Maker perform the worst across
these data sets. On the Benchmark, Ray Maker is the worst while Sensitivity
Sampling and Group Sampling are the best. StreamKM++ performs also very well
compared to BICO.

### Interpretation of Experimental Results

Optimization versus Compression: While all five algorithms are equally matched
when optimizing on the candidate coresets, coreset quality performance differ
significantly (see Figure 2). For all data sets, the obtained costs differed
insignificantly for all values of $k$, (see Appendix D and Figure 6 in the
appendix), irrespective of the coreset algorithm used, while distortions
varied strongly, depending on the coreset algorithm.

Nevertheless, the cost drop with increasing values of $k$ is a predictor for
the quality of certain coresets. It is not uncommon for the $k$-means cost of
real-world data sets to drop significantly for larger values of $k$. Figure 3
illustrates this behavior for several real-world data sets. The more the curve
bends, the less of a difference there is between computing a coreset and a
clustering with low cost. For data sets with an L-shaped cost curve, a coreset
algorithm adding more centers to the coreset will seem to be performing well
when evaluating it based on the outcome of the optimization. Tower is a good
example of a data set where optimization is very close to compression. Its
cost curve bends the most which indicates that adding more centers help reduce
the cost. One of the strengths of the benchmark is that there is no way of
reducing the cost without capturing the right subclusters within a benchmark
instance. This means that the cost does not decrease markedly beyond a certain
value of $k$ even if more centers are added, see Figure 5 in the appendix.

For BICO, Ray Maker, and StreamKM++, there is a correlation between the
steepness of the cost curve for a data set and the distortion of the generated
coreset. On data sets where the curve is less steep, we observed higher
distortions. The effect is more pronounced for BICO and Ray Maker than for
StreamKM++. Importance sampling approaches (Group Sampling and Sensitivity
Sampling) seem to be free from this behavior as they consistently generate
high quality coresets irrespective of the shape of cost curve.

Figure 3: Depicts how clustering costs of five real-world data sets decrease
as the number of centers increase. Plotting the cost curve allows us to study
whether we can observe a difference between coreset construction and
optimization in a data set when evaluating a coreset based on cost.

Movement-based versus Sampling-based Approaches: In general, movement-based
constructions perform the worst in terms of coreset quality. We observed that
BICO and Ray Maker have the highest distortions across all data sets including
on the benchmark instances. Among the sampling-based algorithms, Sensitive
Sampling performs well with Group Sampling generally being competitive. This
runs contrary to theory where Group Sampling has the better (currently known)
theoretical bounds. StreamKM++ is an interesting case. Like the movement-based
methods, its distortion increases with the dimension. Nevertheless, it
generally performs significantly better than BICO and Ray Maker. This can be
attributed to the fact that the coreset produced by StreamKM++ consists
entirely of $k$-means++ centers weighted by the number of points of a minimal
cost assignment. This is similar to movement-based algorithms such as BICO.
Nevertheless, it also retains some of the performance from pure importance
schemes.

In practice as well as in theory, the distortion of movement-based algorithms
are affected by the dimension. By comparison, sampling-based algorithms are
affected very little. Theoretically, there should not exist a difference, as
the sampling bounds are independent of the dimension. What little effect can
be observed is likely due to PCA making it easier to find low cost solutions
that form the backbone of all coreset constructions. StreamKM++ is an
interesting case, as it is still affected by the dimension, though less than
the other movement based methods.

A notable exception is the benchmark. Here, sensitivity sampling generally
found the lowest cost clustering, with BICO finding the second lowest cost
clustering (see LABEL:tab:real-cost-mean-std-benchmark in the appendix). This
happens _despite_ BICO generally having a worse distortion than for example
Group Sampling or StreamKM++ (see LABEL:tab:distortions-mean-std-benchmark in
the appendix).

Impact of PCA: On almost all our data sets, the performance improves when
input data is preprocessed with PCA, especially for the movement-based
algorithms. Empirically, the more noise is removed (i.e., small $k$ value),
the lower the distortion. Notice that $k$ is the number of principal
components that the input data is projected on to. The rest of the low
variance components are treated as noise and removed. Method utilizing
sampling (Group Sampling, Sensitivity Sampling and StreamKM++) are less
effected by the preprocessing step. On Covertype, PCA does not change the
distortions by much because almost all the variance in the data is explained
by the first five principal components (see Figure 4). On Caltech and NYTimes,
the quality of the coresets by BICO and Ray Maker improves greatly because the
noise removal is more aggressive. Even if the quality is much better for
movement-based coreset constructions due to PCA, importance sampling methods
are still superior when it comes to the quality of the compression.
Summarizing, all methods benefit from PCA, and in case of movement-based
constructions, we consider PCA a necessary preprocessing step. For the
sampling-based methods, the computational expense of using PCA in
preprocessing does not seem justify the comparatively meager gains in coreset
distortion.

##  5 Conclusion

In this work, we studied how to assess the quality of $k$-means coresets
computed by state-of-the-art algorithms. Previous work generally measured the
quality of optimization algorithms run on the coreset, which we empirically
observed to be a poor indicator of coreset quality. For real-world data sets,
we sampled candidate clusterings and evaluated the worst case distortion on
them. Complementing this, we also proposed a benchmark framework which
generates hard instances for known $k$-means coreset algorithms. Our
experiments indicate a general advantage for algorithms based on importance
sampling over movement-based methods. Despite movement-based methods running
on very efficient code, it is necessary to complement them with rather
expensive dimension reduction methods, rendering what efficiency they might
have over importance sampling somewhat moot.

Two results bear further investigation. First, the currently known provable
coreset sizes for Sensitivity Sampling are worse than those provable via Group
Sampling. Empirically, we observed the opposite: While Group Sampling is
competitive, Sensitivity Sampling always outperforms it. Since Group Sampling
requires somewhat cumbersome computational overhead, practical applications
should prefer Sensitivity Sampling. In light of these results, a theoretical
analysis for Sensitivity Sampling matching the performance of Group Sampling
would be welcome.

The second point of interest focuses on the performance of StreamKM++. The
distortion of this algorithm is significantly better than what one would
expect from its theoretical analysis. Empirically, StreamKM++ is notably
better than the other movement-based constructions across all data sets, and
especially on high dimensional data. While it is not competitive to the pure
importance sampling algorithms, there are several reasons for investigating it
further. It essentially only requires running $k$-means++ for additional
iterations, which is already a nearly ubiquitous algorithm for the $k$-means
problem. Although the other sampling-based coreset algorithms can also be
readily implemented, doing so might be cumbersome. In particular, the
theoretically (but not empirically) best algorithm Group Sampling requires
extensive preprocessing steps. This begs the question whether there exist a
better theoretical analysis for StreamKM++.

In addition, StreamKM++ currently weighs each point by the number of points
assigned to it. It may also be possible to improve the performance of the
algorithm in both theory and practice by using a different weighting scheme.
We leave this as an open problem for future research.

## References

  * [1] Marcel R. Ackermann, Marcus Märtens, Christoph Raupach, Kamil Swierkot, Christiane Lammersen, and Christian Sohler.  Streamkm++: A clustering algorithm for data streams.  ACM Journal of Experimental Algorithmics, 17(1), 2012.  URL: http://doi.acm.org/10.1145/2133803.2184450, doi:10.1145/2133803.2184450.
  * [2] Pankaj K. Agarwal, Sariel Har-Peled, and Kasturi R. Varadarajan.  Geometric approximation via coresets.  In Combinatorial and computational geometry, MSRI, pages 1–30. University Press, 2005.
  * [3] David Arthur and Sergei Vassilvitskii.  k-means++: the advantages of careful seeding.  In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, pages 1027–1035, 2007.  URL: http://dl.acm.org/citation.cfm?id=1283383.1283494.
  * [4] Luca Becchetti, Marc Bury, Vincent Cohen-Addad, Fabrizio Grandoni, and Chris Schwiegelshohn.  Oblivious dimension reduction for _k_ -means: beyond subspaces and the johnson-lindenstrauss lemma.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 1039–1050, 2019.  doi:10.1145/3313276.3316318.
  * [5] Christos Boutsidis, Michael W. Mahoney, and Petros Drineas.  Unsupervised feature selection for the $k$-means clustering problem.  In Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009. Proceedings of a meeting held 7-10 December 2009, Vancouver, British Columbia, Canada., pages 153–161, 2009.  URL: http://papers.nips.cc/paper/3724-unsupervised-feature-selection-for-the-k-means-clustering-problem.
  * [6] Christos Boutsidis, Anastasios Zouzias, and Petros Drineas.  Random projections for $k$-means clustering.  In Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010. Proceedings of a meeting held 6-9 December 2010, Vancouver, British Columbia, Canada., pages 298–306, 2010.  URL: http://papers.nips.cc/paper/3901-random-projections-for-k-means-clustering.
  * [7] Christos Boutsidis, Anastasios Zouzias, Michael W. Mahoney, and Petros Drineas.  Randomized dimensionality reduction for k-means clustering.  IEEE Trans. Information Theory, 61(2):1045–1062, 2015.  doi:10.1109/TIT.2014.2375327.
  * [8] Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Xuan Wu.  Coresets for clustering in excluded-minor graphs and beyond.  In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 \- 13, 2021, pages 2679–2696. SIAM, 2021.  doi:10.1137/1.9781611976465.159.
  * [9] Timothy M. Chan.  Dynamic coresets.  Discret. Comput. Geom., 42(3):469–488, 2009.  doi:10.1007/s00454-009-9165-3.
  * [10] Ke Chen.  On coresets for k-median and k-means clustering in metric and Euclidean spaces and their applications.  SIAM J. Comput., 39(3):923–947, 2009.
  * [11] Yeshwanth Cherapanamjeri and Jelani Nelson.  Terminal embeddings in sublinear time.  In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 1209–1216. IEEE, 2021.  doi:10.1109/FOCS52979.2021.00118.
  * [12] Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu.  Dimensionality reduction for k-means clustering and low rank approximation.  In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 163–172, 2015.
  * [13] Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, and Chris Schwiegelshohn.  Towards optimal lower bounds for k-median and k-means coresets.  In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 \- 24, 2022, pages 1038–1051. ACM, 2022.  doi:10.1145/3519935.3519946.
  * [14] Vincent Cohen-Addad and Karthik C. S.  Inapproximability of clustering in lp metrics.  In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 519–539. IEEE Computer Society, 2019.  doi:10.1109/FOCS.2019.00040.
  * [15] Vincent Cohen-Addad, Karthik C. S., and Euiwoong Lee.  On approximability of clustering problems without candidate centers.  In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 \- 13, 2021, pages 2635–2648. SIAM, 2021.  doi:10.1137/1.9781611976465.156.
  * [16] Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn.  Improved coresets and sublinear algorithms for power means in euclidean spaces.  In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 21085–21098, 2021.  URL: https://proceedings.neurips.cc/paper/2021/hash/b035d6563a2adac9f822940c145263ce-Abstract.html.
  * [17] Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn.  A new coreset framework for clustering.  In Samir Khuller and Virginia Vassilevska Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 169–182. ACM, 2021.
  * [18] Vincent Cohen-Addad and Chris Schwiegelshohn.  On the local structure of stable clustering instances.  In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 49–60, 2017\.  doi:10.1109/FOCS.2017.14.
  * [19] Petros Drineas, Alan M. Frieze, Ravi Kannan, Santosh Vempala, and V. Vinay.  Clustering large graphs via the singular value decomposition.  Machine Learning, 56(1-3):9–33, 2004.  doi:10.1023/B:MACH.0000033113.59016.96.
  * [20] Michael Elkin, Arnold Filtser, and Ofer Neiman.  Terminal embeddings.  Theor. Comput. Sci., 697:1–36, 2017.  doi:10.1016/j.tcs.2017.06.021.
  * [21] Dan Feldman and Michael Langberg.  A unified framework for approximating and clustering data.  In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 569–578, 2011\.
  * [22] Dan Feldman, Melanie Schmidt, and Christian Sohler.  Turning big data into tiny data: Constant-size coresets for k-means, pca, and projective clustering.  SIAM J. Comput., 49(3):601–657, 2020.  doi:10.1137/18M1209854.
  * [23] Zhili Feng, Praneeth Kacham, and David P. Woodruff.  Dimensionality reduction for the sum-of-distances metric.  In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 3220–3229. PMLR, 2021.  URL: http://proceedings.mlr.press/v139/feng21a.html.
  * [24] Hendrik Fichtenberger, Marc Gillé, Melanie Schmidt, Chris Schwiegelshohn, and Christian Sohler.  BICO: BIRCH meets coresets for k-means clustering.  In Algorithms - ESA 2013 - 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings, pages 481–492, 2013\.
  * [25] Gereon Frahling and Christian Sohler.  Coresets in dynamic geometric data streams.  In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pages 209–217, 2005.
  * [26] Panos Giannopoulos, Christian Knauer, Magnus Wahlström, and Daniel Werner.  Hardness of discrepancy computation and $\epsilon$-net verification in high dimension.  J. Complex., 28(2):162–176, 2012.  doi:10.1016/j.jco.2011.09.001.
  * [27] Sariel Har-Peled and Akash Kushal.  Smaller coresets for k-median and k-means clustering.  Discret. Comput. Geom., 37(1):3–19, 2007.  doi:10.1007/s00454-006-1271-x.
  * [28] Sariel Har-Peled and Soham Mazumdar.  On coresets for k-means and k-median clustering.  In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pages 291–300, 2004.
  * [29] Lingxiao Huang, Shaofeng H.-C. Jiang, Jian Li, and Xuan Wu.  Epsilon-coresets for clustering (with outliers) in doubling metrics.  In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 814–825, 2018\.  doi:10.1109/FOCS.2018.00082.
  * [30] Lingxiao Huang, Shaofeng H.-C. Jiang, and Nisheeth K. Vishnoi.  Coresets for clustering with fairness constraints.  In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 7587–7598, 2019.  URL: https://proceedings.neurips.cc/paper/2019/hash/810dfbbebb17302018ae903e9cb7a483-Abstract.html.
  * [31] Lingxiao Huang and Nisheeth K. Vishnoi.  Coresets for clustering in euclidean spaces: importance sampling is nearly optimal.  In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 1416–1429. ACM, 2020.  doi:10.1145/3357713.3384296.
  * [32] Piotr Indyk, Sepideh Mahabadi, Shayan Oveis Gharan, and Alireza Rezaei.  Composable core-sets for determinant maximization problems via spectral spanners.  In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1675–1694. SIAM, 2020.  doi:10.1137/1.9781611975994.103.
  * [33] Jan-Philipp W. Kappmeier, Daniel R. Schmidt, and Melanie Schmidt.  Solving k-means on high-dimensional big data.  In Experimental Algorithms - 14th International Symposium, SEA 2015, Paris, France, June 29 - July 1, 2015, Proceedings, pages 259–270, 2015\.  doi:10.1007/978-3-319-20086-6\\_20.
  * [34] Amit Kumar and Ravindran Kannan.  Clustering with spectral norm and the k-means algorithm.  In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 299–308, 2010.  URL: http://dx.doi.org/10.1109/FOCS.2010.35, doi:10.1109/FOCS.2010.35.
  * [35] Michael Langberg and Leonard J. Schulman.  Universal $\varepsilon$-approximators for integrals.  In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 598–607, 2010.  URL: http://dx.doi.org/10.1137/1.9781611973075.50, doi:10.1137/1.9781611973075.50.
  * [36] Alaa Maalouf, Ibrahim Jubran, and Dan Feldman.  Fast and accurate least-mean-squares solvers.  In Advances in Neural Information Processing Systems, pages 8307–8318, 2019.
  * [37] Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn.  Nonlinear dimension reduction via outer bi-lipschitz extensions.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 1088–1101, 2018.  URL: http://doi.acm.org/10.1145/3188745.3188828, doi:10.1145/3188745.3188828.
  * [38] Tung Mai, Cameron Musco, and Anup Rao.  Coresets for classification - simplified and strengthened.  In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 11643–11654, 2021.  URL: https://proceedings.neurips.cc/paper/2021/hash/6098ed616e715171f0dabad60a8e5197-Abstract.html.
  * [39] Konstantin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn.  Performance of johnson-lindenstrauss transform for _k_ -means and _k_ -medians clustering.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 1027–1038, 2019.  doi:10.1145/3313276.3316350.
  * [40] Marina Meila.  Comparing clusterings: an axiomatic view.  In Luc De Raedt and Stefan Wrobel, editors, Machine Learning, Proceedings of the Twenty-Second International Conference (ICML 2005), Bonn, Germany, August 7-11, 2005, volume 119 of ACM International Conference Proceeding Series, pages 577–584. ACM, 2005.  doi:10.1145/1102351.1102424.
  * [41] Marina Meila.  The uniqueness of a good optimum for k-means.  In William W. Cohen and Andrew W. Moore, editors, Machine Learning, Proceedings of the Twenty-Third International Conference (ICML 2006), Pittsburgh, Pennsylvania, USA, June 25-29, 2006, volume 148 of ACM International Conference Proceeding Series, pages 625–632. ACM, 2006\.  doi:10.1145/1143844.1143923.
  * [42] Alexander Munteanu and Chris Schwiegelshohn.  Coresets-methods and history: A theoreticians design pattern for approximation and streaming algorithms.  Künstliche Intell., 32(1):37–53, 2018.  doi:10.1007/s13218-017-0519-3.
  * [43] Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, and David P. Woodruff.  On coresets for logistic regression.  In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 6562–6571, 2018.  URL: https://proceedings.neurips.cc/paper/2018/hash/63bfd6e8f26d1d3537f4c5038264ef36-Abstract.html.
  * [44] Shyam Narayanan and Jelani Nelson.  Optimal terminal dimensionality reduction in euclidean space.  In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 1064–1069. ACM, 2019.  doi:10.1145/3313276.3316307.
  * [45] Melanie Schmidt, Chris Schwiegelshohn, and Christian Sohler.  Fair coresets and streaming algorithms for fair k-means.  In Approximation and Online Algorithms - 17th International Workshop, WAOA 2019, Munich, Germany, September 12-13, 2019, Revised Selected Papers, pages 232–251, 2019.  doi:10.1007/978-3-030-39479-0\\_16.
  * [46] Christian Sohler and David P. Woodruff.  Strong coresets for k-median and subspace approximation: Goodbye dimension.  In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 802–813, 2018\.  doi:10.1109/FOCS.2018.00081.
  * [47] Suresh Venkatasubramanian and Qiushi Wang.  The johnson-lindenstrauss transform: An empirical study.  In Matthias Müller-Hannemann and Renato Fonseca F. Werneck, editors, Proceedings of the Thirteenth Workshop on Algorithm Engineering and Experiments, ALENEX 2011, Holiday Inn San Francisco Golden Gateway, San Francisco, California, USA, January 22, 2011, pages 164–173. SIAM, 2011.
  * [48] Dennis Wei.  A constant-factor bi-criteria approximation guarantee for k-means++.  In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett, editors, Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 604–612, 2016.
  * [49] Tian Zhang, Raghu Ramakrishnan, and Miron Livny.  BIRCH: A new data clustering algorithm and its applications.  Data Min. Knowl. Discov., 1(2):141–182, 1997.  URL: http://dx.doi.org/10.1023/A:1009783824328, doi:10.1023/A:1009783824328.

##  Appendix A Properties of the Benchmark

######  Fact 1.

For $a\neq a^{\prime}$, we have
$d(\mathcal{C}^{a},\mathcal{C}^{a^{\prime}})=1-1/k$.

######  Proof A.1.

Consider an arbitrary vector $v_{i}^{\ell}$. By construction, the positive
entries of $v_{i}^{\ell}$ range from $k^{\ell-1}\cdot i+1$ to
$k^{\ell-1}\cdot(i+1)$. Similarly, the positive entries for the vector
$v_{j}^{\ell-1}$ range from range from $k^{\ell-2}\cdot j+1$ to
$k^{\ell-2}\cdot(j+1)$. Therefore, concatenating $v_{j}^{\ell-1}$ $k$ times
into a vector $v^{\prime}$, $v^{\prime}$ and $v_{i}^{\ell}$ can share at most
one positive coordinate. Inductively, the same holds true for any
concatenation of vectors $v_{j}^{\ell-h}$. Thus, the two clusters induced by
the columns formed by concatenating the vectors $v$ can share only a $1/k$
fraction of the points. Since each cluster consists of exactly $k^{\alpha}/k$
= $k^{\alpha-1}$ points, the confusion matrix $M$ only has entries
$\frac{n}{k^{2}}$ and for any permutation $\pi$, we have
$d(\mathcal{C}^{a},\mathcal{C}^{a^{\prime}})=1-1/k$.

######  Fact 2.

For any $C_{j}^{a}$, we have
$\text{cost}_{C_{j}^{a}}(\\{\mu(C_{j}^{a})\\})=(\alpha-1)\cdot
k^{\alpha-2}\cdot(k-1)$.

######  Proof A.2.

Without loss of generality, we consider $C_{1}^{0}$; the proof is analogous
for the other choices of $j$ and $a$. We first note that for any point
$A_{i}\in C_{1}^{0}$, the coordinates $A_{i,\ell}$ are identical for $\ell<k$.
Furthermore for the column $\ell\geq k$, we have by construction
$\sum_{A_{i}\in
C_{j}}A_{i,\ell}=k^{\alpha-1}\cdot\frac{k-1}{k}+(k^{\alpha}-k^{\alpha-1})\frac{1}{k}=k^{\alpha-1}\cdot(\frac{k-1}{k}-(k-1)\frac{1}{k})=0.$
Therefore, the mean of $C_{1}^{0}$ satisfies
$\mu(C_{1}^{0})_{\ell}=\begin{cases}A_{i,\ell}&\text{if }\ell<k\\\
0&\text{else.}\end{cases}$. Thus, the cost is precisely $(\alpha-1)\cdot
k^{\alpha-1}\cdot\left(\left(\frac{k-1}{k}\right)^{2}+\left(\frac{1}{k}\right)^{2}\right)=(\alpha-1)\cdot
k^{\alpha-2}\cdot(k-1)$.

Finally, we show that the means for the clustering $\mathcal{C}^{a}$ also
induce $\mathcal{C}^{a}$.

######  Fact 3.

For a clustering $\mathcal{C}^{a}$, let $\mu(C_{j}^{a})$ denote the mean of
cluster $C_{j}^{a}$. Then every point is assigned to its closest center.
Moreover, every point $A_{i}$ of $C_{j}^{a}$ has equal distance to any center
$\mu(C_{h}^{a})$ with $h\neq j$.

######  Proof A.3.

Again, we assume without loss of generality $a=0$. Let $A_{i}$ be an arbitrary
point of cluster $C_{h}^{a}$ and consider the mean
$\mu(C_{j}^{a})_{\ell}=\begin{cases}A_{i,\ell}&\text{if }\ell<k\\\
0&\text{else.}\end{cases}$ of cluster $C_{j}^{a}$. By definition, the positive
coordinates of $A_{i}$ are not equal to the positive coordinates of
$\mu(C_{j}^{a})$. The only difference in coordinates between the means of
$\mu(C_{j}^{a})$ and $\mu(C_{h}^{a})$ are the first $k$ coordinates, as the
rest are $0$. But here the coordinates of $\mu(C_{h}^{a})$ and $A_{i}$ are
identical, hence $\mu(C_{j}^{a})$ cannot be closer to $A_{i}$.

To prove that the distances between $A_{i}$ and any $\mu(C_{h}^{a})$ with
$h\neq j$ are equal, again consider that any difference can only exist among
the first $k$ coordinates. Here, we have $\mu(C_{h}^{a})_{h}=\frac{k-1}{k}$,
and the remaining columns are $-\frac{1}{k}$. Since $A_{i,h}=-\frac{1}{k}$ for
any $h\neq j$, the claim follows.

##  Appendix B Hardness of Weak Coreset Evaluation

Here, we show that it is in general co-NP hard to evaluate whether two point
sets $A$ and $B$ are weak coresets of each other. A weak coreset only requires
that a $(1+\varepsilon)$ approximation for one point set is a
$(1+O(\varepsilon))$ for the other.

######  Proposition B.1.

Given two point sets $A$ and $B$ in $\mathbb{R}^{d}$ and a sufficiently small
(constant) $\varepsilon>0$, it is co-NP hard to decide whether $A$ is a weak
coreset of $B$.

######  Proof B.2.

First, we recall that for some $\varepsilon_{0}$ and candidate clustering cost
$V$, it is NP-hard to decide whether there exists a clustering $C$ with cost
in $\text{cost}_{A}(C)\leq V$ and
$\text{cost}_{B}(C)\geq(1+\varepsilon_{0})\cdot V$. Conversely, it is co-NP-
hard to decide whether there exists no set of centers $C$ such that
$\text{cost}_{A}(C)\leq V$ and $\text{cost}_{B}(C)\geq(1+\varepsilon_{0})\cdot
V$.

We remark that the possible values for $\varepsilon_{0}$ are determined by the
current APX-hardness results. Assuming NP$\neq$P, $\varepsilon_{0}\approx
1.07$ and assuming UCG, $\varepsilon_{0}\approx 1.17$ [15, 14] for $k$-means
in Euclidean spaces.

#### Further Extensions

On the benchmark we considered here, both Sensitivity Sampling, as well as
Group Sampling are similar to uniform sampling and, indeed, uniform sampling
could be used to construct a good coreset. We can eliminate uniform sampling
as a viable algorithm for this instance by combining multiple benchmarks
$B_{1},\ldots B_{t}$ with $\sum_{i=1}^{t}k_{i}=k$. Each benchmark then has
size $\sum_{i=1}^{t}k_{i}^{\alpha}$. We then add an additive offset to the
coordinates of each benchmark such that they do not interfere. In this case,
uniform sampling does not work if the values of the $k_{i}$ are different
enough. Since it is well known that uniform sampling is not a viable coreset
algorithm in both theory and practice, we only used the basic benchmark for
our evaluations.

##  Appendix C Distortions

The tables (LABEL:tab:distortions-mean-std-benchmark, LABEL:tab:distortions-
mean-std-caltech, LABEL:tab:distortions-mean-std-caltech-pca,
LABEL:tab:distortions-mean-std-census, LABEL:tab:distortions-mean-std-census-
pca, LABEL:tab:distortions-mean-std-covertype, LABEL:tab:distortions-mean-std-
covertype-pca, LABEL:tab:distortions-mean-std-nytimes, LABEL:tab:distortions-
mean-std-nytimes-pca, LABEL:tab:distortions-mean-std-tower) show the
distortions of the 5 evaluated algorithms on the different data sets. We vary
the coreset size $T$ for different $k$ values using the formula: $T=mk$ where
$m=\\{50,100,200,500\\}$. The running time for StreamKM++ with coreset size
$T=500k$ exceeds the allocated time budget of 32 hours on almost all data
sets. For this reason, the distortions for StreamKM++ with $m=500$ are not
present in the tables.

Table 3: Distortions of the evaluated algorithms on the Benchmark data set.
Each cell specify the mean distortion along with the standard deviation in
parenthesis of 10 repetitions of the experiment. Distortions on the Caltech
data set
---
$k$ |  $m$ | BICO |  Group Sampling |  Ray Maker |  Sensitivity Sampling | StreamKM++
10 | 50 | 3.40 (0.440) | 1.02 (0.010) | 5.05 (0.157) | 1.02 (0.005) | 1.07 (0.005)
| 100 | 3.24 (0.729) | 1.01 (0.004) | 3.84 (0.081) | 1.01 (0.003) | 1.05 (0.004)
| 200 | 2.90 (0.153) | 1.01 (0.002) | 3.48 (0.052) | 1.01 (0.002) | 1.04 (0.002)
| 500 | 2.62 (0.095) | 1.01 (0.001) | 3.40 (0.058) | 1.00 (0.001) |
20 | 50 | 3.22 (0.160) | 1.04 (0.004) | 5.52 (0.266) | 1.02 (0.003) | 1.08 (0.006)
| 100 | 3.09 (0.122) | 1.02 (0.004) | 4.31 (0.130) | 1.01 (0.002) | 1.08 (0.003)
| 200 | 2.88 (0.078) | 1.01 (0.002) | 3.93 (0.120) | 1.01 (0.001) | 1.11 (0.002)
| 500 | 2.36 (0.051) | 1.01 (0.001) | 3.81 (0.116) | 1.01 (0.001) |
30 | 50 | 2.81 (0.244) | 1.03 (0.006) | 6.43 (0.470) | 1.02 (0.002) | 1.13 (0.004)
| 100 | 2.58 (0.105) | 1.02 (0.003) | 4.65 (0.256) | 1.02 (0.002) | 1.13 (0.004)
| 200 | 2.38 (0.098) | 1.01 (0.002) | 4.12 (0.234) | 1.01 (0.002) | 1.10 (0.002)
| 500 | 2.01 (0.065) | 1.01 (0.001) | 4.00 (0.138) | 1.01 (0.001) |
40 | 50 | 3.16 (0.500) | 1.03 (0.004) | 5.62 (0.287) | 1.02 (0.004) | 1.10 (0.004)
| 100 | 2.78 (0.258) | 1.02 (0.001) | 4.42 (0.200) | 1.02 (0.002) | 1.14 (0.003)
| 200 | 2.79 (0.217) | 1.02 (0.001) | 3.82 (0.111) | 1.01 (0.001) | 1.17 (0.004)
| 500 | 2.57 (0.113) | 1.01 (0.001) | 3.86 (0.122) | 1.01 (0.001) |
Table 4: Distortions of the evaluated algorithms on the Caltech data set. Each
cell specify the mean distortion along with the standard deviation in
parenthesis of 10 repetitions of the experiment. Distortions on the Caltech
data set
---
$k$ |  $m$ | BICO |  Group Sampling |  Ray Maker |  Sensitivity Sampling | StreamKM++
10 | 50 | 5.12 (0.307) | 1.07 (0.009) | 7.05 (0.250) | 1.05 (0.013) | 1.16 (0.008)
| 100 | 4.48 (0.284) | 1.04 (0.006) | 5.46 (0.254) | 1.03 (0.008) | 1.13 (0.005)
| 200 | 4.08 (0.319) | 1.02 (0.004) | 5.00 (0.196) | 1.01 (0.005) | 1.10 (0.005)
| 500 | 3.41 (0.215) | 1.01 (0.003) | 4.75 (0.188) | 1.00 (0.003) |
20 | 50 | 6.35 (1.173) | 1.06 (0.008) | 6.92 (0.209) | 1.05 (0.007) | 1.18 (0.008)
| 100 | 4.65 (0.283) | 1.04 (0.005) | 5.29 (0.146) | 1.03 (0.005) | 1.14 (0.005)
| 200 | 4.19 (0.384) | 1.02 (0.002) | 4.80 (0.112) | 1.01 (0.004) | 1.12 (0.004)
| 500 | 3.50 (0.404) | 1.01 (0.002) | 4.61 (0.096) | 1.00 (0.001) |
30 | 50 | 6.01 (0.335) | 1.06 (0.005) | 6.79 (0.149) | 1.04 (0.004) | 1.19 (0.005)
| 100 | 5.10 (0.628) | 1.04 (0.005) | 5.30 (0.123) | 1.02 (0.005) | 1.15 (0.002)
| 200 | 4.29 (0.659) | 1.02 (0.003) | 4.70 (0.075) | 1.01 (0.003) | 1.13 (0.002)
| 500 | 3.09 (0.138) | 1.01 (0.002) | 4.62 (0.090) | 1.00 (0.002) |
40 | 50 | 6.24 (0.524) | 1.07 (0.004) | 6.85 (0.145) | 1.05 (0.004) | 1.20 (0.004)
| 100 | 5.23 (0.874) | 1.04 (0.003) | 5.22 (0.092) | 1.02 (0.002) | 1.16 (0.003)
| 200 | 4.50 (1.085) | 1.02 (0.002) | 4.72 (0.086) | 1.01 (0.001) | 1.13 (0.002)
| 500 | 3.38 (0.398) | 1.01 (0.001) | 4.55 (0.094) | 1.00 (0.001) |
50 | 50 | 7.50 (1.013) | 1.07 (0.004) | 6.80 (0.092) | 1.05 (0.004) | 1.20 (0.006)
| 100 | 5.21 (0.968) | 1.04 (0.003) | 5.18 (0.084) | 1.03 (0.002) | 1.16 (0.005)
| 200 | 4.21 (0.296) | 1.02 (0.002) | 4.69 (0.065) | 1.01 (0.003) | 1.13 (0.002)
| 500 | 3.36 (0.429) | 1.01 (0.001) | 4.52 (0.058) | 1.00 (0.001) |
Table 5: Distortions of the evaluated algorithms on the Caltech data set (with
PCA preprocessing). Each cell specify the mean distortion along with the
standard deviation in parenthesis of 10 repetitions of the experiment.
Distortions on the Caltech data set (with PCA preprocessing)
---
$k$ |  $m$ | BICO |  Group Sampling |  Ray Maker |  Sensitivity Sampling | StreamKM++
10 | 50 | 1.21 (0.009) | 1.03 (0.004) | 1.25 (0.005) | 1.02 (0.007) | 1.04 (0.005)
| 100 | 1.19 (0.006) | 1.02 (0.006) | 1.21 (0.006) | 1.01 (0.004) | 1.03 (0.004)
| 200 | 1.16 (0.003) | 1.01 (0.002) | 1.19 (0.003) | 1.01 (0.003) | 1.02 (0.002)
| 500 | 1.13 (0.007) | 1.00 (0.002) | 1.19 (0.006) | 1.00 (0.001) |
20 | 50 | 1.54 (0.024) | 1.04 (0.006) | 1.63 (0.008) | 1.03 (0.006) | 1.07 (0.003)
| 100 | 1.48 (0.020) | 1.02 (0.002) | 1.54 (0.010) | 1.01 (0.004) | 1.06 (0.003)
| 200 | 1.41 (0.006) | 1.01 (0.002) | 1.50 (0.011) | 1.01 (0.003) | 1.04 (0.003)
| 500 | 1.35 (0.008) | 1.00 (0.001) | 1.49 (0.008) | 1.00 (0.001) |
30 | 50 | 1.99 (0.032) | 1.05 (0.006) | 2.05 (0.020) | 1.03 (0.003) | 1.10 (0.004)
| 100 | 1.82 (0.099) | 1.03 (0.004) | 1.90 (0.014) | 1.02 (0.003) | 1.08 (0.002)
| 200 | 1.72 (0.046) | 1.01 (0.002) | 1.84 (0.009) | 1.01 (0.002) | 1.06 (0.002)
| 500 | 1.62 (0.037) | 1.01 (0.001) | 1.81 (0.011) | 1.00 (0.002) |
40 | 50 | 2.34 (0.112) | 1.05 (0.003) | 2.48 (0.020) | 1.04 (0.005) | 1.12 (0.004)
| 100 | 2.25 (0.066) | 1.03 (0.003) | 2.23 (0.011) | 1.02 (0.001) | 1.09 (0.003)
| 200 | 2.11 (0.072) | 1.02 (0.002) | 2.15 (0.012) | 1.01 (0.003) | 1.07 (0.002)
| 500 | 1.90 (0.070) | 1.01 (0.002) | 2.12 (0.011) | 1.00 (0.001) |
50 | 50 | 2.86 (0.214) | 1.06 (0.003) | 2.94 (0.026) | 1.04 (0.005) | 1.14 (0.005)
| 100 | 2.58 (0.124) | 1.03 (0.001) | 2.59 (0.019) | 1.02 (0.001) | 1.11 (0.002)
| 200 | 2.35 (0.139) | 1.02 (0.001) | 2.49 (0.021) | 1.01 (0.002) | 1.09 (0.002)
| 500 | 2.15 (0.075) | 1.01 (0.001) | 2.44 (0.015) | 1.00 (0.001) |
Table 6: Distortions of the evaluated algorithms on the Census data set. Each
cell specify the mean distortion along with the standard deviation in
parenthesis of 10 repetitions of the experiment. Distortions on the Census
data set
---
$k$ |  $m$ | BICO |  Group Sampling |  Ray Maker |  Sensitivity Sampling | StreamKM++
10 | 50 | 2.08 (0.106) | 1.08 (0.019) | 2.30 (0.162) | 1.03 (0.031) | 1.10 (0.012)
| 100 | 1.83 (0.124) | 1.04 (0.021) | 1.92 (0.094) | 1.03 (0.012) | 1.07 (0.006)
| 200 | 1.65 (0.056) | 1.02 (0.005) | 1.72 (0.050) | 1.02 (0.012) | 1.05 (0.005)
| 500 | 1.48 (0.053) | 1.02 (0.004) | 1.69 (0.029) | 1.02 (0.010) |
20 | 50 | 2.18 (0.164) | 1.07 (0.022) | 2.31 (0.078) | 1.03 (0.007) | 1.10 (0.008)
| 100 | 1.93 (0.080) | 1.04 (0.011) | 1.91 (0.048) | 1.02 (0.011) | 1.08 (0.005)
| 200 | 1.71 (0.031) | 1.03 (0.006) | 1.75 (0.027) | 1.01 (0.006) | 1.06 (0.004)
| 500 | 1.51 (0.048) | 1.02 (0.005) | 1.66 (0.019) | 1.01 (0.004) |
30 | 50 | 2.28 (0.177) | 1.07 (0.011) | 2.38 (0.077) | 1.03 (0.011) | 1.11 (0.007)
| 100 | 2.05 (0.096) | 1.04 (0.006) | 1.95 (0.040) | 1.02 (0.007) | 1.09 (0.004)
| 200 | 1.76 (0.055) | 1.03 (0.005) | 1.79 (0.034) | 1.01 (0.007) | 1.07 (0.003)
| 500 | 1.56 (0.016) | 1.01 (0.003) | 1.71 (0.038) | 1.01 (0.003) |
40 | 50 | 2.47 (0.101) | 1.08 (0.009) | 2.43 (0.069) | 1.02 (0.010) | 1.12 (0.006)
| 100 | 2.11 (0.104) | 1.04 (0.006) | 1.99 (0.034) | 1.01 (0.004) | 1.09 (0.003)
| 200 | 1.83 (0.038) | 1.02 (0.007) | 1.81 (0.026) | 1.01 (0.005) | 1.08 (0.002)
| 500 | 1.56 (0.039) | 1.01 (0.005) | 1.73 (0.026) | 1.01 (0.003) |
50 | 50 | 2.50 (0.138) | 1.07 (0.008) | 2.48 (0.054) | 1.02 (0.011) | 1.13 (0.004)
| 100 | 2.12 (0.109) | 1.04 (0.007) | 2.02 (0.055) | 1.01 (0.004) | 1.10 (0.003)
| 200 | 1.84 (0.059) | 1.03 (0.004) | 1.82 (0.022) | 1.01 (0.005) | 1.08 (0.004)
| 500 | 1.57 (0.019) | 1.02 (0.004) | 1.75 (0.022) | 1.01 (0.003) |
Table 7: Distortions of the evaluated algorithms on the Census data set (with
PCA preprocessing). Each cell specify the mean distortion along with the
standard deviation in parenthesis of 10 repetitions of the experiment.
Distortions on the Census data set (with PCA preprocessing)
---
$k$ |  $m$ | BICO |  Group Sampling |  Ray Maker |  Sensitivity Sampling | StreamKM++
10 | 50 | 1.34 (0.048) | 1.06 (0.018) | 1.35 (0.030) | 1.04 (0.021) | 1.03 (0.007)
| 100 | 1.24 (0.015) | 1.03 (0.007) | 1.25 (0.017) | 1.03 (0.016) | 1.02 (0.005)
| 200 | 1.19 (0.020) | 1.02 (0.009) | 1.19 (0.013) | 1.02 (0.018) | 1.01 (0.002)
| 500 | 1.11 (0.003) | 1.01 (0.005) | 1.18 (0.017) | 1.01 (0.003) |
20 | 50 | 1.84 (0.118) | 1.07 (0.018) | 1.78 (0.052) | 1.02 (0.012) | 1.07 (0.005)
| 100 | 1.57 (0.073) | 1.03 (0.010) | 1.56 (0.020) | 1.02 (0.008) | 1.05 (0.005)
| 200 | 1.44 (0.037) | 1.02 (0.007) | 1.44 (0.030) | 1.01 (0.008) | 1.03 (0.002)
| 500 | 1.30 (0.014) | 1.01 (0.005) | 1.39 (0.017) | 1.01 (0.005) |
30 | 50 | 2.13 (0.153) | 1.07 (0.010) | 2.10 (0.045) | 1.02 (0.011) | 1.10 (0.005)
| 100 | 1.81 (0.050) | 1.04 (0.009) | 1.79 (0.029) | 1.01 (0.006) | 1.07 (0.003)
| 200 | 1.63 (0.044) | 1.02 (0.006) | 1.65 (0.029) | 1.01 (0.005) | 1.06 (0.002)
| 500 | 1.47 (0.021) | 1.01 (0.004) | 1.58 (0.014) | 1.01 (0.004) |
40 | 50 | 2.37 (0.102) | 1.07 (0.007) | 2.31 (0.039) | 1.03 (0.008) | 1.11 (0.006)
| 100 | 2.01 (0.118) | 1.04 (0.007) | 1.90 (0.027) | 1.01 (0.004) | 1.09 (0.004)
| 200 | 1.76 (0.027) | 1.03 (0.005) | 1.75 (0.024) | 1.01 (0.002) | 1.07 (0.002)
| 500 | 1.52 (0.044) | 1.02 (0.003) | 1.67 (0.022) | 1.01 (0.003) |
50 | 50 | 2.45 (0.139) | 1.07 (0.008) | 2.46 (0.048) | 1.02 (0.012) | 1.13 (0.004)
| 100 | 2.14 (0.135) | 1.04 (0.007) | 1.99 (0.028) | 1.01 (0.004) | 1.10 (0.003)
| 200 | 1.87 (0.055) | 1.03 (0.005) | 1.82 (0.018) | 1.01 (0.004) | 1.08 (0.002)
| 500 | 1.56 (0.008) | 1.02 (0.004) | 1.73 (0.036) | 1.01 (0.004) |
Table 8: Distortions of the evaluated algorithms on the Covertype data set.
Each cell specify the mean distortion along with the standard deviation in
parenthesis of 10 repetitions of the experiment. Distortions on the Covertype
data set
---
$k$ |  $m$ | BICO |  Group Sampling |  Ray Maker |  Sensitivity Sampling | StreamKM++
10 | 50 | 1.25 (0.018) | 1.08 (0.022) | 1.31 (0.027) | 1.04 (0.025) | 1.05 (0.008)
| 100 | 1.17 (0.015) | 1.04 (0.016) | 1.22 (0.017) | 1.03 (0.014) | 1.02 (0.003)
| 200 | 1.11 (0.004) | 1.03 (0.012) | 1.18 (0.014) | 1.02 (0.008) | 1.02 (0.002)
| 500 | 1.05 (0.001) | 1.01 (0.004) | 1.16 (0.009) | 1.01 (0.006) |
20 | 50 | 1.27 (0.025) | 1.09 (0.022) | 1.35 (0.031) | 1.04 (0.008) | 1.05 (0.006)
| 100 | 1.18 (0.004) | 1.05 (0.016) | 1.24 (0.010) | 1.02 (0.006) | 1.03 (0.003)
| 200 | 1.11 (0.003) | 1.02 (0.008) | 1.21 (0.017) | 1.01 (0.007) | 1.01 (0.002)
| 500 | 1.04 (0.001) | 1.01 (0.004) | 1.19 (0.009) | 1.01 (0.006) |
30 | 50 | 1.29 (0.008) | 1.08 (0.017) | 1.37 (0.013) | 1.04 (0.013) | 1.05 (0.005)
| 100 | 1.17 (0.003) | 1.05 (0.007) | 1.26 (0.013) | 1.01 (0.007) | 1.03 (0.003)
| 200 | 1.10 (0.001) | 1.03 (0.009) | 1.21 (0.008) | 1.01 (0.005) | 1.01 (0.001)
| 500 | 1.04 (0.000) | 1.01 (0.003) | 1.20 (0.006) | 1.01 (0.003) |
40 | 50 | 1.28 (0.009) | 1.09 (0.014) | 1.39 (0.012) | 1.03 (0.013) | 1.05 (0.004)
| 100 | 1.18 (0.005) | 1.05 (0.011) | 1.26 (0.009) | 1.02 (0.007) | 1.03 (0.002)
| 200 | 1.09 (0.002) | 1.02 (0.003) | 1.22 (0.008) | 1.01 (0.005) | 1.01 (0.001)
| 500 | 1.03 (0.000) | 1.01 (0.002) | 1.21 (0.008) | 1.01 (0.003) |
50 | 50 | 1.28 (0.009) | 1.08 (0.007) | 1.38 (0.008) | 1.03 (0.010) | 1.05 (0.004)
| 100 | 1.15 (0.003) | 1.05 (0.005) | 1.27 (0.011) | 1.02 (0.005) | 1.02 (0.001)
| 200 | 1.07 (0.001) | 1.02 (0.004) | 1.23 (0.009) | 1.01 (0.002) | 1.01 (0.001)
| 500 | 1.03 (0.000) | 1.01 (0.004) | 1.23 (0.009) | 1.01 (0.004) |
Table 9: Distortions of the evaluated algorithms on the Covertype data set
(with PCA preprocessing). Each cell specify the mean distortion along with the
standard deviation in parenthesis of 10 repetitions of the experiment.
Distortions on the Covertype data set (with PCA preprocessing)
---
$k$ |  $m$ | BICO |  Group Sampling |  Ray Maker |  Sensitivity Sampling | StreamKM++
10 | 50 | 1.26 (0.024) | 1.09 (0.025) | 1.30 (0.019) | 1.04 (0.017) | 1.04 (0.008)
| 100 | 1.16 (0.010) | 1.05 (0.017) | 1.22 (0.015) | 1.03 (0.017) | 1.02 (0.003)
| 200 | 1.10 (0.003) | 1.03 (0.017) | 1.17 (0.014) | 1.02 (0.011) | 1.01 (0.002)
| 500 | 1.06 (0.001) | 1.01 (0.006) | 1.16 (0.008) | 1.01 (0.007) |
20 | 50 | 1.27 (0.018) | 1.10 (0.021) | 1.34 (0.021) | 1.04 (0.018) | 1.05 (0.004)
| 100 | 1.17 (0.005) | 1.05 (0.011) | 1.25 (0.013) | 1.02 (0.010) | 1.03 (0.002)
| 200 | 1.11 (0.003) | 1.02 (0.007) | 1.20 (0.012) | 1.02 (0.005) | 1.01 (0.002)
| 500 | 1.04 (0.001) | 1.01 (0.004) | 1.19 (0.011) | 1.01 (0.008) |
30 | 50 | 1.29 (0.010) | 1.09 (0.013) | 1.38 (0.013) | 1.04 (0.011) | 1.05 (0.003)
| 100 | 1.17 (0.004) | 1.05 (0.011) | 1.26 (0.009) | 1.01 (0.007) | 1.03 (0.003)
| 200 | 1.10 (0.002) | 1.03 (0.005) | 1.22 (0.011) | 1.01 (0.007) | 1.01 (0.002)
| 500 | 1.04 (0.000) | 1.01 (0.003) | 1.21 (0.010) | 1.01 (0.005) |
40 | 50 | 1.28 (0.006) | 1.09 (0.013) | 1.38 (0.019) | 1.04 (0.014) | 1.05 (0.005)
| 100 | 1.18 (0.003) | 1.05 (0.008) | 1.27 (0.016) | 1.02 (0.008) | 1.02 (0.002)
| 200 | 1.09 (0.001) | 1.02 (0.004) | 1.22 (0.010) | 1.01 (0.004) | 1.01 (0.002)
| 500 | 1.03 (0.000) | 1.01 (0.003) | 1.21 (0.009) | 1.01 (0.003) |
50 | 50 | 1.29 (0.017) | 1.09 (0.014) | 1.39 (0.009) | 1.03 (0.010) | 1.05 (0.003)
| 100 | 1.15 (0.003) | 1.05 (0.007) | 1.27 (0.009) | 1.02 (0.008) | 1.02 (0.001)
| 200 | 1.07 (0.001) | 1.02 (0.003) | 1.22 (0.005) | 1.01 (0.002) | 1.01 (0.001)
| 500 | 1.03 (0.000) | 1.01 (0.002) | 1.23 (0.006) | 1.01 (0.003) |
Table 10: Distortions of the evaluated algorithms on the NYTimes data set.
Each cell specify the mean distortion along with the standard deviation in
parenthesis of 10 repetitions of the experiment. Distortions on the NYTimes
data set
---
$k$ |  $m$ | BICO |  Group Sampling |  Ray Maker |  Sensitivity Sampling | StreamKM++
10 | 50 | 35.32 (8.376) | 1.08 (0.009) | 28.37 (2.761) | 1.05 (0.012) | 2.04 (0.244)
| 100 | 24.50 (5.355) | 1.06 (0.008) | 17.64 (0.561) | 1.03 (0.007) | 1.80 (0.069)
| 200 | 13.97 (2.143) | 1.04 (0.004) | 15.17 (0.512) | 1.02 (0.008) | 1.75 (0.110)
| 500 | 8.09 (1.241) | 1.03 (0.004) | 14.16 (1.031) | 1.01 (0.004) |
20 | 50 | 21.70 (3.965) | 1.09 (0.008) | 23.94 (1.466) | 1.05 (0.010) | 1.97 (0.083)
| 100 | 16.00 (3.906) | 1.05 (0.005) | 14.56 (0.846) | 1.03 (0.006) | 1.79 (0.046)
| 200 | 8.64 (1.429) | 1.04 (0.003) | 12.71 (0.786) | 1.02 (0.003) | 1.68 (0.025)
| 500 | 5.39 (0.441) | 1.02 (0.001) | 11.73 (0.551) | 1.01 (0.003) |
30 | 50 | 21.63 (3.611) | 1.09 (0.007) | 20.44 (0.862) | 1.05 (0.008) | 1.97 (0.106)
| 100 | 13.36 (3.778) | 1.05 (0.005) | 13.00 (0.763) | 1.03 (0.005) | 1.74 (0.035)
| 200 | 7.76 (0.884) | 1.03 (0.003) | 11.68 (0.754) | 1.01 (0.004) | 1.66 (0.028)
| 500 | 4.70 (0.418) | 1.02 (0.001) | 11.17 (0.682) | 1.01 (0.002) |
40 | 50 | 22.03 (7.691) | 1.08 (0.006) | 18.56 (0.955) | 1.05 (0.006) | 1.92 (0.045)
| 100 | 10.49 (1.801) | 1.05 (0.006) | 12.27 (0.688) | 1.03 (0.006) | 1.75 (0.057)
| 200 | 6.39 (0.339) | 1.03 (0.002) | 11.08 (0.461) | 1.01 (0.005) | 1.63 (0.024)
| 500 | 4.19 (0.151) | 1.02 (0.001) | 10.68 (0.736) | 1.01 (0.002) |
50 | 50 | 15.78 (3.123) | 1.09 (0.005) | 17.61 (0.940) | 1.05 (0.007) | 1.89 (0.053)
| 100 | 9.85 (2.053) | 1.05 (0.004) | 11.71 (0.292) | 1.03 (0.003) | 1.71 (0.036)
| 200 | 6.03 (0.505) | 1.03 (0.002) | 10.76 (0.454) | 1.01 (0.004) | 1.63 (0.020)
| 500 | 4.07 (0.182) | 1.02 (0.001) | 10.58 (1.080) | 1.00 (0.002) |
Table 11: Distortions of the evaluated algorithms on the NYTimes data set
(with PCA preprocessing). Each cell specify the mean distortion along with the
standard deviation in parenthesis of 10 repetitions of the experiment.
Distortions on the NYTimes data set (with PCA preprocessing)
---
$k$ |  $m$ | BICO |  Group Sampling |  Ray Maker |  Sensitivity Sampling | StreamKM++
10 | 50 | 1.02 (0.002) | 1.01 (0.002) | 1.02 (0.001) | 1.00 (0.002) | 1.01 (0.000)
| 100 | 1.01 (0.001) | 1.00 (0.001) | 1.01 (0.001) | 1.00 (0.002) | 1.00 (0.000)
| 200 | 1.01 (0.000) | 1.00 (0.001) | 1.01 (0.000) | 1.00 (0.001) | 1.00 (0.000)
| 500 | 1.01 (0.000) | 1.00 (0.001) | 1.01 (0.001) | 1.00 (0.001) |
20 | 50 | 1.03 (0.002) | 1.01 (0.001) | 1.03 (0.001) | 1.00 (0.002) | 1.01 (0.001)
| 100 | 1.03 (0.001) | 1.00 (0.001) | 1.03 (0.001) | 1.00 (0.000) | 1.01 (0.000)
| 200 | 1.02 (0.001) | 1.00 (0.001) | 1.02 (0.001) | 1.00 (0.001) | 1.01 (0.000)
| 500 | 1.01 (0.001) | 1.00 (0.000) | 1.02 (0.001) | 1.00 (0.000) |
30 | 50 | 1.04 (0.003) | 1.01 (0.001) | 1.04 (0.001) | 1.00 (0.002) | 1.02 (0.001)
| 100 | 1.04 (0.002) | 1.01 (0.001) | 1.03 (0.001) | 1.00 (0.001) | 1.01 (0.000)
| 200 | 1.03 (0.001) | 1.00 (0.001) | 1.03 (0.000) | 1.00 (0.001) | 1.01 (0.000)
| 500 | 1.02 (0.000) | 1.00 (0.000) | 1.03 (0.001) | 1.00 (0.001) |
40 | 50 | 1.06 (0.001) | 1.01 (0.001) | 1.05 (0.001) | 1.00 (0.001) | 1.02 (0.000)
| 100 | 1.05 (0.002) | 1.01 (0.001) | 1.05 (0.001) | 1.00 (0.001) | 1.02 (0.000)
| 200 | 1.04 (0.001) | 1.00 (0.001) | 1.04 (0.001) | 1.00 (0.001) | 1.01 (0.000)
| 500 | 1.03 (0.000) | 1.00 (0.000) | 1.05 (0.001) | 1.00 (0.000) |
50 | 50 | 1.07 (0.004) | 1.01 (0.001) | 1.06 (0.002) | 1.00 (0.001) | 1.03 (0.000)
| 100 | 1.06 (0.001) | 1.01 (0.001) | 1.05 (0.001) | 1.00 (0.001) | 1.02 (0.000)
| 200 | 1.04 (0.003) | 1.00 (0.001) | 1.05 (0.001) | 1.00 (0.001) | 1.02 (0.000)
| 500 | 1.03 (0.001) | 1.00 (0.000) | 1.06 (0.001) | 1.00 (0.000) |
Table 12: Distortions of the evaluated algorithms on the Tower data set. Each
cell specify the mean distortion along with the standard deviation in
parenthesis of 10 repetitions of the experiment. Distortions on the Tower data
set
---
$k$ |  $m$ | BICO |  Group Sampling |  Ray Maker |  Sensitivity Sampling | StreamKM++
20 | 50 | 1.18 (0.018) | 1.09 (0.025) | 1.44 (0.045) | 1.04 (0.025) | 1.04 (0.004)
| 100 | 1.11 (0.005) | 1.05 (0.016) | 1.16 (0.013) | 1.03 (0.007) | 1.03 (0.003)
| 200 | 1.06 (0.002) | 1.03 (0.007) | 1.06 (0.007) | 1.02 (0.009) | 1.02 (0.001)
| 500 | 1.03 (0.001) | 1.01 (0.006) | 1.03 (0.002) | 1.01 (0.005) |
40 | 50 | 1.20 (0.012) | 1.11 (0.014) | 1.48 (0.020) | 1.04 (0.019) | 1.05 (0.002)
| 100 | 1.11 (0.006) | 1.05 (0.013) | 1.15 (0.008) | 1.02 (0.010) | 1.03 (0.002)
| 200 | 1.07 (0.005) | 1.03 (0.007) | 1.05 (0.004) | 1.01 (0.006) | 1.02 (0.001)
| 500 | 1.02 (0.001) | 1.01 (0.003) | 1.03 (0.001) | 1.01 (0.003) |
60 | 50 | 1.20 (0.008) | 1.11 (0.011) | 1.49 (0.019) | 1.04 (0.009) | 1.05 (0.002)
| 100 | 1.10 (0.002) | 1.06 (0.007) | 1.13 (0.005) | 1.01 (0.006) | 1.03 (0.002)
| 200 | 1.06 (0.002) | 1.03 (0.007) | 1.05 (0.002) | 1.01 (0.004) | 1.02 (0.001)
| 500 | 1.02 (0.001) | 1.02 (0.005) | 1.03 (0.001) | 1.01 (0.003) |
80 | 50 | 1.18 (0.005) | 1.11 (0.010) | 1.47 (0.013) | 1.03 (0.012) | 1.05 (0.004)
| 100 | 1.10 (0.009) | 1.06 (0.008) | 1.13 (0.004) | 1.01 (0.005) | 1.03 (0.001)
| 200 | 1.05 (0.001) | 1.03 (0.003) | 1.05 (0.002) | 1.01 (0.004) | 1.02 (0.000)
| 500 | 1.02 (0.001) | 1.02 (0.003) | 1.02 (0.001) | 1.01 (0.004) |
100 | 50 | 1.19 (0.007) | 1.10 (0.009) | 1.45 (0.010) | 1.03 (0.008) | 1.05 (0.002)
| 100 | 1.10 (0.008) | 1.06 (0.007) | 1.12 (0.005) | 1.02 (0.007) | 1.03 (0.001)
| 200 | 1.04 (0.001) | 1.03 (0.005) | 1.05 (0.002) | 1.01 (0.003) | 1.02 (0.000)
| 500 | 1.01 (0.001) | 1.02 (0.003) | 1.03 (0.002) | 1.01 (0.003) |

##  Appendix D Costs

Table 13: Costs of the evaluated algorithms on the Benchmark data set. Each
cell specify the mean along with the standard deviation in parenthesis of 10
repetitions of the experiment. Costs on the Benchmark data set
---
$k$ |  $m$ | BICO |  Group Sampling |  Ray Maker |  Sensitivity Sampling | StreamKM++
10 | 50 |  4.8e+06 (2.3e+05) |  5.2e+06 (4.1e+05) |  5.0e+06 (2.9e+05) |  4.7e+06 (3.8e+05) |  5.3e+06 (0.0e+00)
| 100 |  4.6e+06 (1.7e+05) |  5.3e+06 (1.1e+05) |  4.9e+06 (2.8e+05) |  4.5e+06 (1.3e+05) |  5.3e+06 (0.0e+00)
| 200 |  4.7e+06 (3.1e+05) |  5.4e+06 (2.4e+05) |  5.1e+06 (3.6e+05) |  4.6e+06 (2.5e+05) |  5.3e+06 (0.0e+00)
| 500 |  4.6e+06 (1.0e+05) |  5.4e+06 (1.4e+05) |  5.1e+06 (2.1e+05) |  4.7e+06 (3.6e+05) |
20 | 50 |  1.4e+07 (8.8e+05) |  1.5e+07 (2.6e+05) |  1.3e+07 (6.2e+05) |  1.2e+07 (2.9e-09) |  1.6e+07 (2.9e+05)
| 100 |  1.3e+07 (9.8e+05) |  1.5e+07 (4.6e+05) |  1.4e+07 (5.9e+05) |  1.3e+07 (1.1e+06) |  1.6e+07 (1.7e+05)
| 200 |  1.2e+07 (2.2e+05) |  1.5e+07 (4.0e+05) |  1.3e+07 (3.5e+05) |  1.2e+07 (6.1e+05) |  1.6e+07 (1.0e+05)
| 500 |  1.3e+07 (6.2e+05) |  1.5e+07 (3.4e+05) |  1.3e+07 (3.2e+05) |  1.2e+07 (8.1e+05) |
30 | 50 |  2.7e+06 (2.6e+05) |  3.0e+06 (4.0e+04) |  2.5e+06 (6.3e+04) |  2.3e+06 (0.0e+00) |  3.2e+06 (3.1e+04)
| 100 |  2.8e+06 (9.5e+04) |  3.0e+06 (1.0e+05) |  2.4e+06 (1.3e+05) |  2.3e+06 (0.0e+00) |  3.1e+06 (3.8e+04)
| 200 |  2.6e+06 (2.1e+05) |  3.1e+06 (7.6e+04) |  2.6e+06 (8.6e+04) |  2.3e+06 (0.0e+00) |  3.1e+06 (5.0e+04)
| 500 |  2.6e+06 (8.4e+04) |  3.0e+06 (5.6e+04) |  2.5e+06 (1.2e+05) |  2.3e+06 (0.0e+00) |
40 | 50 |  9.2e+06 (6.6e+05) |  9.8e+06 (1.4e+05) |  9.1e+06 (2.6e+05) |  7.5e+06 (0.0e+00) |  1.0e+07 (1.5e+05)
| 100 |  8.5e+06 (3.7e+05) |  9.8e+06 (2.9e+05) |  8.5e+06 (6.8e+05) |  7.5e+06 (2.3e-09) |  1.0e+07 (1.2e+05)
| 200 |  8.7e+06 (4.8e+05) |  9.7e+06 (1.4e+05) |  9.2e+06 (3.1e+05) |  7.5e+06 (3.1e-09) |  1.1e+07 (5.4e+04)
| 500 |  8.4e+06 (1.8e+05) |  9.4e+06 (1.8e+05) |  8.8e+06 (5.4e+05) |  7.5e+06 (0.0e+00) |
Table 14: Costs of the evaluated algorithms on the Caltech data set. Each cell
specify the mean along with the standard deviation in parenthesis of 10
repetitions of the experiment. Costs on the Caltech data set
---
$k$ |  $m$ | BICO |  Group Sampling |  Ray Maker |  Sensitivity Sampling | StreamKM++
10 | 50 |  4.1e+11 (3.2e+09) |  4.1e+11 (2.9e+09) |  4.0e+11 (1.7e+09) |  4.0e+11 (2.5e+09) |  4.1e+11 (2.7e+09)
| 100 |  4.0e+11 (1.6e+09) |  4.0e+11 (3.1e+09) |  4.0e+11 (1.7e+09) |  4.0e+11 (3.0e+09) |  4.0e+11 (8.4e+08)
| 200 |  4.0e+11 (3.9e+09) |  4.0e+11 (1.5e+09) |  4.0e+11 (2.2e+09) |  4.0e+11 (1.5e+09) |  3.9e+11 (1.1e+09)
| 500 |  4.0e+11 (1.8e+09) |  3.9e+11 (1.7e+09) |  4.0e+11 (1.9e+09) |  3.9e+11 (6.3e+08) |
20 | 50 |  3.8e+11 (3.1e+09) |  3.7e+11 (1.3e+09) |  3.7e+11 (2.8e+09) |  3.7e+11 (2.4e+09) |  3.7e+11 (1.4e+09)
| 100 |  3.7e+11 (2.9e+09) |  3.7e+11 (1.2e+09) |  3.7e+11 (1.9e+09) |  3.7e+11 (7.8e+08) |  3.7e+11 (1.2e+09)
| 200 |  3.7e+11 (2.0e+09) |  3.6e+11 (1.1e+09) |  3.7e+11 (1.4e+09) |  3.6e+11 (6.8e+08) |  3.6e+11 (5.4e+08)
| 500 |  3.7e+11 (3.1e+09) |  3.6e+11 (8.8e+08) |  3.7e+11 (2.1e+09) |  3.6e+11 (7.5e+08) |
30 | 50 |  3.6e+11 (2.4e+09) |  3.6e+11 (1.3e+09) |  3.6e+11 (1.7e+09) |  3.6e+11 (1.1e+09) |  3.5e+11 (1.0e+09)
| 100 |  3.6e+11 (2.5e+09) |  3.5e+11 (9.0e+08) |  3.6e+11 (1.4e+09) |  3.5e+11 (1.1e+09) |  3.5e+11 (1.0e+09)
| 200 |  3.6e+11 (3.4e+09) |  3.5e+11 (8.0e+08) |  3.6e+11 (9.6e+08) |  3.5e+11 (4.5e+08) |  3.5e+11 (4.6e+08)
| 500 |  3.5e+11 (1.5e+09) |  3.4e+11 (6.2e+08) |  3.5e+11 (1.1e+09) |  3.4e+11 (9.0e+08) |
40 | 50 |  3.5e+11 (2.3e+09) |  3.4e+11 (8.2e+08) |  3.4e+11 (5.4e+08) |  3.4e+11 (1.0e+09) |  3.4e+11 (7.9e+08)
| 100 |  3.5e+11 (2.8e+09) |  3.4e+11 (1.1e+09) |  3.4e+11 (1.4e+09) |  3.4e+11 (6.0e+08) |  3.4e+11 (3.1e+08)
| 200 |  3.4e+11 (3.9e+09) |  3.3e+11 (5.2e+08) |  3.4e+11 (7.2e+08) |  3.4e+11 (4.2e+08) |  3.4e+11 (3.6e+08)
| 500 |  3.4e+11 (1.9e+09) |  3.3e+11 (3.1e+08) |  3.4e+11 (9.3e+08) |  3.3e+11 (2.8e+08) |
50 | 50 |  3.4e+11 (1.4e+09) |  3.4e+11 (9.2e+08) |  3.4e+11 (8.1e+08) |  3.4e+11 (1.0e+09) |  3.4e+11 (9.9e+08)
| 100 |  3.4e+11 (2.8e+09) |  3.3e+11 (3.0e+08) |  3.4e+11 (1.1e+09) |  3.3e+11 (5.7e+08) |  3.3e+11 (5.5e+08)
| 200 |  3.4e+11 (1.5e+09) |  3.3e+11 (4.7e+08) |  3.4e+11 (7.7e+08) |  3.3e+11 (3.3e+08) |  3.3e+11 (2.6e+08)
| 500 |  3.3e+11 (2.6e+09) |  3.2e+11 (3.7e+08) |  3.4e+11 (7.7e+08) |  3.2e+11 (1.7e+08) |
Table 15: Costs of the evaluated algorithms on the Caltech data set (with PCA
preprocessing). Each cell specify the mean along with the standard deviation
in parenthesis of 10 repetitions of the experiment. Costs on the Caltech data
set (with PCA preprocessing)
---
$k$ |  $m$ | BICO |  Group Sampling |  Ray Maker |  Sensitivity Sampling | StreamKM++
10 | 50 |  4.1e+11 (1.3e+09) |  4.1e+11 (1.1e+09) |  4.1e+11 (1.9e+09) |  4.1e+11 (1.9e+09) |  4.0e+11 (1.5e+09)
| 100 |  4.0e+11 (1.0e+09) |  4.0e+11 (1.4e+09) |  4.0e+11 (1.9e+09) |  4.0e+11 (1.2e+09) |  4.0e+11 (1.7e+09)
| 200 |  4.0e+11 (2.1e+09) |  4.0e+11 (1.3e+09) |  4.0e+11 (1.8e+09) |  4.0e+11 (1.2e+09) |  4.0e+11 (8.4e+08)
| 500 |  4.0e+11 (1.4e+09) |  4.0e+11 (9.7e+08) |  4.0e+11 (1.5e+09) |  4.0e+11 (9.2e+08) |
20 | 50 |  3.7e+11 (1.3e+09) |  3.7e+11 (1.3e+09) |  3.7e+11 (1.1e+09) |  3.7e+11 (1.2e+09) |  3.7e+11 (1.6e+09)
| 100 |  3.7e+11 (1.3e+09) |  3.7e+11 (9.1e+08) |  3.7e+11 (9.5e+08) |  3.7e+11 (1.0e+09) |  3.7e+11 (9.9e+08)
| 200 |  3.7e+11 (1.1e+09) |  3.7e+11 (5.1e+08) |  3.7e+11 (1.6e+09) |  3.7e+11 (7.8e+08) |  3.6e+11 (3.4e+08)
| 500 |  3.7e+11 (6.4e+08) |  3.6e+11 (5.2e+08) |  3.7e+11 (8.8e+08) |  3.6e+11 (4.7e+08) |
30 | 50 |  3.6e+11 (1.2e+09) |  3.5e+11 (1.3e+09) |  3.6e+11 (1.1e+09) |  3.5e+11 (9.0e+08) |  3.5e+11 (5.5e+08)
| 100 |  3.6e+11 (2.2e+09) |  3.5e+11 (9.5e+08) |  3.6e+11 (1.1e+09) |  3.5e+11 (1.4e+09) |  3.5e+11 (7.2e+08)
| 200 |  3.5e+11 (1.7e+09) |  3.5e+11 (4.9e+08) |  3.6e+11 (6.5e+08) |  3.5e+11 (8.1e+08) |  3.5e+11 (4.0e+08)
| 500 |  3.5e+11 (1.7e+09) |  3.5e+11 (5.7e+08) |  3.6e+11 (1.6e+09) |  3.5e+11 (4.8e+08) |
40 | 50 |  3.5e+11 (1.7e+09) |  3.4e+11 (1.1e+09) |  3.4e+11 (1.0e+09) |  3.4e+11 (8.0e+08) |  3.4e+11 (5.3e+08)
| 100 |  3.5e+11 (2.0e+09) |  3.4e+11 (3.6e+08) |  3.4e+11 (8.5e+08) |  3.4e+11 (6.9e+08) |  3.4e+11 (5.1e+08)
| 200 |  3.4e+11 (1.5e+09) |  3.4e+11 (4.7e+08) |  3.4e+11 (1.2e+09) |  3.4e+11 (6.2e+08) |  3.4e+11 (3.9e+08)
| 500 |  3.4e+11 (1.6e+09) |  3.3e+11 (1.9e+08) |  3.4e+11 (1.1e+09) |  3.3e+11 (3.0e+08) |
50 | 50 |  3.4e+11 (1.2e+09) |  3.4e+11 (6.1e+08) |  3.4e+11 (5.7e+08) |  3.3e+11 (1.1e+09) |  3.3e+11 (1.0e+09)
| 100 |  3.4e+11 (1.6e+09) |  3.3e+11 (6.2e+08) |  3.4e+11 (6.2e+08) |  3.3e+11 (4.5e+08) |  3.3e+11 (2.8e+08)
| 200 |  3.3e+11 (2.1e+09) |  3.3e+11 (5.1e+08) |  3.4e+11 (8.1e+08) |  3.3e+11 (3.3e+08) |  3.3e+11 (2.9e+08)
| 500 |  3.3e+11 (1.4e+09) |  3.3e+11 (2.3e+08) |  3.4e+11 (1.1e+09) |  3.3e+11 (2.8e+08) |
Table 16: Costs of the evaluated algorithms on the Census data set. Each cell
specify the mean along with the standard deviation in parenthesis of 10
repetitions of the experiment. Costs on the Census data set
---
$k$ |  $m$ | BICO |  Group Sampling |  Ray Maker |  Sensitivity Sampling | StreamKM++
10 | 50 |  2.5e+08 (4.7e+06) |  2.6e+08 (9.7e+06) |  2.5e+08 (7.5e+06) |  2.7e+08 (1.5e+07) |  2.5e+08 (8.9e+06)
| 100 |  2.5e+08 (6.1e+06) |  2.6e+08 (1.2e+07) |  2.5e+08 (5.1e+06) |  2.6e+08 (8.3e+06) |  2.6e+08 (7.9e+06)
| 200 |  2.5e+08 (5.8e+06) |  2.6e+08 (1.2e+07) |  2.5e+08 (5.0e+06) |  2.7e+08 (1.0e+07) |  2.5e+08 (5.1e+06)
| 500 |  2.5e+08 (4.3e+06) |  2.6e+08 (1.5e+07) |  2.4e+08 (2.6e+06) |  2.6e+08 (1.2e+07) |
20 | 50 |  1.9e+08 (4.3e+06) |  2.1e+08 (1.1e+07) |  1.9e+08 (2.0e+06) |  2.0e+08 (1.1e+07) |  1.9e+08 (4.3e+06)
| 100 |  1.9e+08 (4.9e+06) |  2.0e+08 (7.2e+06) |  1.9e+08 (2.1e+06) |  2.0e+08 (9.7e+06) |  1.9e+08 (4.0e+06)
| 200 |  1.9e+08 (3.1e+06) |  2.0e+08 (6.4e+06) |  1.9e+08 (2.1e+06) |  2.0e+08 (6.0e+06) |  1.9e+08 (2.5e+06)
| 500 |  1.9e+08 (3.4e+06) |  1.9e+08 (6.2e+06) |  1.9e+08 (2.2e+06) |  2.0e+08 (8.3e+06) |
30 | 50 |  1.6e+08 (2.4e+06) |  1.7e+08 (4.0e+06) |  1.6e+08 (3.1e+06) |  1.7e+08 (4.9e+06) |  1.6e+08 (1.8e+06)
| 100 |  1.6e+08 (3.2e+06) |  1.7e+08 (3.4e+06) |  1.6e+08 (2.4e+06) |  1.7e+08 (4.9e+06) |  1.6e+08 (2.9e+06)
| 200 |  1.6e+08 (2.5e+06) |  1.6e+08 (5.3e+06) |  1.6e+08 (2.5e+06) |  1.7e+08 (3.2e+06) |  1.6e+08 (2.7e+06)
| 500 |  1.6e+08 (1.5e+06) |  1.6e+08 (5.8e+06) |  1.6e+08 (2.4e+06) |  1.7e+08 (4.5e+06) |
40 | 50 |  1.4e+08 (2.5e+06) |  1.5e+08 (7.1e+06) |  1.4e+08 (2.2e+06) |  1.5e+08 (3.7e+06) |  1.4e+08 (1.6e+06)
| 100 |  1.4e+08 (1.7e+06) |  1.5e+08 (3.4e+06) |  1.4e+08 (1.6e+06) |  1.5e+08 (2.2e+06) |  1.4e+08 (2.0e+06)
| 200 |  1.4e+08 (1.7e+06) |  1.5e+08 (4.6e+06) |  1.4e+08 (8.6e+05) |  1.4e+08 (3.9e+06) |  1.4e+08 (1.9e+06)
| 500 |  1.4e+08 (1.6e+06) |  1.4e+08 (2.4e+06) |  1.4e+08 (1.8e+06) |  1.4e+08 (3.2e+06) |
50 | 50 |  1.3e+08 (2.1e+06) |  1.3e+08 (1.5e+06) |  1.3e+08 (1.2e+06) |  1.3e+08 (3.3e+06) |  1.3e+08 (2.9e+06)
| 100 |  1.3e+08 (1.5e+06) |  1.3e+08 (2.2e+06) |  1.3e+08 (2.2e+06) |  1.4e+08 (3.4e+06) |  1.3e+08 (2.3e+06)
| 200 |  1.3e+08 (1.0e+06) |  1.3e+08 (1.6e+06) |  1.3e+08 (1.8e+06) |  1.3e+08 (3.3e+06) |  1.3e+08 (1.9e+06)
| 500 |  1.3e+08 (2.0e+06) |  1.3e+08 (1.6e+06) |  1.3e+08 (1.7e+06) |  1.3e+08 (2.4e+06) |
Table 17: Costs of the evaluated algorithms on the Census data set (with PCA
preprocessing). Each cell specify the mean along with the standard deviation
in parenthesis of 10 repetitions of the experiment. Costs on the Census data
set (with PCA preprocessing)
---
$k$ |  $m$ | BICO |  Group Sampling |  Ray Maker |  Sensitivity Sampling | StreamKM++
10 | 50 |  2.5e+08 (6.2e+06) |  2.6e+08 (9.8e+06) |  2.5e+08 (4.7e+06) |  2.7e+08 (8.1e+06) |  2.6e+08 (6.9e+06)
| 100 |  2.5e+08 (5.8e+06) |  2.7e+08 (8.8e+06) |  2.5e+08 (6.8e+06) |  2.7e+08 (1.5e+07) |  2.6e+08 (1.1e+07)
| 200 |  2.5e+08 (4.2e+06) |  2.5e+08 (8.2e+06) |  2.5e+08 (4.9e+06) |  2.7e+08 (1.1e+07) |  2.5e+08 (7.2e+06)
| 500 |  2.5e+08 (5.9e+06) |  2.6e+08 (1.1e+07) |  2.5e+08 (7.2e+06) |  2.6e+08 (1.2e+07) |
20 | 50 |  2.0e+08 (5.2e+06) |  2.0e+08 (7.1e+06) |  1.9e+08 (5.0e+06) |  2.0e+08 (7.6e+06) |  2.0e+08 (6.3e+06)
| 100 |  1.9e+08 (1.9e+06) |  2.0e+08 (5.3e+06) |  1.9e+08 (4.1e+06) |  2.1e+08 (1.4e+07) |  1.9e+08 (3.4e+06)
| 200 |  1.9e+08 (2.7e+06) |  2.0e+08 (6.9e+06) |  1.9e+08 (3.7e+06) |  2.0e+08 (8.4e+06) |  1.9e+08 (3.3e+06)
| 500 |  1.9e+08 (2.8e+06) |  2.0e+08 (4.9e+06) |  1.9e+08 (4.1e+06) |  2.0e+08 (6.2e+06) |
30 | 50 |  1.6e+08 (2.9e+06) |  1.7e+08 (7.9e+06) |  1.6e+08 (2.5e+06) |  1.7e+08 (5.3e+06) |  1.6e+08 (3.1e+06)
| 100 |  1.6e+08 (2.2e+06) |  1.6e+08 (4.2e+06) |  1.6e+08 (2.1e+06) |  1.7e+08 (2.2e+06) |  1.6e+08 (2.9e+06)
| 200 |  1.6e+08 (2.6e+06) |  1.6e+08 (3.4e+06) |  1.6e+08 (2.1e+06) |  1.7e+08 (5.0e+06) |  1.6e+08 (2.7e+06)
| 500 |  1.6e+08 (1.6e+06) |  1.6e+08 (3.4e+06) |  1.6e+08 (2.9e+06) |  1.7e+08 (6.8e+06) |
40 | 50 |  1.5e+08 (2.8e+06) |  1.5e+08 (2.5e+06) |  1.4e+08 (1.4e+06) |  1.5e+08 (3.5e+06) |  1.4e+08 (2.6e+06)
| 100 |  1.4e+08 (2.6e+06) |  1.4e+08 (2.8e+06) |  1.4e+08 (1.9e+06) |  1.5e+08 (6.9e+06) |  1.4e+08 (2.4e+06)
| 200 |  1.4e+08 (2.4e+06) |  1.4e+08 (2.4e+06) |  1.4e+08 (2.2e+06) |  1.5e+08 (5.0e+06) |  1.4e+08 (2.0e+06)
| 500 |  1.4e+08 (1.9e+06) |  1.4e+08 (2.5e+06) |  1.4e+08 (2.0e+06) |  1.4e+08 (4.4e+06) |
50 | 50 |  1.3e+08 (2.0e+06) |  1.4e+08 (3.0e+06) |  1.3e+08 (2.3e+06) |  1.3e+08 (3.3e+06) |  1.3e+08 (1.5e+06)
| 100 |  1.3e+08 (1.3e+06) |  1.3e+08 (2.5e+06) |  1.3e+08 (7.1e+05) |  1.3e+08 (4.2e+06) |  1.3e+08 (1.8e+06)
| 200 |  1.3e+08 (1.8e+06) |  1.3e+08 (2.0e+06) |  1.3e+08 (1.5e+06) |  1.3e+08 (6.3e+06) |  1.3e+08 (1.5e+06)
| 500 |  1.3e+08 (1.3e+06) |  1.3e+08 (4.3e+06) |  1.3e+08 (2.0e+06) |  1.3e+08 (3.8e+06) |
Table 18: Costs of the evaluated algorithms on the Covertype data set. Each
cell specify the mean along with the standard deviation in parenthesis of 10
repetitions of the experiment. Costs on the Covertype data set
---
$k$ |  $m$ | BICO |  Group Sampling |  Ray Maker |  Sensitivity Sampling | StreamKM++
10 | 50 |  3.5e+11 (5.4e+09) |  3.6e+11 (4.8e+09) |  3.5e+11 (5.5e+09) |  3.6e+11 (9.1e+09) |  3.5e+11 (8.5e+09)
| 100 |  3.5e+11 (4.4e+09) |  3.5e+11 (4.8e+09) |  3.5e+11 (6.2e+09) |  3.6e+11 (4.9e+09) |  3.5e+11 (5.6e+09)
| 200 |  3.4e+11 (3.2e+09) |  3.5e+11 (5.2e+09) |  3.5e+11 (5.1e+09) |  3.5e+11 (5.7e+09) |  3.4e+11 (1.8e+09)
| 500 |  3.4e+11 (3.3e+09) |  3.4e+11 (5.1e+09) |  3.5e+11 (6.7e+09) |  3.5e+11 (3.2e+09) |
20 | 50 |  2.1e+11 (2.5e+09) |  2.1e+11 (2.3e+09) |  2.1e+11 (1.9e+09) |  2.2e+11 (4.1e+09) |  2.1e+11 (2.8e+09)
| 100 |  2.1e+11 (1.9e+09) |  2.1e+11 (3.0e+09) |  2.1e+11 (2.4e+09) |  2.1e+11 (4.2e+09) |  2.1e+11 (1.5e+09)
| 200 |  2.0e+11 (9.0e+08) |  2.1e+11 (2.0e+09) |  2.1e+11 (1.4e+09) |  2.1e+11 (2.5e+09) |  2.0e+11 (1.3e+09)
| 500 |  2.0e+11 (8.4e+08) |  2.1e+11 (2.0e+09) |  2.1e+11 (1.9e+09) |  2.1e+11 (1.6e+09) |
30 | 50 |  1.6e+11 (1.9e+09) |  1.6e+11 (1.4e+09) |  1.6e+11 (1.8e+09) |  1.6e+11 (2.7e+09) |  1.6e+11 (1.5e+09)
| 100 |  1.6e+11 (1.4e+09) |  1.6e+11 (1.4e+09) |  1.6e+11 (1.6e+09) |  1.6e+11 (1.4e+09) |  1.6e+11 (1.4e+09)
| 200 |  1.6e+11 (1.3e+09) |  1.6e+11 (1.4e+09) |  1.6e+11 (1.5e+09) |  1.6e+11 (1.4e+09) |  1.6e+11 (1.2e+09)
| 500 |  1.5e+11 (1.1e+09) |  1.6e+11 (9.3e+08) |  1.6e+11 (2.1e+09) |  1.6e+11 (1.4e+09) |
40 | 50 |  1.3e+11 (1.6e+09) |  1.4e+11 (8.7e+08) |  1.3e+11 (7.5e+08) |  1.4e+11 (1.3e+09) |  1.3e+11 (1.9e+09)
| 100 |  1.3e+11 (7.9e+08) |  1.3e+11 (1.2e+09) |  1.3e+11 (1.2e+09) |  1.3e+11 (1.5e+09) |  1.3e+11 (1.2e+09)
| 200 |  1.3e+11 (8.5e+08) |  1.3e+11 (1.3e+09) |  1.3e+11 (1.8e+09) |  1.3e+11 (9.3e+08) |  1.3e+11 (8.8e+08)
| 500 |  1.3e+11 (3.8e+08) |  1.3e+11 (9.9e+08) |  1.3e+11 (7.0e+08) |  1.3e+11 (9.1e+08) |
50 | 50 |  1.2e+11 (8.8e+08) |  1.2e+11 (9.4e+08) |  1.2e+11 (7.2e+08) |  1.2e+11 (1.2e+09) |  1.2e+11 (1.1e+09)
| 100 |  1.2e+11 (7.7e+08) |  1.2e+11 (9.6e+08) |  1.2e+11 (6.4e+08) |  1.2e+11 (1.1e+09) |  1.2e+11 (1.0e+09)
| 200 |  1.1e+11 (7.2e+08) |  1.2e+11 (1.5e+09) |  1.2e+11 (4.9e+08) |  1.2e+11 (7.0e+08) |  1.1e+11 (7.6e+08)
| 500 |  1.1e+11 (6.0e+08) |  1.1e+11 (7.4e+08) |  1.2e+11 (9.1e+08) |  1.1e+11 (7.0e+08) |
Table 19: Costs of the evaluated algorithms on the Covertype data set (with
PCA preprocessing). Each cell specify the mean along with the standard
deviation in parenthesis of 10 repetitions of the experiment. Costs on the
Covertype data set (with PCA preprocessing)
---
$k$ |  $m$ | BICO |  Group Sampling |  Ray Maker |  Sensitivity Sampling | StreamKM++
10 | 50 |  3.5e+11 (5.4e+09) |  3.6e+11 (1.0e+10) |  3.5e+11 (7.4e+09) |  3.6e+11 (9.2e+09) |  3.5e+11 (5.9e+09)
| 100 |  3.5e+11 (4.6e+09) |  3.5e+11 (6.8e+09) |  3.5e+11 (3.2e+09) |  3.6e+11 (3.5e+09) |  3.5e+11 (3.0e+09)
| 200 |  3.4e+11 (3.1e+09) |  3.5e+11 (6.9e+09) |  3.5e+11 (6.7e+09) |  3.5e+11 (3.6e+09) |  3.4e+11 (3.8e+08)
| 500 |  3.4e+11 (2.2e+09) |  3.4e+11 (3.5e+09) |  3.5e+11 (3.1e+09) |  3.5e+11 (3.7e+09) |
20 | 50 |  2.1e+11 (1.7e+09) |  2.1e+11 (2.6e+09) |  2.1e+11 (2.7e+09) |  2.2e+11 (4.7e+09) |  2.1e+11 (4.3e+09)
| 100 |  2.1e+11 (2.6e+09) |  2.1e+11 (3.7e+09) |  2.1e+11 (2.5e+09) |  2.1e+11 (1.6e+09) |  2.1e+11 (1.6e+09)
| 200 |  2.1e+11 (1.2e+09) |  2.1e+11 (1.7e+09) |  2.1e+11 (1.7e+09) |  2.1e+11 (2.1e+09) |  2.0e+11 (1.3e+09)
| 500 |  2.0e+11 (6.3e+08) |  2.1e+11 (1.2e+09) |  2.1e+11 (1.8e+09) |  2.1e+11 (2.0e+09) |
30 | 50 |  1.6e+11 (1.6e+09) |  1.6e+11 (2.2e+09) |  1.6e+11 (1.6e+09) |  1.7e+11 (4.8e+09) |  1.6e+11 (1.7e+09)
| 100 |  1.6e+11 (1.2e+09) |  1.6e+11 (1.7e+09) |  1.6e+11 (1.4e+09) |  1.6e+11 (1.5e+09) |  1.6e+11 (1.0e+09)
| 200 |  1.6e+11 (5.7e+08) |  1.6e+11 (2.5e+09) |  1.6e+11 (1.6e+09) |  1.6e+11 (1.5e+09) |  1.5e+11 (6.7e+08)
| 500 |  1.5e+11 (6.0e+08) |  1.6e+11 (1.5e+09) |  1.6e+11 (1.0e+09) |  1.6e+11 (1.2e+09) |
40 | 50 |  1.3e+11 (1.6e+09) |  1.4e+11 (1.6e+09) |  1.3e+11 (1.2e+09) |  1.4e+11 (1.6e+09) |  1.3e+11 (9.7e+08)
| 100 |  1.3e+11 (1.3e+09) |  1.3e+11 (1.4e+09) |  1.3e+11 (1.4e+09) |  1.3e+11 (1.8e+09) |  1.3e+11 (1.3e+09)
| 200 |  1.3e+11 (8.2e+08) |  1.3e+11 (9.9e+08) |  1.3e+11 (1.2e+09) |  1.3e+11 (1.8e+09) |  1.3e+11 (3.1e+08)
| 500 |  1.3e+11 (5.4e+08) |  1.3e+11 (7.2e+08) |  1.3e+11 (8.2e+08) |  1.3e+11 (1.3e+09) |
50 | 50 |  1.2e+11 (8.4e+08) |  1.2e+11 (1.4e+09) |  1.2e+11 (9.7e+08) |  1.2e+11 (1.7e+09) |  1.2e+11 (1.4e+09)
| 100 |  1.2e+11 (1.4e+09) |  1.2e+11 (1.0e+09) |  1.2e+11 (4.7e+08) |  1.2e+11 (1.1e+09) |  1.2e+11 (1.1e+09)
| 200 |  1.1e+11 (9.7e+08) |  1.2e+11 (1.0e+09) |  1.2e+11 (9.4e+08) |  1.2e+11 (6.0e+08) |  1.1e+11 (8.8e+08)
| 500 |  1.1e+11 (6.2e+08) |  1.1e+11 (6.1e+08) |  1.2e+11 (9.0e+08) |  1.1e+11 (7.0e+08) |
Table 20: Costs of the evaluated algorithms on the NYTimes data set. Each cell
specify the mean along with the standard deviation in parenthesis of 10
repetitions of the experiment. Costs on the NYTimes data set
---
$k$ |  $m$ | BICO |  Group Sampling |  Ray Maker |  Sensitivity Sampling | StreamKM++
10 | 50 |  2.8e+08 (7.7e+05) |  2.8e+08 (4.6e+05) |  2.8e+08 (3.6e+05) |  2.8e+08 (5.2e+05) |  2.9e+08 (1.5e+06)
| 100 |  2.8e+08 (7.7e+05) |  2.8e+08 (4.4e+05) |  2.8e+08 (4.9e+05) |  2.8e+08 (5.1e+05) |  2.8e+08 (7.2e+05)
| 200 |  2.8e+08 (9.3e+05) |  2.8e+08 (8.6e+05) |  2.8e+08 (7.7e+05) |  2.8e+08 (5.2e+05) |  2.8e+08 (7.4e+05)
| 500 |  2.8e+08 (4.5e+05) |  2.8e+08 (3.0e+05) |  2.8e+08 (5.6e+05) |  2.8e+08 (3.9e+05) |
20 | 50 |  2.8e+08 (9.7e+05) |  2.8e+08 (1.2e+06) |  2.8e+08 (5.5e+05) |  2.8e+08 (9.1e+05) |  2.8e+08 (5.3e+05)
| 100 |  2.7e+08 (9.1e+05) |  2.8e+08 (6.8e+05) |  2.7e+08 (5.1e+05) |  2.8e+08 (8.8e+05) |  2.8e+08 (7.5e+05)
| 200 |  2.7e+08 (5.0e+05) |  2.7e+08 (6.6e+05) |  2.7e+08 (5.9e+05) |  2.7e+08 (6.8e+05) |  2.8e+08 (1.0e+06)
| 500 |  2.7e+08 (6.5e+05) |  2.7e+08 (2.4e+05) |  2.7e+08 (1.0e+06) |  2.7e+08 (4.6e+05) |
30 | 50 |  2.7e+08 (6.6e+05) |  2.7e+08 (1.1e+06) |  2.7e+08 (7.7e+05) |  2.7e+08 (1.7e+06) |  2.8e+08 (1.1e+06)
| 100 |  2.7e+08 (7.7e+05) |  2.7e+08 (1.1e+06) |  2.7e+08 (1.1e+06) |  2.7e+08 (1.0e+06) |  2.7e+08 (1.0e+06)
| 200 |  2.7e+08 (7.4e+05) |  2.7e+08 (6.6e+05) |  2.7e+08 (8.2e+05) |  2.7e+08 (9.0e+05) |  2.7e+08 (1.2e+06)
| 500 |  2.7e+08 (7.9e+05) |  2.6e+08 (5.2e+05) |  2.7e+08 (1.0e+06) |  2.6e+08 (4.5e+05) |
40 | 50 |  2.7e+08 (1.1e+06) |  2.7e+08 (9.1e+05) |  2.7e+08 (1.0e+06) |  2.7e+08 (9.9e+05) |  2.8e+08 (5.2e+05)
| 100 |  2.6e+08 (7.2e+05) |  2.6e+08 (8.4e+05) |  2.7e+08 (8.2e+05) |  2.6e+08 (1.0e+06) |  2.7e+08 (8.3e+05)
| 200 |  2.6e+08 (8.1e+05) |  2.6e+08 (4.6e+05) |  2.7e+08 (7.6e+05) |  2.6e+08 (5.0e+05) |  2.7e+08 (8.7e+05)
| 500 |  2.6e+08 (9.5e+05) |  2.6e+08 (7.4e+05) |  2.7e+08 (1.1e+06) |  2.6e+08 (4.1e+05) |
50 | 50 |  2.6e+08 (1.0e+06) |  2.7e+08 (8.0e+05) |  2.6e+08 (5.5e+05) |  2.6e+08 (1.5e+06) |  2.7e+08 (8.9e+05)
| 100 |  2.6e+08 (9.9e+05) |  2.6e+08 (9.0e+05) |  2.6e+08 (5.8e+05) |  2.6e+08 (1.5e+06) |  2.7e+08 (9.0e+05)
| 200 |  2.6e+08 (9.4e+05) |  2.6e+08 (4.3e+05) |  2.6e+08 (8.0e+05) |  2.6e+08 (5.5e+05) |  2.6e+08 (1.1e+06)
| 500 |  2.6e+08 (6.5e+05) |  2.5e+08 (5.9e+05) |  2.6e+08 (1.1e+06) |  2.5e+08 (4.6e+05) |
Table 21: Costs of the evaluated algorithms on the NYTimes data set (with PCA
preprocessing). Each cell specify the mean along with the standard deviation
in parenthesis of 10 repetitions of the experiment. Costs on the NYTimes data
set (with PCA preprocessing)
---
$k$ |  $m$ | BICO |  Group Sampling |  Ray Maker |  Sensitivity Sampling | StreamKM++
10 | 50 |  2.7e+08 (5.5e+05) |  2.7e+08 (5.2e+05) |  2.7e+08 (4.7e+05) |  2.7e+08 (5.3e+05) |  2.7e+08 (5.4e+05)
| 100 |  2.7e+08 (4.5e+05) |  2.7e+08 (4.5e+05) |  2.7e+08 (6.9e+05) |  2.7e+08 (7.4e+05) |  2.7e+08 (3.4e+05)
| 200 |  2.7e+08 (4.9e+05) |  2.7e+08 (3.4e+05) |  2.7e+08 (5.0e+05) |  2.7e+08 (5.9e+05) |  2.7e+08 (8.4e+04)
| 500 |  2.7e+08 (2.2e+05) |  2.7e+08 (2.5e+05) |  2.7e+08 (3.6e+05) |  2.7e+08 (5.1e+05) |
20 | 50 |  2.6e+08 (4.2e+05) |  2.6e+08 (4.3e+05) |  2.6e+08 (2.6e+05) |  2.6e+08 (4.4e+05) |  2.6e+08 (2.5e+05)
| 100 |  2.6e+08 (3.8e+05) |  2.6e+08 (5.9e+05) |  2.6e+08 (3.2e+05) |  2.6e+08 (5.1e+05) |  2.6e+08 (2.5e+05)
| 200 |  2.6e+08 (2.7e+05) |  2.6e+08 (2.5e+05) |  2.6e+08 (3.9e+05) |  2.6e+08 (2.5e+05) |  2.6e+08 (2.0e+05)
| 500 |  2.6e+08 (1.4e+05) |  2.6e+08 (1.8e+05) |  2.6e+08 (2.2e+05) |  2.6e+08 (1.5e+05) |
30 | 50 |  2.6e+08 (5.7e+05) |  2.6e+08 (3.7e+05) |  2.6e+08 (3.0e+05) |  2.6e+08 (4.2e+05) |  2.6e+08 (3.4e+05)
| 100 |  2.6e+08 (4.3e+05) |  2.6e+08 (3.4e+05) |  2.6e+08 (3.0e+05) |  2.6e+08 (3.1e+05) |  2.6e+08 (3.7e+05)
| 200 |  2.6e+08 (4.2e+05) |  2.6e+08 (2.2e+05) |  2.6e+08 (3.8e+05) |  2.6e+08 (5.1e+05) |  2.6e+08 (3.0e+05)
| 500 |  2.6e+08 (2.5e+05) |  2.6e+08 (1.8e+05) |  2.6e+08 (2.8e+05) |  2.6e+08 (3.6e+05) |
40 | 50 |  2.6e+08 (2.3e+05) |  2.6e+08 (4.3e+05) |  2.6e+08 (4.0e+05) |  2.6e+08 (4.4e+05) |  2.6e+08 (4.5e+05)
| 100 |  2.6e+08 (6.4e+05) |  2.6e+08 (2.7e+05) |  2.6e+08 (4.6e+05) |  2.6e+08 (5.0e+05) |  2.6e+08 (1.1e+05)
| 200 |  2.6e+08 (4.7e+05) |  2.6e+08 (2.9e+05) |  2.6e+08 (4.0e+05) |  2.6e+08 (4.1e+05) |  2.6e+08 (1.8e+05)
| 500 |  2.6e+08 (3.5e+05) |  2.6e+08 (2.0e+05) |  2.6e+08 (3.3e+05) |  2.6e+08 (2.4e+05) |
50 | 50 |  2.5e+08 (3.8e+05) |  2.5e+08 (4.6e+05) |  2.5e+08 (3.6e+05) |  2.5e+08 (5.5e+05) |  2.5e+08 (4.3e+05)
| 100 |  2.5e+08 (4.4e+05) |  2.5e+08 (3.2e+05) |  2.5e+08 (5.0e+05) |  2.5e+08 (5.2e+05) |  2.5e+08 (3.9e+05)
| 200 |  2.5e+08 (3.6e+05) |  2.5e+08 (3.6e+05) |  2.5e+08 (5.0e+05) |  2.5e+08 (3.8e+05) |  2.5e+08 (2.8e+05)
| 500 |  2.5e+08 (3.7e+05) |  2.5e+08 (3.3e+05) |  2.5e+08 (3.8e+05) |  2.5e+08 (3.2e+05) |
Table 22: Costs of the evaluated algorithms on the Tower data set. Each cell
specify the mean along with the standard deviation in parenthesis of 10
repetitions of the experiment. Costs on the Tower data set
---
$k$ |  $m$ | BICO |  Group Sampling |  Ray Maker |  Sensitivity Sampling | StreamKM++
20 | 50 |  6.5e+08 (1.3e+07) |  6.6e+08 (3.4e+07) |  6.6e+08 (1.8e+07) |  6.6e+08 (1.4e+07) |  6.5e+08 (2.3e+07)
| 100 |  6.4e+08 (1.8e+07) |  6.5e+08 (2.3e+07) |  6.3e+08 (1.3e+07) |  6.8e+08 (4.2e+07) |  6.4e+08 (1.4e+07)
| 200 |  6.3e+08 (4.8e+06) |  6.4e+08 (2.0e+07) |  6.2e+08 (7.0e+06) |  6.5e+08 (1.9e+07) |  6.3e+08 (1.4e+07)
| 500 |  6.2e+08 (8.4e+06) |  6.5e+08 (4.8e+07) |  6.2e+08 (1.2e+07) |  6.4e+08 (2.0e+07) |
40 | 50 |  3.4e+08 (7.3e+06) |  3.6e+08 (6.3e+06) |  3.4e+08 (5.2e+06) |  3.6e+08 (8.4e+06) |  3.4e+08 (4.9e+06)
| 100 |  3.4e+08 (9.1e+06) |  3.5e+08 (5.9e+06) |  3.4e+08 (6.0e+06) |  3.5e+08 (7.9e+06) |  3.4e+08 (1.6e+06)
| 200 |  3.3e+08 (2.2e+06) |  3.4e+08 (5.9e+06) |  3.3e+08 (2.5e+06) |  3.5e+08 (5.5e+06) |  3.3e+08 (4.4e+06)
| 500 |  3.3e+08 (3.2e+06) |  3.3e+08 (5.9e+06) |  3.3e+08 (5.2e+06) |  3.4e+08 (5.6e+06) |
60 | 50 |  2.5e+08 (3.1e+06) |  2.5e+08 (3.4e+06) |  2.5e+08 (3.8e+06) |  2.6e+08 (5.3e+06) |  2.5e+08 (3.4e+06)
| 100 |  2.5e+08 (3.7e+06) |  2.5e+08 (2.3e+06) |  2.4e+08 (1.4e+06) |  2.5e+08 (5.2e+06) |  2.4e+08 (2.9e+06)
| 200 |  2.4e+08 (1.7e+06) |  2.5e+08 (2.9e+06) |  2.4e+08 (2.3e+06) |  2.5e+08 (3.5e+06) |  2.4e+08 (2.2e+06)
| 500 |  2.4e+08 (2.1e+06) |  2.4e+08 (1.8e+06) |  2.4e+08 (2.2e+06) |  2.5e+08 (3.3e+06) |
80 | 50 |  2.0e+08 (1.5e+06) |  2.0e+08 (3.3e+06) |  2.0e+08 (1.6e+06) |  2.0e+08 (3.4e+06) |  2.0e+08 (1.7e+06)
| 100 |  2.0e+08 (1.9e+06) |  2.0e+08 (2.7e+06) |  2.0e+08 (1.7e+06) |  2.0e+08 (2.6e+06) |  2.0e+08 (2.6e+06)
| 200 |  1.9e+08 (1.4e+06) |  2.0e+08 (2.4e+06) |  1.9e+08 (1.4e+06) |  2.0e+08 (2.0e+06) |  1.9e+08 (1.4e+06)
| 500 |  1.9e+08 (1.2e+06) |  2.0e+08 (2.4e+06) |  1.9e+08 (1.7e+06) |  1.9e+08 (2.2e+06) |
100 | 50 |  1.7e+08 (2.1e+06) |  1.7e+08 (2.6e+06) |  1.7e+08 (1.5e+06) |  1.7e+08 (1.5e+06) |  1.7e+08 (2.0e+06)
| 100 |  1.7e+08 (1.5e+06) |  1.7e+08 (2.0e+06) |  1.7e+08 (1.4e+06) |  1.7e+08 (1.7e+06) |  1.7e+08 (9.2e+05)
| 200 |  1.6e+08 (1.2e+06) |  1.7e+08 (1.3e+06) |  1.6e+08 (1.2e+06) |  1.7e+08 (1.8e+06) |  1.6e+08 (7.8e+05)
| 500 |  1.6e+08 (7.7e+05) |  1.7e+08 (9.1e+05) |  1.6e+08 (1.3e+06) |  1.7e+08 (1.3e+06) |

##  Appendix E Running Times

Table 23: Running times (in seconds) of the evaluated algorithms on the
Benchmark data set. Each cell specify the mean along with the standard
deviation in parenthesis of 10 repetitions of the experiment. Running times on
the Benchmark data set
---
$k$ |  $m$ | BICO |  Group Sampling | Ray Maker |  Sensitivity Sampling | StreamKM++
10 | 50 | 19 (3) | 117 (10) | 138 (15) | 106 (10) | 736 (60)
| 100 | 20 (4) | 120 (7) | 143 (17) | 107 (8) | 1460 (87)
| 200 | 25 (3) | 118 (10) | 151 (19) | 108 (8) | 2889 (139)
| 500 | 31 (7) | 125 (9) | 188 (10) | 105 (14) |
20 | 50 | 104 (7) | 1016 (74) | 904 (68) | 933 (81) | 7233 (555)
| 100 | 124 (14) | 1021 (77) | 918 (72) | 913 (112) | 14546 (528)
| 200 | 176 (12) | 1004 (73) | 960 (77) | 933 (89) | 28532 (1115)
| 500 | 298 (52) | 1014 (54) | 1040 (128) | 930 (101) |
30 | 50 | 36 (3) | 440 (36) | 356 (30) | 420 (29) | 3344 (306)
| 100 | 41 (3) | 440 (37) | 362 (30) | 418 (45) | 6433 (464)
| 200 | 49 (3) | 442 (30) | 371 (30) | 423 (37) | 12431 (969)
| 500 | 70 (2) | 445 (43) | 410 (28) | 424 (43) |
40 | 50 | 124 (7) | 2064 (157) | 1480 (124) | 1917 (200) | 18387 (918)
| 100 | 154 (13) | 2032 (181) | 1513 (120) | 1931 (189) | 36296 (1090)
| 200 | 175 (15) | 2079 (160) | 1534 (120) | 1919 (202) | 64835 (2254)
| 500 | 240 (18) | 2068 (80) | 1596 (128) | 2005 (97) |
Table 24: Running times (in seconds) of the evaluated algorithms on the
Caltech data set. Each cell specify the mean along with the standard deviation
in parenthesis of 10 repetitions of the experiment. Running times on the
Caltech data set
---
$k$ |  $m$ | BICO |  Group Sampling | Ray Maker |  Sensitivity Sampling | StreamKM++
10 | 50 | 133 (9) | 1039 (33) | 1146 (134) | 940 (98) | 5799 (309)
| 100 | 151 (12) | 1020 (55) | 1202 (49) | 949 (92) | 11026 (675)
| 200 | 180 (22) | 1029 (53) | 1218 (118) | 974 (34) | 21922 (952)
| 500 | 233 (17) | 933 (65) | 1302 (39) | 877 (61) |
20 | 50 | 144 (16) | 1549 (113) | 1400 (85) | 1447 (106) | 11418 (441)
| 100 | 191 (18) | 1566 (72) | 1439 (37) | 1458 (90) | 22963 (649)
| 200 | 195 (13) | 1561 (65) | 1466 (82) | 1472 (92) | 44830 (1023)
| 500 | 373 (55) | 1428 (80) | 1475 (91) | 1349 (49) |
30 | 50 | 170 (8) | 2060 (125) | 1633 (113) | 1943 (141) | 16920 (715)
| 100 | 171 (11) | 2071 (98) | 1664 (80) | 1946 (142) | 33911 (1532)
| 200 | 233 (36) | 2051 (152) | 1675 (120) | 1980 (81) | 66665 (2266)
| 500 | 393 (46) | 1861 (97) | 1701 (92) | 1814 (63) |
40 | 50 | 177 (19) | 2566 (180) | 1846 (169) | 2442 (202) | 22409 (1109)
| 100 | 193 (18) | 2588 (168) | 1860 (154) | 2445 (124) | 43943 (1369)
| 200 | 266 (49) | 2605 (145) | 1898 (173) | 2478 (62) | 88300 (2367)
| 500 | 492 (63) | 2466 (111) | 1946 (127) | 2296 (109) |
50 | 50 | 163 (12) | 3149 (126) | 2095 (156) | 2887 (197) | 27940 (1348)
| 100 | 206 (18) | 3084 (214) | 2137 (134) | 2916 (137) | 55743 (1457)
| 200 | 320 (36) | 3110 (155) | 2169 (158) | 2935 (138) | 111393 (2884)
| 500 | 556 (74) | 2930 (95) | 2098 (61) | 2664 (100) |
Table 25: Running times (in seconds) of the evaluated algorithms on the
Caltech data set (with PCA preprocessing). Each cell specify the mean along
with the standard deviation in parenthesis of 10 repetitions of the
experiment. Running times on the Caltech data set (with PCA preprocessing)
---
$k$ |  $m$ | BICO |  Group Sampling | Ray Maker |  Sensitivity Sampling | StreamKM++
10 | 50 | 325 (16) | 1452 (112) | 1569 (174) | 1357 (153) | 6156 (268)
| 100 | 326 (25) | 1449 (118) | 1596 (135) | 1360 (114) | 11401 (454)
| 200 | 334 (27) | 1425 (161) | 1568 (222) | 1383 (113) | 21289 (1324)
| 500 | 386 (27) | 1386 (91) | 1685 (94) | 1357 (77) |
20 | 50 | 362 (26) | 1934 (179) | 1753 (166) | 1783 (223) | 10751 (914)
| 100 | 379 (29) | 1895 (222) | 1796 (128) | 1833 (143) | 20680 (1273)
| 200 | 403 (39) | 1951 (143) | 1855 (143) | 1784 (216) | 40903 (3138)
| 500 | 489 (28) | 1833 (162) | 1898 (154) | 1800 (71) |
30 | 50 | 346 (24) | 2401 (234) | 1999 (135) | 2257 (182) | 16026 (865)
| 100 | 373 (25) | 2443 (185) | 2011 (139) | 2276 (192) | 31501 (995)
| 200 | 422 (26) | 2430 (186) | 2019 (178) | 2277 (185) | 60330 (4284)
| 500 | 571 (35) | 2361 (97) | 2131 (89) | 2235 (61) |
40 | 50 | 355 (22) | 2870 (270) | 2144 (184) | 2748 (202) | 21992 (620)
| 100 | 399 (33) | 2904 (211) | 2204 (157) | 2710 (255) | 41273 (1086)
| 200 | 432 (35) | 2892 (273) | 2213 (177) | 2744 (215) | 79148 (6325)
| 500 | 595 (55) | 2852 (103) | 2337 (78) | 2593 (94) |
50 | 50 | 363 (23) | 3320 (323) | 2369 (200) | 3126 (316) | 26609 (600)
| 100 | 392 (33) | 3354 (293) | 2405 (195) | 3163 (287) | 51562 (2479)
| 200 | 432 (33) | 3405 (261) | 2445 (210) | 3156 (285) | 98934 (4995)
| 500 | 657 (47) | 3306 (122) | 2531 (111) | 3041 (162) |
Table 26: Running times (in seconds) of the evaluated algorithms on the Census
data set. Each cell specify the mean along with the standard deviation in
parenthesis of 10 repetitions of the experiment. Running times on the Census
data set
---
$k$ |  $m$ | BICO |  Group Sampling | Ray Maker |  Sensitivity Sampling | StreamKM++
10 | 50 | 47 (6) | 265 (33) | 300 (34) | 239 (37) | 1866 (176)
| 100 | 57 (2) | 318 (27) | 400 (15) | 291 (23) | 4080 (273)
| 200 | 61 (4) | 329 (18) | 438 (26) | 286 (29) | 8203 (231)
| 500 | 69 (4) | 314 (35) | 534 (36) | 281 (42) |
20 | 50 | 48 (5) | 444 (61) | 373 (49) | 401 (54) | 3584 (239)
| 100 | 55 (5) | 512 (40) | 474 (28) | 469 (12) | 8107 (529)
| 200 | 62 (4) | 498 (27) | 505 (25) | 450 (15) | 15862 (582)
| 500 | 83 (4) | 538 (26) | 624 (55) | 450 (37) |
30 | 50 | 47 (3) | 599 (73) | 448 (75) | 523 (79) | 4877 (259)
| 100 | 60 (4) | 698 (28) | 522 (27) | 607 (28) | 12061 (765)
| 200 | 66 (7) | 700 (23) | 593 (24) | 611 (35) | 23266 (1072)
| 500 | 99 (8) | 660 (67) | 684 (42) | 638 (38) |
40 | 50 | 50 (5) | 772 (103) | 503 (40) | 662 (85) | 6507 (372)
| 100 | 62 (4) | 881 (20) | 616 (35) | 783 (47) | 15837 (759)
| 200 | 73 (4) | 863 (32) | 655 (29) | 784 (59) | 31133 (1827)
| 500 | 135 (13) | 858 (87) | 779 (45) | 802 (51) |
50 | 50 | 51 (7) | 934 (84) | 574 (87) | 803 (98) | 7680 (467)
| 100 | 66 (3) | 1051 (32) | 694 (24) | 936 (76) | 19651 (747)
| 200 | 81 (3) | 1054 (37) | 730 (29) | 922 (74) | 38624 (1771)
| 500 | 172 (20) | 1062 (86) | 845 (39) | 977 (50) |
Table 27: Running times (in seconds) of the evaluated algorithms on the Census
data set (with PCA preprocessing). Each cell specify the mean along with the
standard deviation in parenthesis of 10 repetitions of the experiment. Running
times on the Census data set (with PCA preprocessing)
---
$k$ |  $m$ | BICO |  Group Sampling | Ray Maker |  Sensitivity Sampling | StreamKM++
10 | 50 | 103 (8) | 529 (38) | 535 (87) | 479 (40) | 2089 (224)
| 100 | 105 (8) | 505 (61) | 593 (49) | 481 (37) | 4153 (376)
| 200 | 106 (6) | 517 (40) | 630 (62) | 477 (45) | 7587 (443)
| 500 | 114 (10) | 483 (38) | 706 (54) | 463 (28) |
20 | 50 | 107 (7) | 702 (62) | 646 (48) | 635 (74) | 4037 (384)
| 100 | 110 (7) | 694 (71) | 667 (46) | 642 (58) | 8010 (410)
| 200 | 113 (7) | 701 (57) | 694 (58) | 647 (57) | 14984 (979)
| 500 | 140 (8) | 690 (30) | 775 (42) | 626 (29) |
30 | 50 | 112 (8) | 870 (94) | 701 (71) | 813 (62) | 5947 (492)
| 100 | 115 (7) | 879 (95) | 731 (64) | 815 (61) | 11560 (493)
| 200 | 122 (8) | 880 (96) | 761 (69) | 820 (62) | 22705 (935)
| 500 | 164 (6) | 891 (23) | 854 (45) | 800 (24) |
40 | 50 | 113 (6) | 1073 (92) | 769 (100) | 982 (72) | 8021 (395)
| 100 | 120 (10) | 1068 (108) | 816 (54) | 982 (74) | 15201 (854)
| 200 | 127 (12) | 1075 (91) | 824 (87) | 995 (75) | 29927 (2012)
| 500 | 199 (11) | 1063 (47) | 904 (57) | 938 (37) |
50 | 50 | 114 (11) | 1257 (96) | 861 (66) | 1155 (83) | 9655 (578)
| 100 | 121 (9) | 1244 (155) | 887 (70) | 1144 (91) | 19140 (1164)
| 200 | 134 (11) | 1266 (92) | 922 (68) | 1152 (87) | 36861 (2182)
| 500 | 243 (14) | 1225 (54) | 1007 (32) | 1113 (55) |
Table 28: Running times (in seconds) of the evaluated algorithms on the
Covertype data set. Each cell specify the mean along with the standard
deviation in parenthesis of 10 repetitions of the experiment. Running times on
the Covertype data set
---
$k$ |  $m$ | BICO |  Group Sampling | Ray Maker |  Sensitivity Sampling | StreamKM++
10 | 50 | 8 (1) | 58 (9) | 60 (8) | 50 (8) | 275 (37)
| 100 | 8 (1) | 61 (7) | 67 (9) | 48 (9) | 597 (69)
| 200 | 9 (1) | 57 (7) | 85 (9) | 51 (9) | 1322 (214)
| 500 | 12 (1) | 67 (7) | 123 (18) | 55 (5) |
20 | 50 | 9 (1) | 93 (13) | 70 (10) | 77 (12) | 580 (80)
| 100 | 9 (1) | 88 (8) | 81 (11) | 74 (12) | 1038 (183)
| 200 | 10 (1) | 93 (9) | 90 (11) | 79 (13) | 2603 (385)
| 500 | 19 (1) | 108 (7) | 131 (9) | 84 (9) |
30 | 50 | 8 (1) | 125 (15) | 84 (11) | 104 (18) | 888 (148)
| 100 | 10 (1) | 125 (13) | 87 (11) | 105 (19) | 1593 (211)
| 200 | 12 (2) | 125 (14) | 99 (14) | 105 (20) | 3755 (463)
| 500 | 25 (2) | 146 (10) | 139 (14) | 122 (8) |
40 | 50 | 8 (1) | 156 (19) | 97 (10) | 132 (23) | 1146 (89)
| 100 | 10 (1) | 158 (19) | 101 (19) | 132 (21) | 2251 (239)
| 200 | 14 (2) | 159 (20) | 120 (15) | 132 (21) | 5308 (681)
| 500 | 38 (4) | 189 (10) | 157 (15) | 147 (12) |
50 | 50 | 9 (1) | 191 (24) | 109 (20) | 153 (27) | 1467 (184)
| 100 | 11 (1) | 187 (20) | 114 (22) | 157 (27) | 2491 (318)
| 200 | 16 (3) | 186 (16) | 128 (20) | 163 (30) | 6057 (672)
| 500 | 48 (5) | 231 (10) | 181 (9) | 185 (12) |
Table 29: Running times (in seconds) of the evaluated algorithms on the
Covertype data set (with PCA preprocessing). Each cell specify the mean along
with the standard deviation in parenthesis of 10 repetitions of the
experiment. Running times on the Covertype data set (with PCA preprocessing)
---
$k$ |  $m$ | BICO |  Group Sampling | Ray Maker |  Sensitivity Sampling | StreamKM++
10 | 50 | 19 (2) | 100 (8) | 101 (10) | 86 (8) | 417 (45)
| 100 | 18 (1) | 99 (7) | 111 (9) | 84 (10) | 797 (58)
| 200 | 19 (1) | 98 (7) | 118 (14) | 87 (8) | 1579 (63)
| 500 | 22 (1) | 90 (10) | 148 (14) | 84 (7) |
20 | 50 | 19 (1) | 141 (10) | 116 (10) | 119 (9) | 781 (91)
| 100 | 19 (2) | 137 (13) | 122 (8) | 116 (11) | 1452 (186)
| 200 | 21 (2) | 136 (13) | 134 (7) | 115 (11) | 2958 (238)
| 500 | 29 (1) | 136 (12) | 160 (12) | 113 (8) |
30 | 50 | 19 (1) | 175 (18) | 132 (12) | 149 (15) | 1170 (97)
| 100 | 20 (2) | 175 (20) | 138 (13) | 154 (11) | 2198 (312)
| 200 | 23 (2) | 180 (15) | 146 (17) | 150 (13) | 4430 (307)
| 500 | 37 (3) | 174 (7) | 170 (14) | 145 (14) |
40 | 50 | 19 (1) | 214 (20) | 147 (12) | 181 (17) | 1455 (192)
| 100 | 22 (2) | 220 (18) | 149 (12) | 185 (12) | 2890 (301)
| 200 | 25 (2) | 222 (18) | 165 (13) | 185 (13) | 5686 (644)
| 500 | 47 (4) | 212 (11) | 196 (13) | 179 (16) |
50 | 50 | 20 (1) | 254 (29) | 160 (12) | 214 (18) | 1866 (180)
| 100 | 22 (2) | 264 (20) | 168 (13) | 211 (16) | 3840 (157)
| 200 | 29 (2) | 260 (20) | 177 (16) | 214 (17) | 7186 (493)
| 500 | 60 (4) | 254 (13) | 203 (13) | 203 (24) |
Table 30: Running times (in seconds) of the evaluated algorithms on the
NYTimes data set. Each cell specify the mean along with the standard deviation
in parenthesis of 10 repetitions of the experiment. Running times on the
NYTimes data set
---
$k$ |  $m$ | BICO |  Group Sampling | Ray Maker |  Sensitivity Sampling | StreamKM++
10 | 50 | 12 (2) | 58 (6) | 68 (3) | 56 (1) | 369 (19)
| 100 | 16 (5) | 54 (2) | 65 (4) | 49 (3) | 708 (42)
| 200 | 33 (7) | 51 (2) | 64 (2) | 49 (3) | 1373 (173)
| 500 | 107 (24) | 52 (6) | 76 (8) | 52 (4) |
20 | 50 | 20 (5) | 92 (5) | 84 (2) | 88 (3) | 670 (70)
| 100 | 36 (12) | 85 (6) | 75 (5) | 79 (6) | 1338 (112)
| 200 | 101 (29) | 79 (5) | 76 (4) | 78 (4) | 2681 (228)
| 500 | 374 (139) | 83 (9) | 86 (10) | 80 (8) |
30 | 50 | 25 (6) | 124 (4) | 97 (3) | 117 (4) | 1023 (89)
| 100 | 61 (21) | 111 (10) | 88 (4) | 109 (13) | 2032 (176)
| 200 | 178 (53) | 108 (5) | 90 (3) | 108 (14) | 3775 (342)
| 500 | 715 (456) | 110 (9) | 106 (8) | 112 (11) |
40 | 50 | 29 (15) | 156 (4) | 112 (4) | 149 (4) | 1432 (46)
| 100 | 86 (26) | 138 (10) | 100 (6) | 139 (17) | 2771 (168)
| 200 | 294 (65) | 135 (17) | 103 (2) | 137 (16) | 5548 (351)
| 500 | 1110 (401) | 140 (18) | 119 (10) | 138 (12) |
50 | 50 | 46 (15) | 180 (25) | 125 (4) | 181 (7) | 1689 (190)
| 100 | 114 (37) | 162 (20) | 115 (7) | 165 (15) | 3537 (48)
| 200 | 375 (136) | 168 (3) | 117 (7) | 163 (15) | 6464 (573)
| 500 | 886 (547) | 174 (11) | 131 (12) | 166 (17) |
Table 31: Running times (in seconds) of the evaluated algorithms on the
NYTimes data set (with PCA preprocessing). Each cell specify the mean along
with the standard deviation in parenthesis of 10 repetitions of the
experiment. Running times on the NYTimes data set (with PCA preprocessing)
---
$k$ |  $m$ | BICO |  Group Sampling | Ray Maker |  Sensitivity Sampling | StreamKM++
10 | 50 | 18 (0) | 28 (1) | 28 (0) | 26 (0) | 71 (3)
| 100 | 18 (0) | 28 (2) | 30 (1) | 25 (1) | 109 (17)
| 200 | 19 (0) | 28 (1) | 33 (1) | 26 (0) | 199 (19)
| 500 | 20 (0) | 29 (0) | 47 (4) | 26 (1) |
20 | 50 | 30 (0) | 51 (4) | 50 (1) | 49 (2) | 203 (3)
| 100 | 31 (0) | 54 (2) | 50 (3) | 50 (2) | 375 (6)
| 200 | 32 (0) | 55 (1) | 55 (1) | 50 (3) | 610 (74)
| 500 | 40 (1) | 54 (2) | 69 (2) | 51 (2) |
30 | 50 | 40 (0) | 79 (7) | 72 (4) | 77 (3) | 403 (14)
| 100 | 42 (0) | 83 (2) | 75 (3) | 78 (3) | 690 (107)
| 200 | 45 (1) | 80 (10) | 78 (3) | 77 (4) | 1258 (141)
| 500 | 68 (3) | 87 (3) | 92 (7) | 81 (3) |
40 | 50 | 49 (1) | 109 (11) | 94 (5) | 105 (6) | 624 (77)
| 100 | 52 (1) | 110 (12) | 93 (5) | 110 (3) | 1225 (75)
| 200 | 60 (1) | 109 (17) | 99 (4) | 104 (8) | 2055 (148)
| 500 | 114 (6) | 118 (10) | 118 (6) | 116 (3) |
50 | 50 | 61 (1) | 136 (23) | 123 (5) | 143 (10) | 995 (21)
| 100 | 66 (1) | 147 (20) | 121 (6) | 152 (9) | 1846 (151)
| 200 | 78 (3) | 133 (18) | 125 (5) | 145 (10) | 2980 (262)
| 500 | 183 (11) | 156 (19) | 150 (6) | 153 (7) |
Table 32: Running times (in seconds) of the evaluated algorithms on the Tower
data set. Each cell specify the mean along with the standard deviation in
parenthesis of 10 repetitions of the experiment. Running times on the Tower
data set
---
$k$ |  $m$ | BICO |  Group Sampling | Ray Maker |  Sensitivity Sampling | StreamKM++
20 | 50 | 8 (2) | 266 (12) | 66 (3) | 68 (2) | 685 (11)
| 100 | 8 (2) | 268 (13) | 91 (5) | 71 (4) | 1373 (14)
| 200 | 7 (1) | 268 (12) | 135 (12) | 71 (4) | 2746 (14)
| 500 | 8 (2) | 265 (8) | 268 (11) | 70 (2) |
40 | 50 | 8 (2) | 546 (10) | 92 (2) | 133 (5) | 1368 (21)
| 100 | 7 (1) | 552 (14) | 112 (2) | 134 (4) | 2747 (21)
| 200 | 8 (1) | 548 (14) | 155 (3) | 136 (5) | 5478 (35)
| 500 | 10 (2) | 547 (16) | 269 (7) | 136 (2) |
60 | 50 | 6 (1) | 831 (19) | 120 (3) | 195 (8) | 2050 (38)
| 100 | 7 (1) | 832 (14) | 139 (2) | 199 (6) | 4121 (88)
| 200 | 7 (1) | 842 (13) | 183 (2) | 201 (5) | 8162 (253)
| 500 | 14 (4) | 835 (17) | 306 (8) | 202 (5) |
80 | 50 | 7 (2) | 1125 (20) | 148 (3) | 261 (6) | 2730 (89)
| 100 | 8 (2) | 1125 (12) | 167 (4) | 263 (6) | 5354 (281)
| 200 | 9 (2) | 1129 (21) | 211 (6) | 267 (5) | 10819 (514)
| 500 | 20 (4) | 1122 (14) | 340 (11) | 269 (5) |
100 | 50 | 7 (2) | 1419 (22) | 175 (6) | 324 (8) | 3403 (36)
| 100 | 8 (1) | 1434 (21) | 198 (3) | 327 (7) | 6859 (120)
| 200 | 10 (1) | 1428 (15) | 241 (7) | 330 (7) | 13530 (475)
| 500 | 28 (7) | 1444 (9) | 384 (10) | 338 (5) |

##  Appendix F Generating Candidate Solutions

As mentioned in Section 4, it is difficult to construct a candidate solution
consisting of $k$ centers which yields a maximal distortion. We experimented
with three methods for candidate solution generation; find $k$ centers via
$k$-means++, randomly generate $k$ points inside the convex hull (Random CH),
and randomly generate $k$ points inside the minimum enclosing ball (Random
MEB). Our experiments show that the $k$-means++ method generates candidate
solutions which consistently result in large distortions across all algorithms
and data sets. The numerical results are presented in LABEL:tab:comparison-
solution-generation-all. Notice that the the numbers in LABEL:tab:comparison-
solution-generation-all are the maximum distortions across $k$ and $m$ because
we are only interesting in determining which of the three methods is superior.
LABEL:tab:comparison-solution-generation-caltech-bico shows all the numbers
for BICO on the Caltech data set. For all the other combinations of algorithms
and data sets, the takeaway message is virtually the same; $k$-means++ is the