Abstract

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 presen polynomial-time, O(n · 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 nodepartition to be measured. We then combine these data structures with convex programming and sampling techniques to solve the relevant approximation problem. However the standard LP and SDP formulations are not obviously solvable in O(n · polylog n)-space. Our work presents spaceefficient 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. 1 Currently at Google, Inc. Email:kookjin@google.com Proceedings of the 32 nd International Conference on MachLearning, Lille, France, 2015. JMLR: W&CP volume 37. Copyright 2015 by the author(s).