Streaming Non-monotone Submodular Maximization: Personalized Video Summarization on the Fly
This addresses the need for real-time data stream analysis in applications like video summarization, offering a significant speed improvement for personalized and privacy-constrained optimization.
The paper tackles the problem of maximizing non-monotone submodular functions in streaming settings, such as personalized video summarization, by developing a single-pass algorithm that provides a constant approximation guarantee and runs over 1700 times faster than prior methods while maintaining similar performance.
The need for real time analysis of rapidly producing data streams (e.g., video and image streams) motivated the design of streaming algorithms that can efficiently extract and summarize useful information from massive data "on the fly". Such problems can often be reduced to maximizing a submodular set function subject to various constraints. While efficient streaming methods have been recently developed for monotone submodular maximization, in a wide range of applications, such as video summarization, the underlying utility function is non-monotone, and there are often various constraints imposed on the optimization problem to consider privacy or personalization. We develop the first efficient single pass streaming algorithm, Streaming Local Search, that for any streaming monotone submodular maximization algorithm with approximation guarantee $α$ under a collection of independence systems ${\cal I}$, provides a constant $1/\big(1+2/\sqrtα+1/α+2d(1+\sqrtα)\big)$ approximation guarantee for maximizing a non-monotone submodular function under the intersection of ${\cal I}$ and $d$ knapsack constraints. Our experiments show that for video summarization, our method runs more than 1700 times faster than previous work, while maintaining practically the same performance.