The offline coreset construction of [1]} has the following structure: first, a bicriterion approximation is computed. Second, points are sampled according a distribution that depends only on the distances between points of the input and their assigned bicriterion centers.
This suggests a two-pass streaming algorithm (which we later combine into a single pass): in the first pass, construct a bicriterion using an algorithm such as [2]}. In the second pass, sample according to the bicriterion found in the first pass.
This provides a two-pass algorithm for a coreset using \(O(\epsilon ^{-2} k \log k \log n)\) -space. Our contribution is showing how these two passes can be combined into a single-pass. Using the algorithm of [2]} to output \(O(k \log n)\)  centers at any time, we show that this is sufficient to carry out the sampling (originally in the second pass) in parallel without re-reading the stream.
Our main lemma (Lemma REF ) shows that the bicriterion, rather than just providing “central” points to concentrate the sampling, actually can be thought of as a proof of the importance of points for the coreset (technically, a bound on the “sensitivity” that we define at the beginning of Section ). Moreover, the importance of points is non-increasing as the stream progresses, so we can maintain a sample in the streaming setting without using any additional space.
