  Spatial crowdsourcing refers to a system that periodically assigns a number
of location-based workers with spatial tasks nearby (e.g., taking photos or
videos at some spatial locations). Previous works on the spatial crowdsourcing
usually designed task assignment strategies that maximize some assignment
scores, which are however only based on available workers/tasks in the system
at the time point of assigning workers/tasks. These strategies may achieve
local optimality, due to the neglect of future workers/tasks that may join the
system. In contrast, in this paper, we aim to achieve "globally" optimal task
assignments, by considering not only those present, but also future (via
predictions), workers/tasks. Specifically, we formalize an important problem,
namely prediction-based spatial crowdsourcing (PB-SC), which expects to obtain
a "globally" optimal strategy for worker-and-task assignments, over both
present and predicted task/worker locations, such that the total assignment
quality score is maximized under the constraint of the traveling budget. In
this paper, we design an effective grid-based prediction method to estimate
spatial distributions of workers/tasks in the future, and then utilize the
predicted ones in our procedure of task assignments. We prove that the PB-SC
problem is NP-hard, and thus intractable. Therefore, we propose efficient
approximate algorithms to tackle the PB-SC problem, including greedy and
divide-and-conquer (D&C) approaches, which can efficiently assign workers to
spatial tasks with high quality scores and low budget consumptions, by
considering both current and future task/worker distributions. Through
extensive experiments, we demonstrate the efficiency and effectiveness of our
PB-SC processing approaches on real/synthetic data.
