So who won? Dynamic max discovery with the crowd

Stephen Guo, Aditya Parameswaran, Hector Garcia-Molina

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider a crowdsourcing database system that may cleanse, populate, or filter its data by using human workers. Just like a conventional DB system, such a crowdsourcing DB system requires data manipulation functions such as select, aggregate, maximum, average, and so on, except that now it must rely on human operators (that for example compare two objects) with very different latency, cost and accuracy characteristics. In this paper, we focus on one such function, maximum, that finds the highest ranked object or tuple in a set. In particularm we study two problems: given a set of votes (pairwise comparisons among objects), how do we select the maximum? And how do we improve our estimate by requesting additional votes? We show that in a crowdsourcing DB system, the optimal solution to both problems is NP-Hard. We then provide heuristic functions to select the maximum given evidence, and to select additional votes. We experimentally evaluate our functions to highlight their strengths and weaknesses.

Original languageEnglish (US)
Title of host publicationSIGMOD '12 - Proceedings of the International Conference on Management of Data
Pages385-396
Number of pages12
DOIs
StatePublished - 2012
Externally publishedYes
Event2012 ACM SIGMOD International Conference on Management of Data, SIGMOD '12 - Scottsdale, AZ, United States
Duration: May 21 2012May 24 2012

Publication series

NameProceedings of the ACM SIGMOD International Conference on Management of Data
ISSN (Print)0730-8078

Other

Other2012 ACM SIGMOD International Conference on Management of Data, SIGMOD '12
Country/TerritoryUnited States
CityScottsdale, AZ
Period5/21/125/24/12

Keywords

  • aggregation
  • crowdsourcing
  • human computation
  • max
  • voting

ASJC Scopus subject areas

  • Software
  • Information Systems

Fingerprint

Dive into the research topics of 'So who won? Dynamic max discovery with the crowd'. Together they form a unique fingerprint.

Cite this