Title
On the Complexity of Evaluating Order Queries with the Crowd.
Abstract
One of the foremost challenges for information technology over the last few years has been to explore, understand, and extract useful information from large amounts of data. Some particular tasks such as annotating data or matching entities have been outsourced to human workers for many years. But the last few years have seen the rise of a new research field called crowdsourcing that aims at delegating a wide range of tasks to human workers, building formal frameworks, and improving the efficiency of these processes. The database community has thus been suggesting algorithms to process traditional data manipulation operators with the crowd, such as joins or filtering. This is even more useful when comparing the underlying “tuples” is a subjective decision – e.g., when they are photos, text, or simply noisy data with different variations and interpretations – and can presumably be done better and faster by humans than by machines. The problems considered in this article aim to retrieve a subset of preferred items from a set of items by delegating pairwise comparison operations to the crowd. The most obvious example is finding the maximum of a set of items (called max). We also consider two natural generalizations of the max problem:
Year
Venue
Field
2015
IEEE Data Eng. Bull.
Data mining,Pairwise comparison,Joins,Computer science,Generalization,Tuple,Information technology,Crowdsourcing,Data manipulation language,Delegation
DocType
Volume
Issue
Journal
38
3
Citations 
PageRank 
References 
1
0.35
27
Authors
3
Name
Order
Citations
PageRank
Benoît Groz1252.80
Tova Milo240741052.72
Sudeepa Roy326830.95