So Who Won? Dynamic Max Discovery with the Crowd

This is the latest version of this item.

Abstract

A crowdsourcing database system is one that uses human workers to cleanse, populate, or filter its data. 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 particular, we study two problems: First, given a set of crowdsourced votes (pairwise comparisons among objects), how do we select the maximum? Second, 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.

Available Versions of this Item

• So Who Won? Dynamic Max Discovery with the Crowd. (deposited 13 Mar 2012 11:05) [Currently Displayed]