Crowdsourced Clustering via Active Querying: Practical Algorithm with Theoretical Guarantees

We propose a novel, practical, simple, and computationally efficient active querying algorithm for crowdsourced clustering that does not require knowledge of unknown problem parameters. We show that our algorithm succeeds in recovering the clusters when the crowdworkers provide answers with an error probability less than $1/2$ and provide sample complexity bounds on the number of queries made by our algorithm to guarantee successful clustering. While the bounds depend on the error probabilities, the algorithm itself does not require this knowledge. In addition to the theoretical guarantees, we implement and deploy the proposed algorithm on a real crowdsourcing platform to characterize its performance in real-world settings.