Ahn, Kook-Jin, Cormode, Graham, Guha, Sudipto, McGregor, Andrew and Wirth, Anthony Ian (2015) Correlation clustering in data streams. In: International Conference on Machine Learning, Lille, France, 6-11 Jul 2015. Published in: Proceedings of the 32nd International Conference on Machine Learning, 37 pp. 2237-2246. doi:10.5555/3045118.3045356
Preview |
PDF
WRAP-correlation-clustering-data-streams-Cormode-2017.pdf - Accepted Version - Requires a PDF viewer. Download (700kB) | Preview |
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 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.
| Item Type: | Conference Item (Paper) |
|---|---|
| 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): | Cluster analysis -- Computer programs, Correlation (Statistics), Streaming technology (Telecommunications) |
| Journal or Publication Title: | Proceedings of the 32nd International Conference on Machine Learning |
| Publisher: | ML Research Press |
| Official Date: | 2015 |
| Dates: | Date Event 2015 Available 25 April 2015 Accepted |
| Volume: | 37 |
| Page Range: | pp. 2237-2246 |
| DOI: | 10.5555/3045118.3045356 |
| Status: | Peer Reviewed |
| Publication Status: | Published |
| Access rights to Published version: | Open Access (Creative Commons open licence) |
| Date of first compliant deposit: | 29 June 2016 |
| Date of first compliant Open Access: | 29 June 2016 |
| Funder: | Royal Society (Great Britain). Wolfson Research Merit Award (RSWRMA), Yahoo! Research Labs, National Science Foundation (U.S.) (NSF), Google (Firm), Australian Research Council (ARC) |
| Grant number: | CCF-1117216 (NSF), CCF-0953754 (NSF), CCF-1320719 (NSF), IIS-1251110 (NSF), FT120100307 (ARC) |
| Conference Paper Type: | Paper |
| Title of Event: | International Conference on Machine Learning |
| Type of Event: | Conference |
| Location of Event: | Lille, France |
| Date(s) of Event: | 6-11 Jul 2015 |
| Related URLs: | |
| URI: | https://wrap.warwick.ac.uk/74439/ |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |