[edit]
Submodular Streaming in All Its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:3311-3320, 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 SIEVE-STREAMING++, which requires just one pass over the data, keeps only O(k) elements and achieves the tight 12-approximation guarantee. The best previously known streaming algorithms either achieve a suboptimal 14-approximation with Θ(k) memory or the optimal 12-approximation with O(klogk) 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 12-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 real-world data summarization tasks for multi-source streams of tweets and of YouTube videos.