  The prevalence of mobile internet techniques stimulates the emergence of
various spatial crowdsourcing applications. Certain of the applications serve
for requesters, budget providers, who submit a batch of tasks and a fixed
budget to platform with the desire to search suitable workers to complete the
tasks in maximum quantity. Platform lays stress on optimizing assignment
strategies on seeking less budget-consumed worker-task pairs to meet
requesters' demands. Existing research on the task assignment with budget
constraint mostly focuses on static offline scenarios, where the spatiotemporal
information of all workers and tasks is known in advance. However, workers
usually appear dynamically on real spatial crowdsourcing platforms, where
existing solutions can hardly handle it. In this paper, we formally define a
novel problem Budget-aware Online task Assignment(BOA) in spatial crowdsourcing
applications. BOA aims to maximize the number of assigned worker- task pairs
under a budget constraint where workers appear dynamically on platforms. To
address the BOA problem, we first propose an efficient threshold-based greedy
algorithm Greedy-RT which utilizes a random generated threshold to prune the
pairs with large travel cost. Greedy-RT performs well in adversary model when
compared with simple greedy algorithm, but it is unstable in random model for
its randomly generated threshold may produce poor quality in matching size. We
then propose a revised algorithm Greedy-OT which could learn approximately
optimal threshold from historical data, and consequently improves matching size
significantly in both models. Finally, we verify the effectiveness and
efficiency of the proposed methods through extensive experiments on real and
synthetic datasets.
