Correlation Clustering in Data Streams

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...

Full description

Saved in:
Bibliographic Details
Published in:Algorithmica 2021-07, Vol.83 (7), p.1980-2017
Main Authors: Ahn, Kook Jin, Cormode, Graham, Guha, Sudipto, McGregor, Andrew, Wirth, Anthony
Format: Article
Language:English
Subjects:
Algorithm Analysis and Problem Complexity
Algorithms
Approximation
Clustering
Computational geometry
Computer Science
Computer Systems Organization and Communication Networks
Convexity
Data structures
Data Structures and Information Theory
Data transmission
Mathematical analysis
Mathematical programming
Mathematics of Computing
Optimization
Partitions (mathematics)
Polynomials
Sampling methods
Sketches
Theory of Computation
Weight
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 · 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 · 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.
ISSN:0178-4617
1432-0541
DOI:10.1007/s00453-021-00816-9