CrowdOp: Query Optimization for Declarative Crowdsourcing Systems

We study the query optimization problem in declarative crowdsourcing systems. Declarative crowdsourcing is designed to hide the complexities and relieve the user of the burden of dealing with the crowd. The user is only required to submit an SQL-like query and the system takes the responsibility of...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on knowledge and data engineering 2015-08, Vol.27 (8), p.2078-2092
Main Authors: Ju Fan, Meihui Zhang, Kok, Stanley, Meiyu Lu, Beng Chin Ooi
Format: Article
Language:English
Subjects:
Accuracy
Algorithms
Automobiles
Balancing
Computer simulation
Crowdsourcing
Data models
Dealing
Marketing
Online analytical processing
Optimization
Queries
Query Optimization
Query processing
Relational data bases
Servers
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study the query optimization problem in declarative crowdsourcing systems. Declarative crowdsourcing is designed to hide the complexities and relieve the user of the burden of dealing with the crowd. The user is only required to submit an SQL-like query and the system takes the responsibility of compiling the query, generating the execution plan and evaluating in the crowdsourcing marketplace. A given query can have many alternative execution plans and the difference in crowdsourcing cost between the best and the worst plans may be several orders of magnitude. Therefore, as in relational database systems, query optimization is important to crowdsourcing systems that provide declarative query interfaces. In this paper, we propose CROWDOP, a cost-based query optimization approach for declarative crowdsourcing systems. CROWDOP considers both cost and latency in query optimization objectives and generates query plans that provide a good balance between the cost and latency. We develop efficient algorithms in the CROWDOP for optimizing three types of queries: selection queries, join queries, and complex selection-join queries. We validate our approach via extensive experiments by simulation as well as with the real crowd on Amazon Mechanical Turk.
ISSN:1041-4347
1558-2191
DOI:10.1109/TKDE.2015.2407353