  We study the classic NP-Hard problem of finding the maximum $k$-set coverage
in the data stream model: given a set system of $m$ sets that are subsets of a
universe $\{1,\ldots,n \}$, find the $k$ sets that cover the most number of
distinct elements. The problem can be approximated up to a factor $1-1/e$ in
polynomial time. In the streaming-set model, the sets and their elements are
revealed online. The main goal of our work is to design algorithms, with
approximation guarantees as close as possible to $1-1/e$, that use sublinear
space $o(mn)$. Our main results are:
  Two $(1-1/e-\epsilon)$ approximation algorithms: One uses $O(\epsilon^{-1})$
passes and $\tilde{O}(\epsilon^{-2} k)$ space whereas the other uses only a
single pass but $\tilde{O}(\epsilon^{-2} m)$ space.
  We show that any approximation factor better than $(1-(1-1/k)^k)$ in constant
passes requires $\Omega(m)$ space for constant $k$ even if the algorithm is
allowed unbounded processing time. We also demonstrate a single-pass,
$(1-\epsilon)$ approximation algorithm using $\tilde{O}(\epsilon^{-2} m \cdot
\min(k,\epsilon^{-1}))$ space.
  We also study the maximum $k$-vertex coverage problem in the dynamic graph
stream model. In this model, the stream consists of edge insertions and
deletions of a graph on $N$ vertices. The goal is to find $k$ vertices that
cover the most number of distinct edges.
  We show that any constant approximation in constant passes requires
$\Omega(N)$ space for constant $k$ whereas $\tilde{O}(\epsilon^{-2}N)$ space is
sufficient for a $(1-\epsilon)$ approximation and arbitrary $k$ in a single
pass.
  For regular graphs, we show that $\tilde{O}(\epsilon^{-3}k)$ space is
sufficient for a $(1-\epsilon)$ approximation in a single pass. We generalize
this to a $(\kappa-\epsilon)$ approximation when the ratio between the minimum
and maximum degree is bounded below by $\kappa$.
