  Clustering is a fundamental tool for analyzing large data sets. A rich body
of work has been devoted to designing data-stream algorithms for the relevant
optimization problems such as $k$-center, $k$-median, and $k$-means. Such
algorithms need to be both time and and space efficient. In this paper, we
address the problem of correlation clustering in the dynamic data stream model.
The stream consists of updates to the edge weights of a graph on $n$ nodes and
the goal is to find a node-partition such that the end-points of
negative-weight edges are typically in different clusters whereas the
end-points of positive-weight edges are typically in the same cluster. We
present polynomial-time, $O(n\cdot \ \mbox{polylog}~n)$-space approximation
algorithms for natural problems that arise.
  We first develop data structures based on linear sketches that allow the
"quality" of a given node-partition to be measured. We then combine these data
structures with convex programming and sampling techniques to solve the
relevant approximation problem. Unfortunately, the standard LP and SDP
formulations are not obviously solvable in $O(n\cdot \mbox{polylog}~n)$-space.
Our work presents space-efficient algorithms for the convex programming
required, as well as approaches to reduce the adaptivity of the sampling.
