  Streaming algorithms are generally judged by the quality of their solution,
memory footprint, and computational complexity. In this paper, we study the
problem of maximizing a monotone submodular function in the streaming setting
with a cardinality constraint $k$. We first propose Sieve-Streaming++, which
requires just one pass over the data, keeps only $O(k)$ elements and achieves
the tight $(1/2)$-approximation guarantee. The best previously known streaming
algorithms either achieve a suboptimal $(1/4)$-approximation with $\Theta(k)$
memory or the optimal $(1/2)$-approximation with $O(k\log k)$ memory. Next, we
show that by buffering a small fraction of the stream and applying a careful
filtering procedure, one can heavily reduce the number of adaptive
computational rounds, thus substantially lowering the computational complexity
of Sieve-Streaming++. We then generalize our results to the more challenging
multi-source streaming setting. We show how one can achieve the tight
$(1/2)$-approximation guarantee with $O(k)$ shared memory while minimizing not
only the required rounds of computations but also the total number of
communicated bits. Finally, we demonstrate the efficiency of our algorithms on
real-world data summarization tasks for multi-source streams of tweets and of
YouTube videos.
