2016/06/01 by Tianyi Zhou, Zhou, Tianyi, Jeff Bilmes +1
Computer Science · #Algorithms and Data Compression #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Computer and information sciences #FOS: Mathematics #Internet Traffic Analysis and Secure E-voting #Machine Learning (cs.LG) #Machine Learning (stat.ML)
paper · pdf · doi:10.48550/arxiv.1606.00389
openalex publication_date 2016/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We propose a streaming submodular maximization algorithm "stream clipper" that performs as well as the offline greedy algorithm on document/video summarization in practice. It adds elements from a stream either to a solution set S or to an extra buffer B based on two adaptive thresholds, and improves S by a final greedy step that starts from S adding elements from B. During this process, swapping elements out of S can occur if doing so yields improvements. The thresholds adapt based on if current memory utilization exceeds a budget, e.g., it increases the lower threshold, and removes from the buffer B elements below the new lower threshold. We show that, while our approximation factor in the worst case is 1/2 (like in previous work, and corresponding to the tight bound), we show that there are data-dependent conditions where our bound falls within the range [1/2, 1-1/e]. In news and video summarization experiments, the algorithm consistently outperforms other streaming methods, and, while using significantly less computation and memory, performs similarly to the offline greedy algorithm.