Show simple item record

dc.contributor.authorDavid, Garcia-Sorianoen_US
dc.contributor.authorKutzkov, Konstantinen_US
dc.contributor.authorFrancesco, Bonchien_US
dc.contributor.authorTsourakakis, Charalamposen_US
dc.coverage.spatialTaipeien_US
dc.date2020-01-10
dc.date.accessioned2020-09-16T17:31:16Z
dc.date.available2020-09-16T17:31:16Z
dc.date.issued2020-04
dc.identifier.citationGarcia-Soriano David, Konstantin Kutzkov, Bonchi Francesco, Charalampos Tsourakakis. 2020. "Query-Efficient Correlation Clustering." WWW '20: Proceedings of The Web Conference 2020. The Web Conference 2020. Taipei, https://doi.org/10.1145/3366423.3380220
dc.identifier.urihttps://hdl.handle.net/2144/41397
dc.description.abstractCorrelation clustering is arguably the most natural formulation of clustering. Given n objects and a pairwise similarity measure, the goal is to cluster the objects so that, to the best possible extent, similar objects are put in the same cluster and dissimilar objects are put in different clusters. A main drawback of correlation clustering is that it requires as input the Θ(n2) pairwise similarities. This is often infeasible to compute or even just to store. In this paper we study query-efficient algorithms for correlation clustering. Specifically, we devise a correlation clustering algorithm that, given a budget of Q queries, attains a solution whose expected number of disagreements is at most , where is the optimal cost for the instance. Its running time is O(Q), and can be easily made non-adaptive (meaning it can specify all its queries at the outset and make them in parallel) with the same guarantees. Up to constant factors, our algorithm yields a provably optimal trade-off between the number of queries Q and the worst-case error attained, even for adaptive algorithms. Finally, we perform an experimental study of our proposed method on both synthetic and real data, showing the scalability and the accuracy of our algorithm.en_US
dc.format.extentp. 1468 - 1478en_US
dc.language.isoen_US
dc.publisherAssociation for Computing Machineryen_US
dc.relation.ispartofWWW '20: Proceedings of The Web Conference 2020
dc.titleQuery-efficient correlation clusteringen_US
dc.typeConference materialsen_US
dc.description.versionFirst author draften_US
dc.identifier.doi10.1145/3366423.3380220
pubs.elements-sourcemanual-entryen_US
pubs.notesEmbargo: Not knownen_US
pubs.organisational-groupBoston Universityen_US
pubs.organisational-groupBoston University, College of Arts & Sciencesen_US
pubs.organisational-groupBoston University, College of Arts & Sciences, Department of Computer Scienceen_US
pubs.publication-statusPublisheden_US
dc.identifier.mycv540405


This item appears in the following Collection(s)

Show simple item record