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 $\alpha$ under a collection of independence systems ${\cal I}$,
provides a constant $1/\big(1+2/\sqrt{\alpha}+1/\alpha
+2d(1+\sqrt{\alpha})\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.

本文提出了第一个高效的单遍流式计算算法 Streaming Local Search，用于在独立系统和多重背包约束下，同时最大化非单调子模函数，解决实时提取和总结大规模视频流的问题。