With the abundance and ubiquity of mobile devices, a new class of applications, called spatial crowdsourcing, is emerging, which enables spatial tasks (i.e., tasks related to a location) assigned to and performed by human workers. However, one of the major challenges with spatial crowdsourcing is how to verify the validity of the results provided by workers, when the workers are not trusted equally. To tackle this problem, we assume every worker has a reputation score, which states the probability that the worker performs a task correctly. Moreover, we define a confidence level for every spatial task, which states that the answer to the given spatial task is only accepted if its confidence is higher than a certain threshold. Thus, the problem we are trying to solve is to maximize the number of spatial tasks that are assigned to a set of workers while satisfying the confidence levels of those tasks. Note that a unique aspect of our problem is that the optimal assignment of tasks heavily depends on the geographical locations of workers and tasks. This means that every spatial task should be assigned to enough number of workers such that their aggregate reputation satisfies the confidence of the task. Consequently, an exhaustive approach needs to compute the aggregate reputation score (using a typical decision fusion aggregation mechanism, such as voting) for all possible subsets of the workers, which renders the problem complex (we show it is NP-hard). Subsequently, we propose a number of heuristics and utilizing real-world and synthetic data in extensive sets of experiments we show that we can achieve close to optimal performance with the cost of a greedy approach, by exploiting our problem's unique characteristics.

With the ubiquity of mobile devices, spatial crowdsourcing is emerging as a new platform, enabling spatial tasks (i.e., tasks related to a location) assigned to and performed by human workers. In this paper, for the first time we introduce a taxonomy for spatial crowdsourcing. Subsequently, we focus on one class of this taxonomy, in which workers send their locations to a centralized server and thereafter the server assigns to every worker his nearby tasks with the objective of maximizing the overall number of assigned tasks. We formally define this maximum task assignment (or MTA) problem in spatial crowdsourcing, and identify its challenges. We propose alternative solutions to address these challenges by exploiting the spatial properties of the problem space. Finally, our experimental evaluations on both real-world and synthetic data verify the applicability of our proposed approaches and compare them by measuring both the number of assigned tasks and the travel cost of the workers.

In this article, we first introduce the concept of Spatial Skyline Queries (SSQ). Given a set of data points P and a set of query points Q , each data point has a number of derived spatial attributes each of which is the point's distance to a query point. An SSQ retrieves those points of P which are not dominated by any other point in P considering their derived spatial attributes. The main difference with the regular skyline query is that this spatial domination depends on the location of the query points Q . SSQ has application in several domains such as emergency response and online maps. The main intuition and novelty behind our approaches is that we exploit the geometric properties of the SSQ problem space to avoid the exhaustive examination of all the point pairs in P and Q . Consequently, we reduce the complexity of SSQ search from O (| P | 2 | Q |) to O (| S | 2 | C | + √| P |), where | S | and | C | are the solution size and the number of vertices of the convex hull of Q , respectively. Considering Euclidean distance, we propose two algorithms, B 2 S 2 and VS 2 , for static query points and one algorithm, VCS 2 , for streaming Q whose points change location over time (e.g., are mobile). VCS 2 exploits the pattern of change in Q to avoid unnecessary recomputation of the skyline and hence efficiently perform updates. We also propose two algorithms, SNS 2 and VSNS 2 , that compute the spatial skyline with respect to the network distance in a spatial network database. Our extensive experiments using real-world datasets verify that both R-tree-based B 2 S 2 and Voronoi-based VS 2 outperform the best competitor approach in terms of both processing time and I/O cost. Furthermore, their output computed based on Euclidean distance is a good approximation of the spatial skyline in network space. For accurate computation of spatial skylines in network space, our experiments showed the superiority of VSNS 2 over SNS 2 .

A frequent query in geospatial planning and decision making domains (e.g., emergency response, data acquisition, street cleaning), is to find an optimal traversal plan (OTP) that traverses an entire area (e.g., a city) by navigating through all its streets. The optimality is defined in terms of the time it takes to complete the traversal. This time depends on the number of times each street segment is traversed as well as the navigation time such as the time spent on changing direction at each intersection.