We now briefly introduce the previous technique for maintaining coresets in the streaming setting due to Har-Peled and Mazumdar [1]} and Bentley and Sax [2]}.
In this method, a merge-and-reduce tree is built by using an offline coreset construction as a blackbox. Previously merge-and-reduce was the only known technique for building a streaming coreset for metric \(k\) -median, and it relies solely on the following two properties:
