Clustering with a faulty oracle

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Standard

Clustering with a faulty oracle. / Green Larsen, Kasper; Mitzenmacher, Michael; Tsourakakis, Charalampos.

WWW '20: Proceedings of The Web Conference 2020. ed. / Yennun Huang; Irwin King; Tie-Yan Liu; Maarten van Steen. New York : Association for Computing Machinery, 2020. p. 2831-2834.

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Harvard

Green Larsen, K, Mitzenmacher, M & Tsourakakis, C 2020, Clustering with a faulty oracle. in Y Huang, I King, T-Y Liu & M van Steen (eds), WWW '20: Proceedings of The Web Conference 2020. Association for Computing Machinery, New York, pp. 2831-2834, WWW '20, Taipei , Taiwan, 20/04/2020. https://doi.org/10.1145/3366423.3380045

APA

Green Larsen, K., Mitzenmacher, M., & Tsourakakis, C. (2020). Clustering with a faulty oracle. In Y. Huang, I. King, T-Y. Liu, & M. van Steen (Eds.), WWW '20: Proceedings of The Web Conference 2020 (pp. 2831-2834). Association for Computing Machinery. https://doi.org/10.1145/3366423.3380045

CBE

Green Larsen K, Mitzenmacher M, Tsourakakis C. 2020. Clustering with a faulty oracle. Huang Y, King I, Liu T-Y, van Steen M, editors. In WWW '20: Proceedings of The Web Conference 2020. New York: Association for Computing Machinery. pp. 2831-2834. https://doi.org/10.1145/3366423.3380045

MLA

Green Larsen, Kasper, Michael Mitzenmacher and Charalampos Tsourakakis "Clustering with a faulty oracle"., Huang, Yennun and King, Irwin Liu, Tie-Yan van Steen, Maarten (editors). WWW '20: Proceedings of The Web Conference 2020. New York: Association for Computing Machinery. 2020, 2831-2834. https://doi.org/10.1145/3366423.3380045

Vancouver

Green Larsen K, Mitzenmacher M, Tsourakakis C. Clustering with a faulty oracle. In Huang Y, King I, Liu T-Y, van Steen M, editors, WWW '20: Proceedings of The Web Conference 2020. New York: Association for Computing Machinery. 2020. p. 2831-2834 https://doi.org/10.1145/3366423.3380045

Author

Green Larsen, Kasper ; Mitzenmacher, Michael ; Tsourakakis, Charalampos. / Clustering with a faulty oracle. WWW '20: Proceedings of The Web Conference 2020. editor / Yennun Huang ; Irwin King ; Tie-Yan Liu ; Maarten van Steen. New York : Association for Computing Machinery, 2020. pp. 2831-2834

Bibtex

@inproceedings{7fe169e9d0fe4ccf95a023abcff34268,
title = "Clustering with a faulty oracle",
abstract = "Clustering, i.e., finding groups in the data, is a problem that permeates multiple fields of science and engineering. Recently, the problem of clustering with a noisy oracle has drawn attention due to various applications including crowdsourced entity resolution [33], and predicting signs of interactions in large-scale online social networks [20, 21]. Here, we consider the following fundamental model for two clusters as proposed by Mitzenmacher and Tsourakakis [28], and Mazumdar and Saha [25]; there exist n items, belonging to two unknown groups. We are allowed to query any pair of nodes whether they belong to the same cluster or not, but the answer to the query is corrupted with some probability . Let 1 > δ= 1 - 2q > 0 be the bias. In this work, we provide a polynomial time algorithm that recovers all signs correctly with high probability in the presence of noise with queries. This is the best known result for this problem for all but tiny d, improving on the current state-of-the-art due to Mazumdar and Saha [25].",
keywords = "active learning, clustering, randomized algorithms",
author = "{Green Larsen}, Kasper and Michael Mitzenmacher and Charalampos Tsourakakis",
year = "2020",
month = apr,
doi = "10.1145/3366423.3380045",
language = "English",
isbn = "9781450370233",
pages = "2831--2834",
editor = "Huang, { Yennun } and { King}, { Irwin} and Liu, {Tie-Yan } and { van Steen}, Maarten",
booktitle = "WWW '20",
publisher = "Association for Computing Machinery",
note = "WWW '20 : The Web Conference 2020 ; Conference date: 20-04-2020 Through 24-04-2020",

}

RIS

TY - GEN

T1 - Clustering with a faulty oracle

AU - Green Larsen, Kasper

AU - Mitzenmacher, Michael

AU - Tsourakakis, Charalampos

PY - 2020/4

Y1 - 2020/4

N2 - Clustering, i.e., finding groups in the data, is a problem that permeates multiple fields of science and engineering. Recently, the problem of clustering with a noisy oracle has drawn attention due to various applications including crowdsourced entity resolution [33], and predicting signs of interactions in large-scale online social networks [20, 21]. Here, we consider the following fundamental model for two clusters as proposed by Mitzenmacher and Tsourakakis [28], and Mazumdar and Saha [25]; there exist n items, belonging to two unknown groups. We are allowed to query any pair of nodes whether they belong to the same cluster or not, but the answer to the query is corrupted with some probability . Let 1 > δ= 1 - 2q > 0 be the bias. In this work, we provide a polynomial time algorithm that recovers all signs correctly with high probability in the presence of noise with queries. This is the best known result for this problem for all but tiny d, improving on the current state-of-the-art due to Mazumdar and Saha [25].

AB - Clustering, i.e., finding groups in the data, is a problem that permeates multiple fields of science and engineering. Recently, the problem of clustering with a noisy oracle has drawn attention due to various applications including crowdsourced entity resolution [33], and predicting signs of interactions in large-scale online social networks [20, 21]. Here, we consider the following fundamental model for two clusters as proposed by Mitzenmacher and Tsourakakis [28], and Mazumdar and Saha [25]; there exist n items, belonging to two unknown groups. We are allowed to query any pair of nodes whether they belong to the same cluster or not, but the answer to the query is corrupted with some probability . Let 1 > δ= 1 - 2q > 0 be the bias. In this work, we provide a polynomial time algorithm that recovers all signs correctly with high probability in the presence of noise with queries. This is the best known result for this problem for all but tiny d, improving on the current state-of-the-art due to Mazumdar and Saha [25].

KW - active learning

KW - clustering

KW - randomized algorithms

UR - http://www.scopus.com/inward/record.url?scp=85086596158&partnerID=8YFLogxK

U2 - 10.1145/3366423.3380045

DO - 10.1145/3366423.3380045

M3 - Article in proceedings

AN - SCOPUS:85086596158

SN - 9781450370233

SP - 2831

EP - 2834

BT - WWW '20

A2 - Huang, Yennun

A2 - King, Irwin

A2 - Liu, Tie-Yan

A2 - van Steen, Maarten

PB - Association for Computing Machinery

CY - New York

T2 - WWW '20

Y2 - 20 April 2020 through 24 April 2020

ER -