The coreset technique is a “dataset compression” mechanism, aiming to reduce the dependency on \(n\) . From the \(n\)  points \(P \subset ^d\) , an algorithm computes a much smaller (weighted) set of points \(S \subset ^d\) , \(w\colon S \rightarrow _{\ge 0}\) , such that the cost of clustering the weighted points \(S, w\)  approximates that of \(P\) . Following a long line of work [1]}, [2]}, [3]}, [4]}, [5]}, [6]}, [7]}, [8]}, [9]}, [10]}, [11]}, the best coreset constructions for \((k,z)\) -clustering in \(\ell _p\)  achieve sizes \(\tilde{O}(k / ^4) \cdot \min \lbrace  1/^{z-2}, k\rbrace \)  for a \((1\pm )\) -approximation. The ensuing streaming and distributed-memory algorithms maintain a coreset of the input; these algorithms find (approximately) optimal centers \(c_1,\dots , c_k \in ^d\)  and use space complexity \(d \cdot \tilde{O}(k/^4) \cdot \min \lbrace 1/^{z-2}, k\rbrace  \cdot (n)\) .The \(\log n\) -factors arise from utilizing the “merge-and-reduce” framework for maintaining coresets on a stream [12]}, [3]}, and the fact the coreset constructions are randomized.
