Stream Clipper: Scalable Submodular Maximization on Stream

arXiv1606.00389MaRDI QIDQ6274191FDOQ6274191

Authors: Tianyi Zhou, Jeff A. Bilmes 

Publication date: 1 June 2016

Abstract: 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.

This page was built for publication: Stream Clipper: Scalable Submodular Maximization on Stream

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6274191)