With the rapid development of mobile devices and the crowdsourcing platforms, the spatial crowdsourcing has attracted much attention from the database community, specifically, spatial crowdsourcing refers to sending a location-based request to workers according to their positions. In this paper, we consider an important spatial crowdsourcing problem, namely reliable diversity-based spatial crowdsourcing (RDB-SC), in which spatial tasks (such as taking videos/photos of a landmark or firework shows, and checking whether or not parking spaces are available) are time-constrained, and workers are moving towards some directions. Our RDB-SC problem is to assign workers to spatial tasks such that the completion reliability and the spatial/temporal diversities of spatial tasks are maximized. We prove that the RDB-SC problem is NP-hard and intractable. Thus, we propose three effective approximation approaches, including greedy, sampling, and divide-and-conquer algorithms. In order to improve the efficiency, we also design an effective cost-model-based index, which can dynamically maintain moving workers and spatial tasks with low cost, and efficiently facilitate the retrieval of RDB-SC answers. Through extensive experiments, we demonstrate the efficiency and effectiveness of our proposed approaches over both real and synthetic datasets. where parameter β ∈ [0, 1]. Here, β is a weight balancing between SD and TD, which depends on the application requirement specified by the task requester of ti. When β = 0, we consider TD only; when β = 1, we require SD only in the spatial task ti. Therefore, under possible worlds semantics, in this paper, we will consider the expected spatial/temporal diversity (defined later) in our crowdsourcing problem. The RDB-SC Problem. We define our RDB-SC problem below. Definition 4. (Reliable Diversity-Based Spatial Crowdsourcing, RDB-SC) Given m time-constrained spatial tasks in T , and n dy-I j,k e i −s i ) · log( I j,k e i −s i ), for j ≤ k; moreover, MT D [j][k] = 0,if j > k. Formally, for j ≤ k, we have:
REF shows task assignment with these constraints is NP-hard and proposes several approximation algorithms.
Reliable Diversity-Based Spatial Crowdsourcing by Moving Workers
ArXiv
ArXiv
Computer Science