Space-Optimal Streaming Algorithms via Efficient Encodings

We study the problem of constructing coresets on data streams: Given a dataset of $n$ points in ${\mathbb{R}}^d$ arriving sequentially, the goal is to maintain a small weighted subset that accurately approximates the objective values of the entire dataset for a given class of query functions. Previous methods like merge-and-reduce and online sensitivity sampling required more space than the size of an optimal such subset in the offline setting. In this work, we show that such overheads are not necessary by presenting space-optimal streaming algorithms for central high-dimensional optimization problems such as Euclidean $(k,z)$-clustering and $L_p$ subspace embeddings, as well as applications to projection-cost preserving sketches. For $(k,z)$-clustering, our streaming algorithm uses memory independent of the number $n$ of input points (in words of memory) and the aspect ratio $\Delta$, yielding a coreset with an optimal $\tilde{\mathcal{O}}\left(\frac{dk}{\min ({\epsilon }^4,{\epsilon }^{z+2})}\right)$ words of memory for accuracy parameter $\epsilon \in (0,1)$. For $L_p$ subspace embeddings, where the rows of matrix $\mathbf{A}\in {\mathbb{R}}^{n\times d}$ arrive in an insertion-only stream, we achieve an efficient algorithm that uses optimal space for different ranges of $p$: $\tilde{\mathcal{O}}\left(\frac{d^2}{{\epsilon }^2}\right)$ words for $p\le 2$ and $\tilde{\mathcal{O}}\left(\frac{d^{p/2+1}}{{\epsilon }^2}\right)$ words for $p>2$, both independent of the number of rows $n$. Thus, our work shows that streaming algorithms can match offline algorithms in space complexity.