
The requirement that \(p \le 2\)  is necessary for the exponential compression we desire. For \(p > 2\) , there are strong lower bounds for sketching distances which show that such sketches require \(\Omega (d^{1-2/p})\)  space [1]}. For \(p < 1\) , we are not aware of small coresets.

The focus of this work is on optimizing the space complexity of the sketch, and while we do not explicitly specify the running time of the sketching and streaming algorithms, a naive implementation runs in time \((k\log (nd) / )^{(k\log n/)^{O(1)}}\) . The exponential factor is due to the fact that we evaluate the cost of all possible partitions of the \((k\log (n)/)^{O(1)}\) -coreset points into \(k\)  clusters. One could alleviate the exponential dependence to \((k/)^{O(1)}\)  (as opposed to \((k \log n/)^{O(1)}\) ) by running more sophisticated approximation algorithms [2]}, [3]} on the sketched representation of the coreset.The one subtlety is that the algorithm should be implemented without explicitly considering the \(d\) -dimensional representation of the points. Instead, it should only use the sketches of Theorem REF . We note that a super-polynomial dependence on \(k\)  should is unavoidable, because \((1\pm )\) -approximations for \((k,z)\) -clustering problems, for non-constant \(k\) , are NP-hard [4]}, [5]}, [6]}.

It would be interesting to generalize Theorem REF  to dynamic streams. The reason our algorithm works in the insertion-only model is that we utilize the coreset of [7]} with the merge-and-reduce framework [8]}, [9]} which do not support deletions. While there exist dynamic coreset constructions for the streaming model [10]}, [11]}, our use of coresets is not entirely black-box. Other dynamic coresets, like [12]}, focus on update time and do not optimize the space complexity. We must ensure that the algorithm for constructing the coreset does not utilize the \(d\) -dimensional representation of the dataset points. The coreset construction of [7]} only consider distances between the dataset points, so it suffices for us to only maintain a sketch of the dataset points.

The fact that \(z = p\)  in our theorems above is a consequence of our techniques. It is unclear to us whether this assumption is necessary, although our approach hinges on the fact \(\ell _p^p\)  is additive over the \(d\)  coordinates. We leave this as a problem for future work.

