## K. J. Ahn, G. Cormode, S. Guha, A. McGregor, and A. Wirth.
Correlation clustering in data streams.
In *International Conference on Machine Learning, ICML*, pages
2237-2246, 2015.

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*·*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.
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 adaptivity 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.

[ bib |
.html |
.pdf ]
Back

*This file was generated by
bibtex2html 1.92.*