Correlation Clustering in Data Streams

In this paper, we address the problem of cor-relation 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 ·polylog n)-space approxi-mation 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 approx-imation problem. However the standard LP and SDP formulations are not obviously solvable in O(n ·polylog n)-space. Our work presents space-efficient algorithms for the convex programming required, as well as approaches to reduce the adap-tivity of the sampling. Note that the improved space and running-time bounds achieved from streaming algorithms are also useful for offline settings such as MapReduce models