Correlation Clustering in Data Streams

被引:5
作者
Ahn, Kook Jin [1 ]
Cormode, Graham [2 ]
Guha, Sudipto [1 ]
McGregor, Andrew [3 ]
Wirth, Anthony [4 ]
机构
[1] Univ Penn, Philadelphia, PA 19104 USA
[2] Univ Warwick, Coventry, W Midlands, England
[3] Univ Massachusetts, Amherst, MA 01003 USA
[4] Univ Melbourne, Sch Comp & Informat Syst, Parkville, Vic, Australia
基金
欧洲研究理事会; 澳大利亚研究理事会;
关键词
Correlation clustering; Data streams; Linear sketches; Linear programming; PROBABILISTIC COMMUNICATION COMPLEXITY; ALGORITHMS;
D O I
10.1007/s00453-021-00816-9
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
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 center dot polylogn)-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 center dot polylogn)-space. Our work presents space-efficient algorithms for the convex programming required, as well as approaches to reduce the adaptivity of the sampling.
引用
收藏
页码:1980 / 2017
页数:38
相关论文
共 51 条