Online Algorithms of Task Allocation in Spatial Crowdsourcing
Yong Sun, Jun Wang, Wenan Tan · 2017
Recently, spatial collaborations1 and crowdsourcing has emerged as a novel typical pattern for applying to a range of problems. A key problem of spatial collaboration is to allocate suitable workers to nearby tasks in a real-time online way. Traditional crowdsourcing algorithms always consider the quality of worker with prior knowledge. However, in online crowdsourcing context, the quality of crowd-workers is unknown and uncertain. It is so hard for such task crowdsourcing process in an inherently online and dynamic environment. To solve this spatial crowdsourcing problem, the branch-and-bound R-tree data structure is employed in our algorithms to prune the search tree of the nearby crowd-workers. Furthermore, we introduce a new online algorithm to deal with the uncertain crowdsourcing problems. Theoretical analysis and extensive experiments are conducted for validation purpose; and the experimental results show that our algorithms outperform several existing algorithms in terms of computation time in dealing with the increasing number of crowdsourcing task executing candidates.