Submodular Streaming in All Its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity
[edit]
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:33113320, 2019.
Abstract
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 SIEVESTREAMING++, which requires just one pass over the data, keeps only $O(k)$ elements and achieves the tight $\frac{1}{2}$approximation guarantee. The best previously known streaming algorithms either achieve a suboptimal $\frac{1}{4}$approximation with $\Theta(k)$ memory or the optimal $\frac{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 SIEVESTREAMING++. We then generalize our results to the more challenging multisource streaming setting. We show how one can achieve the tight $\frac{1}{2}$approximation guarantee with $O(k)$ shared memory, while minimizing not only the rounds of computations but also the total number of communicated bits. Finally, we demonstrate the efficiency of our algorithms on realworld data summarization tasks for multisource streams of tweets and of YouTube videos.
Related Material


