A LARGE SCALE TASK DECOMPOSITION SCHEME IN CROWDSOURCING SYSTEMS

MPhil Thesis Defence


Title: "A LARGE SCALE TASK DECOMPOSITION SCHEME IN CROWDSOURCING SYSTEMS"

By

Mr. Leihao XIA


Abstract

Crowdsourcing has been shown to be effective in a wide range of applications, 
and is seeing increasing use. It is generally recognized that a complex 
large-scale task has to be decomposed into smaller HITs (Human Intelligence 
Tasks) before it can be crowdsourced. This raises the question of how to 
perform this task decomposition best. It turns out that creating HITs that are 
too large results in poor answer quality while creating HITs that are too small 
incurs unnecessary cost. In this study, we propose a smart large scale task 
decomposition scheme in crowdsourcing systems, to effectively decompose a 
large-scale task into a set of HITs to achieve a result that is both 
costeffective and accurate.

Specifically, we define the Effective Decomposition Problem (ED Problem) and 
prove its NP-hardness. Then, we investigate this hard problem from two 
scenarios. In the first scenario, all tasks have the same quality threshold, 
and we propose two efficient and effective approximation algorithms using 
greedy strategy and optimal priority queue structure to find a near-optimal 
solution. In the second scenario, quality thresholds of different tasks are 
different, and we extend the approximation algorithms proposed for the first 
scenario by using partitioning strategy. Finally, we verify the effectiveness 
and efficiency of our scheme through extensive experiments on representative 
crowdsourcing platforms.


Date:			Monday, 24 August 2015

Time:			12:00noon - 2:00pm

Venue:			Room 3584
 			Lifts 27/28

Committee Members:	Dr. Lei Chen (Supervisor)
 			Dr. Ke Yi (Chairperson)
 			Dr. Pan Hui


**** ALL are Welcome ****