
of size linear in \(k\)  (for \(d>\log k\) ) and arbitrary metric space of dimension \(d\) . Current coresets that are subset of the input have size at least cubic in \(k\)  [1]}. This is by reducing the total sensitivity to \(O(1)\)  without introducing negative weights that might be conditioned on the queries as in [2]}.

of size independent of \(d\)  for the Euclidean case of \(k\) -means (squared distances). This is particular useful for sparse input set of points where \(d\ge n\) , such as in adjacency matrices of graphs, document-term, or image-object matrices. Recent coreset for sparse \(k\) -means of [3]} is of size exponential in \(1/\varepsilon \)  and thus turn to \(O(n)\)  when used when the merge-and-reduce tree (where \(\varepsilon \)  is replaced by \(O(\varepsilon /\log (n))\) . The result of [4]} for \(k\) -means is exponential in \(k/\varepsilon \)  and fails with constant probability, so also cannot be used with streaming. Another result of [4]} suggests a coreset type set for \(k\) -means of size \(O(k/\varepsilon )\)  but which is based on projections that loss the sparsity of the data. Similar sparsity loss occurs with other projection-type compression methods e.g. in [6]}. Nevertheless, we use the technique in [4]} to bound the dimension of the \(k\) -means problem by \(O(k/\varepsilon )\) .

of size independent of \(d\)  for the Euclidean case, and non-squared distances, using weak coresets. These coresets can be used to approximates the optimal solution, but not every set of \(k\)  centers. Unlike the weak coresets in [2]}, [9]}, we can use any existing heuristic on these coresets, as explained in Section REF .

Robust to outliers. This is since the general pseudo-metric definition we used (inspired by [10]}, support \(m\) -estimators which is a tool for handling outliers [11]}. Unlike in [10]} our coresets are linear (and not exponential) in \(k\) , and also independent of \(n\)  (and not logarithmic in \(n\) ).

