Loading…
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...
Saved in:
| Published in: | Algorithmica 2021-07, Vol.83 (7), p.1980-2017 |
|---|---|
| Main Authors: | , , , , |
| Format: | Article |
| Language: | English |
| Subjects: | |
| 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!
|
| cited_by | cdi_FETCH-LOGICAL-c363t-9b84350d4fc0e800a5d8a9a7ccd4436216a8cb5d7a030b64f3dc69290ff09a723 |
|---|---|
| cites | cdi_FETCH-LOGICAL-c363t-9b84350d4fc0e800a5d8a9a7ccd4436216a8cb5d7a030b64f3dc69290ff09a723 |
| container_end_page | 2017 |
| container_issue | 7 |
| container_start_page | 1980 |
| container_title | Algorithmica |
| container_volume | 83 |
| creator | Ahn, Kook Jin Cormode, Graham Guha, Sudipto McGregor, Andrew Wirth, Anthony |
| description | 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. |
| doi_str_mv | 10.1007/s00453-021-00816-9 |
| format | article |
| fullrecord | <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_2544228583</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2544228583</sourcerecordid><originalsourceid>FETCH-LOGICAL-c363t-9b84350d4fc0e800a5d8a9a7ccd4436216a8cb5d7a030b64f3dc69290ff09a723</originalsourceid><addsrcrecordid>eNp9kE1LxDAURYMoWEf_gKuC4C768tlkKdVRYcCFug5pmkiHTjsm6cJ_b8cK7ly9zbn38g5ClwRuCEB1mwC4YBgowQCKSKyPUEE4oxgEJ8eoAFIpzCWpTtFZSlsAQistC3RdjzH63uZuHMq6n1L2sRs-ym4o72225WuO3u7SOToJtk_-4veu0Pv64a1-wpuXx-f6boMdkyxj3SjOBLQ8OPAKwIpWWW0r51rOmaREWuUa0VYWGDSSB9Y6qamGEGDGKFuhq6V3H8fPyadstuMUh3nSUME5pUooNlN0oVwcU4o-mH3sdjZ-GQLm4MMsPszsw_z4MHoOsSWU9ocPffyr_if1DetIYPk</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2544228583</pqid></control><display><type>article</type><title>Correlation Clustering in Data Streams</title><source>Springer Nature</source><creator>Ahn, Kook Jin ; Cormode, Graham ; Guha, Sudipto ; McGregor, Andrew ; Wirth, Anthony</creator><creatorcontrib>Ahn, Kook Jin ; Cormode, Graham ; Guha, Sudipto ; McGregor, Andrew ; Wirth, Anthony</creatorcontrib><description>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.</description><identifier>ISSN: 0178-4617</identifier><identifier>EISSN: 1432-0541</identifier><identifier>DOI: 10.1007/s00453-021-00816-9</identifier><language>eng</language><publisher>New York: Springer US</publisher><subject>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</subject><ispartof>Algorithmica, 2021-07, Vol.83 (7), p.1980-2017</ispartof><rights>The Author(s) 2021</rights><rights>The Author(s) 2021. This work is published under http://creativecommons.org/licenses/by/4.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c363t-9b84350d4fc0e800a5d8a9a7ccd4436216a8cb5d7a030b64f3dc69290ff09a723</citedby><cites>FETCH-LOGICAL-c363t-9b84350d4fc0e800a5d8a9a7ccd4436216a8cb5d7a030b64f3dc69290ff09a723</cites><orcidid>0000-0003-3746-6704 ; 0000-0002-0698-0922</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Ahn, Kook Jin</creatorcontrib><creatorcontrib>Cormode, Graham</creatorcontrib><creatorcontrib>Guha, Sudipto</creatorcontrib><creatorcontrib>McGregor, Andrew</creatorcontrib><creatorcontrib>Wirth, Anthony</creatorcontrib><title>Correlation Clustering in Data Streams</title><title>Algorithmica</title><addtitle>Algorithmica</addtitle><description>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.</description><subject>Algorithm Analysis and Problem Complexity</subject><subject>Algorithms</subject><subject>Approximation</subject><subject>Clustering</subject><subject>Computational geometry</subject><subject>Computer Science</subject><subject>Computer Systems Organization and Communication Networks</subject><subject>Convexity</subject><subject>Data structures</subject><subject>Data Structures and Information Theory</subject><subject>Data transmission</subject><subject>Mathematical analysis</subject><subject>Mathematical programming</subject><subject>Mathematics of Computing</subject><subject>Optimization</subject><subject>Partitions (mathematics)</subject><subject>Polynomials</subject><subject>Sampling methods</subject><subject>Sketches</subject><subject>Theory of Computation</subject><subject>Weight</subject><issn>0178-4617</issn><issn>1432-0541</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2021</creationdate><recordtype>article</recordtype><recordid>eNp9kE1LxDAURYMoWEf_gKuC4C768tlkKdVRYcCFug5pmkiHTjsm6cJ_b8cK7ly9zbn38g5ClwRuCEB1mwC4YBgowQCKSKyPUEE4oxgEJ8eoAFIpzCWpTtFZSlsAQistC3RdjzH63uZuHMq6n1L2sRs-ym4o72225WuO3u7SOToJtk_-4veu0Pv64a1-wpuXx-f6boMdkyxj3SjOBLQ8OPAKwIpWWW0r51rOmaREWuUa0VYWGDSSB9Y6qamGEGDGKFuhq6V3H8fPyadstuMUh3nSUME5pUooNlN0oVwcU4o-mH3sdjZ-GQLm4MMsPszsw_z4MHoOsSWU9ocPffyr_if1DetIYPk</recordid><startdate>20210701</startdate><enddate>20210701</enddate><creator>Ahn, Kook Jin</creator><creator>Cormode, Graham</creator><creator>Guha, Sudipto</creator><creator>McGregor, Andrew</creator><creator>Wirth, Anthony</creator><general>Springer US</general><general>Springer Nature B.V</general><scope>C6C</scope><scope>AAYXX</scope><scope>CITATION</scope><orcidid>https://orcid.org/0000-0003-3746-6704</orcidid><orcidid>https://orcid.org/0000-0002-0698-0922</orcidid></search><sort><creationdate>20210701</creationdate><title>Correlation Clustering in Data Streams</title><author>Ahn, Kook Jin ; Cormode, Graham ; Guha, Sudipto ; McGregor, Andrew ; Wirth, Anthony</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c363t-9b84350d4fc0e800a5d8a9a7ccd4436216a8cb5d7a030b64f3dc69290ff09a723</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2021</creationdate><topic>Algorithm Analysis and Problem Complexity</topic><topic>Algorithms</topic><topic>Approximation</topic><topic>Clustering</topic><topic>Computational geometry</topic><topic>Computer Science</topic><topic>Computer Systems Organization and Communication Networks</topic><topic>Convexity</topic><topic>Data structures</topic><topic>Data Structures and Information Theory</topic><topic>Data transmission</topic><topic>Mathematical analysis</topic><topic>Mathematical programming</topic><topic>Mathematics of Computing</topic><topic>Optimization</topic><topic>Partitions (mathematics)</topic><topic>Polynomials</topic><topic>Sampling methods</topic><topic>Sketches</topic><topic>Theory of Computation</topic><topic>Weight</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Ahn, Kook Jin</creatorcontrib><creatorcontrib>Cormode, Graham</creatorcontrib><creatorcontrib>Guha, Sudipto</creatorcontrib><creatorcontrib>McGregor, Andrew</creatorcontrib><creatorcontrib>Wirth, Anthony</creatorcontrib><collection>Springer Nature OA Free Journals</collection><collection>CrossRef</collection><jtitle>Algorithmica</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Ahn, Kook Jin</au><au>Cormode, Graham</au><au>Guha, Sudipto</au><au>McGregor, Andrew</au><au>Wirth, Anthony</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Correlation Clustering in Data Streams</atitle><jtitle>Algorithmica</jtitle><stitle>Algorithmica</stitle><date>2021-07-01</date><risdate>2021</risdate><volume>83</volume><issue>7</issue><spage>1980</spage><epage>2017</epage><pages>1980-2017</pages><issn>0178-4617</issn><eissn>1432-0541</eissn><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
·
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.</abstract><cop>New York</cop><pub>Springer US</pub><doi>10.1007/s00453-021-00816-9</doi><tpages>38</tpages><orcidid>https://orcid.org/0000-0003-3746-6704</orcidid><orcidid>https://orcid.org/0000-0002-0698-0922</orcidid><oa>free_for_read</oa></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 0178-4617 |
| ispartof | Algorithmica, 2021-07, Vol.83 (7), p.1980-2017 |
| issn | 0178-4617 1432-0541 |
| language | eng |
| recordid | cdi_proquest_journals_2544228583 |
| source | Springer Nature |
| 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 |
| title | Correlation Clustering in Data Streams |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-29T19%3A29%3A09IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Correlation%20Clustering%20in%20Data%20Streams&rft.jtitle=Algorithmica&rft.au=Ahn,%20Kook%20Jin&rft.date=2021-07-01&rft.volume=83&rft.issue=7&rft.spage=1980&rft.epage=2017&rft.pages=1980-2017&rft.issn=0178-4617&rft.eissn=1432-0541&rft_id=info:doi/10.1007/s00453-021-00816-9&rft_dat=%3Cproquest_cross%3E2544228583%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c363t-9b84350d4fc0e800a5d8a9a7ccd4436216a8cb5d7a030b64f3dc69290ff09a723%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2544228583&rft_id=info:pmid/&rfr_iscdi=true |