The Library
Correlation clustering in data streams
Tools
Tools
Tools
Ahn, Kook Jin, Cormode, Graham, Guha, Sudipto, McGregor, Andrew and Wirth, Anthony (2021) Correlation clustering in data streams. Algorithmica, 83 . pp. 1980-2017. doi:10.1007/s00453-021-00816-9 ISSN 0178-4617.
|
PDF
WRAP-correlation-clustering-data-streams-Cormode-2021.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (3043Kb) | Preview |
|
![[img]](http://wrap.warwick.ac.uk/style/images/fileicons/application_pdf.png) |
PDF
WRAP-correlation-clustering-data-streams-Cormode-2021.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (863Kb) |
Official URL: https://doi.org/10.1007/s00453-021-00816-9
Abstract
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⋅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⋅polylogn)-space. Our work presents space-efficient algorithms for the convex programming required, as well as approaches to reduce the adaptivity of the sampling.
| Item Type: | Journal Article | ||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||||||||||||||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||||||||||||||||||
| Library of Congress Subject Headings (LCSH): | Correlation (Statistics) -- Computer programs, Data mining, Algorithms, Database management, Computer science -- Mathematics, Linear programming | ||||||||||||||||||||||||
| Journal or Publication Title: | Algorithmica | ||||||||||||||||||||||||
| Publisher: | Springer Verlag | ||||||||||||||||||||||||
| ISSN: | 0178-4617 | ||||||||||||||||||||||||
| Official Date: | July 2021 | ||||||||||||||||||||||||
| Dates: |
|
||||||||||||||||||||||||
| Volume: | 83 | ||||||||||||||||||||||||
| Page Range: | pp. 1980-2017 | ||||||||||||||||||||||||
| DOI: | 10.1007/s00453-021-00816-9 | ||||||||||||||||||||||||
| Status: | Peer Reviewed | ||||||||||||||||||||||||
| Publication Status: | Published | ||||||||||||||||||||||||
| Access rights to Published version: | Open Access (Creative Commons) | ||||||||||||||||||||||||
| Date of first compliant deposit: | 19 March 2021 | ||||||||||||||||||||||||
| Date of first compliant Open Access: | 16 April 2021 | ||||||||||||||||||||||||
| RIOXX Funder/Project Grant: |
|
||||||||||||||||||||||||
| Is Part Of: | 1 | ||||||||||||||||||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
