While processing the stream, we maintain a coreset \(S \subset [n]\)  with weights \(w \colon S \rightarrow _{\ge 0}\)  by using the merge-and-reduce framework of Bentley and Saxe [1]} for the streaming model. We maintain the \(\ell _p\) -sketch of \(x_i\)  and the \(O(M^2)\)  vectors \(_j^{(m)} x_i\)  for all \(m \in [M]\)  and \(j \in [m]\)  whenever \(i \in S\) . If \(i \notin S\) , we no longer maintain the \(\ell _p\) -sketch or the vectors \(_j^{(m)} x_i\) . This ensures that the total space complexity is \((\log (nd), k, 1/)\)  because we store: 1) \(O(M^3)\)  vectors in \(^s\) , since there are \(M\)  points in the coreset, and each \(i \in S\)  stores the \(O(M^2)\)  vectors \(^{(m)}_j x_i \in ^s\) , 2) the weights \(w(i)\)  for each \(i \in S\) , and 3) the \(\ell _p\) -sketches for the points \(x_i\) .
