Streaming Euclidean k-median and k-means with o(log n) Space

We consider the classic Euclidean k-median and k-means objective on data streams, where the goal is to provide a $(1+\varepsilon)$-approximation to the optimal k-median or k-means solution, while using as little memory as possible. Over the last 20 years, clustering in data streams has received a tremendous amount of attention and has been the test-bed for a large variety of new techniques, including coresets, the merge-and-reduce framework, bicriteria approximation, sensitivity sampling, and so on. Despite this intense effort to obtain smaller sketches for these problems, all known techniques require storing at least $\Omega(\log (n \Delta))$ words of memory, where n is size of the input and $\Delta$ is the aspect ratio. A natural question is if one can beat this logarithmic dependence on n and $\Delta$. In this paper, we break this barrier by first giving an insertion-only streaming algorithm that achieves a $(1+\varepsilon)$-approximation to the more general $(k, z)$-clustering problem, using $\tilde{\mathcal{O}}\left(\frac{d k}{\varepsilon^{2}}\right) \cdot\left(2^{z \log z}\right) \cdot \min \left(\frac{1}{\varepsilon^{z}}, k\right) \cdot \operatorname{poly}(\log \log (n \Delta))$ words of memory. Our techniques can also be used to achieve two-pass algorithms for k-median and k-means clustering on dynamic streams using $\tilde{\mathcal{O}}\left(\frac{1}{\varepsilon^{2}}\right) \cdot \operatorname{poly}(d, k, \log \log (n \Delta))$ words of memory.