# Deterministic Coresets for \(k\)-Means of Big Sparse Data +
## 2 Related Work
### Importance Sampling  
Following a decade of research, coreset of size polynomial in \(d\) were suggested by [9]. Ref [10] suggested an improved version of size \(O(dk^{2}/\epsilon^{2})\) in which is a special case of the algorithms proposed by [11]. The construction is based on computing an approximation to the \(k\)-means of the input points (with no constraints on the centers) and then sample points proportionally to their distance to these centers. Each chosen point is then assigned a weight that is inverse proportional to this distance. The probability of failure in these algorithms reduces exponentially with the input size. Coresets of size \(O(dk/\epsilon^{2})\), i.e., linear in \(k\), were suggested in work of [12], however the weight of a point may be negative or a function of the given query. For the special case \(k=1\), [PERSON] et al. [13], provided constructions of coresets of size \(O(1/\epsilon^{2})\) using uniform sampling.  
**Projection based coresets.** Data summarization which are similar to coresets of size \(O(k/\epsilon)\) that are based on projections on low-dimensional subspaces that diminishes the sparsity of the input data were suggested by [14] by improving the analysis of [4]. Recently [15] improves both on [4,14] by applying Johnson-Lindenstrauss Lemma [16] on construction from [4]. However, due to the  
Figure 1: Coresets construction from data streams [2]. The black arrows indicate “merge-and-reduce” operations. The intermediate coresets \(C_{1},\ldots,C_{7}\) are numbered in the order in which they would be generated in the streaming case. In the parallel case, \(C_{1},C_{2},C_{4}\) and \(C_{5}\) would be constructed in parallel, followed by \(C_{3}\) and \(C_{6}\), finally resulting in \(C_{7}\). The Figure is from [7].  
projections, the resulting summarizations of all works mentioned above are not subset of the input points, unlike the coreset definition of this paper. In particular, for sparse data sets such as adjacency matrix of a graphs, documents-term matrix of Wikipedia, or images-objects matrix, the sparsity of the data diminishes and a single point in the summarization might be larger than the complete sparse input data.  
Other type of weak coresets approximates only the optimal solution, and not every \(k\) centers. Such randomized coresets of size independent of \(d\) and only polynomial in \(k\) were suggested by [11] and simplified by [12].  
**Deterministic Constructions.** The first coresets for \(k\)-means [2; 17] were based on partitioning the data into cells, and take a representative point from each cell to the coreset, as is done in hashing or Hough transform [18]. However, these coresets are of size at least \(k/\epsilon^{O(d)}\), i.e., exponential in \(d\), while still providing result which is a sub-set of the the input in contrast to previous work [17]. While, our technique is most related to the deterministic construction that was suggested in [4] by recursively computing \(k\)-means clustering of the input points. While the output set has size independent of \(d\), it is not a coreset as defined in this paper, since it is not a subset of the input and thus cannot handle sparse data as explained above. Techniques such as uniform sampling for each cluster yields coresets with probability of failure that is linear in the input size, or whose size depends on \(d\).  
\(m\)**-means is a coreset for \(k\)-means?** A natural approach for coreset construction, that is strongly related to this paper, is to compute the \(m\)-means of the input set \(P\), for a sufficiently large \(m\), where the weight of each center is the number of point in its cluster. If the sum of squared distances to these \(m\)-centers is about \(\varepsilon\) factor from the \(k\)-means, we obtain a \((k,\varepsilon)\)-coreset by (a weaker version of) the triangle inequality. Unfortunately, it was recently proved in [19] that there exists sets such that \(m\in k^{\Omega(d)}\) centers are needed in order to obtain this small sum of squared distances.