Prior to the current work, the merge-and-reduce technique due to Har-Peled and Mazumdar [1]} and Bentley and Sax [2]} was used to maintain a coreset on an insertion-only stream. For a summary of this technique, see Section  in the Appendix.
In this paper we introduce an alternative technique that reduces the multiplicative overhead from \(\log ^{2a+1} n\)  to \(\log n\)  (here, \(a\)  is the offline construction's dependence on \(1/\epsilon \) ). While our method is not as general as merge-and-reduce (it requires that the function in question satisfies more than just the “merge” and “reduce” properties, defined in Section ), it is general enough to apply to all \(M\) -estimators. For the special case of our coreset offline construction for \(M\) -estimators (introduced in Section ), we use a more tailored method that causes this to be \(\log n\)  additive overhead. Therefore our streaming space complexity matches our offline space complexity, both of which improve upon the state-of-the-art.
