The streaming algorithm of [1]} provides a bicriterion solution using \(O(k \log n)\)  space. Our new offline construction of Section  requires \(O(\epsilon ^{-2} k \log k \log n)\)  space. Therefore our main theorem yields a streaming algorithm that combines these spaces additively, therefore requiring \(O(\epsilon ^{-2} k \log k \log n )\)  space while maintaining a coreset for \(k\) -means clustering. The previous state-of-the-art framework that works for the metric variant (other methods are known to improve upon this for the special case of Euclidean space) was the merge-and-reduce technique [2]} that yields a streaming algorithm requiring \(O(\epsilon ^{-4} k \log k \log ^6 n)\)  space, incurring an overhead of \(\Theta (\log ^{5} n)\)  over the offline coreset size. In comparison, our framework incurs no overhead. The additional improvement in our space is due the improved offline construction given in Sections 5-7.
