  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.
