  We consider the problem of maximizing a nonnegative submodular set function
$f:2^{\mathcal{N}} \rightarrow \mathbb{R}^+$ subject to a $p$-matchoid
constraint in the single-pass streaming setting. Previous work in this context
has considered streaming algorithms for modular functions and monotone
submodular functions. The main result is for submodular functions that are {\em
non-monotone}. We describe deterministic and randomized algorithms that obtain
a $\Omega(\frac{1}{p})$-approximation using $O(k \log k)$-space, where $k$ is
an upper bound on the cardinality of the desired set. The model assumes value
oracle access to $f$ and membership oracles for the matroids defining the
$p$-matchoid constraint.
