The pervasiveness of shortest path queries is evident in real life, particularly in online mapping applications. However, in practice, the travel times of road segments can be uncertain due to various reasons, such as traffic congestion, which leads to the shortest path not to be the fastest, resulting in an unreliable path. The Reliable Shortest Path (RSP) query has been developed to fulfill individuals' reliability requirements by considering travel times as random variables. Extensive solutions have been proposed to efficiently find RSPs in stochastic road networks. However, they are either unscalable to large networks or incapable of handling rapid streams of routing queries. In this paper, we propose an efficient index-based solution for RSP queries, called Non-dominated Reliable Path (NRP). It stores partial path answers to support fast query processing and utilizes several tailored pruning techniques that can significantly reduce the query time. Experiments conducted on large city road networks verified the superiority of our solution, which can answer each query in around 100 microseconds and beat competitors by orders of magnitude.

The point-to-point shortest path query is widely used in many spatial applications, e.g., navigation systems. However, the returned shortest path minimizing only one objective fails to satisfy users' various routing requirements in practice. For example, the user may specify the order of using several transportation modes in the planned route. The Label-Constrained Shortest Path (LCSP) query under regular languages is powerful enough to express diversified routing demands in a labeled road network where each edge is associated with a label to denote its road type. The complex routing demand can be formulated by a regular language, and the edge labels along each path should be a word under the given regular language. Previous LCSP solutions were either inefficient in query processing or inflexible in their use of the languages since they made some assumptions about the given language. In this paper, we propose an efficient index-based solution called Border-based State Move (BSM), which can answer LCSP queries quickly with flexible use of the language constraint. Specifically, our BSM builds indexes to skip the exploration between a vertex and its border vertices during query processing. Our experiments conducted on real road networks demonstrated the superiority of our proposed BSM. It can reduce the query time over state-of-the-art solutions by two orders of magnitude.

Vehicular traffic congestion is a recurring and widespread societal phenomenon. Since drivers increasingly rely on routing services, we consider how to enhance such services to provide routes that mitigate congestion. Specifically, we propose the Congestion-mitigating Spatiotemporal Routing (CSR) problem that considers the congestion caused by vehicles following the routes provided. This problem is challenging because vehicles that follow recommended routes appear on different road segments at different times. We propose two solutions, Spatiotemporal Oblivious Routing (SOR) and Spatiotemporal Routing with History (SRH), which return routes based on the current and anticipated future traffic statuses, respectively, while offering theoretical guarantees. We also propose an update procedure for handling traffic dynamics. Extensive evaluations on real data provide insight into the properties of the solutions, indicating that SRH can reduce the number of vehicles on the most congested road segments by nearly 33 % and can process a query in less than 10 ms.

Shortest path queries are ubiquitous in many spatial applications. Existing solutions assign numerical weights to edges and compute the path with the minimum sum of edge weights. However, in practice, the road categories associated with edges (e.g., toll) can make shortest paths undesirable, e.g., they may use unfavorable toll roads. Augmenting each edge with a label to denote its category, we study the Label-Constrained Shortest Path (LCSP) query that finds the shortest path under the constraint that the edge labels along the path should follow a pattern expressed by a formal language. There have been extensive LCSP solutions, but they are either inefficient in query processing or limited to special languages with low expressiveness capacity. In this paper, we propose the index called Partially Constrained Shortest Path (PCSP), which answers each query quickly by concatenating two shortest paths that partially satisfy the constraint and support more general regular languages. We also present pruning techniques that further optimize query efficiency. Experimental comparison with the state-of-the-art index demonstrates the superiority of PCSP. It can answer each LCSP query in around 100 microseconds and runs faster than the best-known solution by up to two orders of magnitude.

Public transport contributes significantly to addressing some city issues such as air pollution and traffic congestion. As the public transport demand changes in urban development, we need to plan new routes to match the demand. Existing methods of planning new bus routes either are inefficient in using the path’s cost or use other inaccurate cost measurements. This paper focuses on finding a new bus route efficiently on road networks. Specifically, we first propose the Bus Routing on Roads (BRR) problem which combines two common goals of minimizing the walking costs of passengers and maximizing the connectivity of the new route to the existing transit network. They are consistent with matching the demand and facilitating the transfer. We first show the NP-hardness of the BRR and design an approximation algorithm called Efficient Bus Routing on Roads (EBRR). We theoretically analyzed its approximation ratio and time complexity. Extensive evaluations with state-of-the-art solutions on three real-world datasets validate the effectiveness and efficiency of EBRR. It could recommend a new bus route with high quality in around 10 seconds, 60x faster than the baselines.

Route planning is fundamental in our daily life. However, existing mapping applications focus on recommending routes by optimizing one single objective, which is inconsistent with some scenarios where users prefer the optimal route under a constraint. The constrained shortest path (CSP) query matches this requirement, but the query efficiencies of previous solutions are often low due to CSP's NP-hardness. In the era of big data, state-of-the-art indexes are getting larger to support faster query processing. Recent attempts to preprocess more intermediate results and reduce the number of table lookups have proved successful in solving the CSP. However, the best-known algorithm ignores some information in the CSP queries and tries to solve a more general problem before tackling the exact CSP. In this paper, we propose by far the fastest algorithm called QHL, which fully utilizes the pruning power of the CSP query information. Specifically, we preprocess our index by generating pruning conditions that can improve query efficiency. We also conducted extensive experiments on real-world datasets to demonstrate the superiority of our proposed algorithm. QHL could answer each CSP query in around 50 μs and run faster than the best-known algorithm by orders of magnitude.

With the rapid development of smartphones, spatial crowdsourcing platforms are getting popular. A foundational research of spatial crowdsourcing is to allocate micro-tasks to suitable crowd workers. Many existing studies focus on the offline scenario, where all the spatiotemporal information of micro-tasks and crowd workers is given. In this paper, we focus on the online scenario and identify a more practical micro-task allocation problem, called theGlobalOnlineMicro-taskAllocation in spatial crowdsourcing(GOMA) problem. We first extend the state-of-the-art algorithm for the online maximum weighted bipartite matching problem to the GOMA problem as the baseline algorithm. Although the baseline algorithm provides a theoretical guarantee for the worst case, its average performance in practice is not good enough since the worst case happens with a very low probability in the real world. Thus, we consider the average performance of online algorithms,a.k.a.random order model. We propose a two-phase-based framework, based on which we present the TGOA algorithm with a$\frac{1}{4}$-competitive ratio under the random order model. To improve its efficiency, we further design the TGOA-Greedy and TGOA-OP algorithm following this framework, which runs faster than the TGOA algorithm with a competitive ratio of$\frac{1}{8}$and$\frac{1}{4}$, respectively. We also revisit the average performance of Greedy, which has long been considered as the worst due to its unbounded competitive ratio in the worst case. Finally, we verify the effectiveness and efficiency of the proposed methods through extensive experiments on synthetic and real datasets.

Procrastination is a prevalent form of self-control failure. As it often concerns with the individual's ability to meet the deadline, an efficient time management is crucial for overcoming it. Though a considerable amount of work in behavioral economics provides useful insights, there is not a computational way to guide us how to obtain an appropriate schedule for all the things to be done, especially when the relationship of the deadlines is intrinsic. In this paper, we first propose the Procrastination-aware Scheduling Problem (PSP) to model an appropriate schedule. A bipartite graph formulation is then developed to further illustrate the concepts. We find the PSP is NP-hard in the strong sense and design an approximation algorithm. In addition, we note the significance of the PSP under the online scenario (called OnlinePSP). Finally, we verify the effectiveness and efficiency of the proposed algorithms through extensive experiments on real datasets.

In spatial crowdsourcing, requesters submit their task-related locations and increase the demand of a local area. The platform prices these tasks and assigns spatial workers to serve if the prices are accepted by requesters. There exist mature pricing strategies which specialize in tackling the imbalance between supply and demand in a local market. However, in global optimization, the platform should consider the mobility of workers; that is, any single worker can be the potential supply for several areas, while it can only be the true supply of one area when assigned by the platform. The hardness lies in the uncertainty of the true supply of each area, hence the existing pricing strategies do not work. In the paper, we formally define this Global Dynamic Pricing(GDP) problem in spatial crowdsourcing. And since the objective is concerned with how the platform matches the supply to areas, we let the matching algorithm guide us how to price. We propose a MAtching-based Pricing Strategy (MAPS) with guaranteed bound. Extensive experiments conducted on the synthetic and real datasets demonstrate the effectiveness of MAPS.

The prevalence of mobile Internet techniques and Online-To-Offline (O2O) business models has led the emergence of various spatial crowdsourcing (SC) platforms in our daily life. A core issue of SC is to assign real-time tasks to suitable crowd workers. Existing approaches usually focus on the matching of two types of objects, tasks and workers, or assume the static offline scenarios, where the spatio-temporal information of all the tasks and workers is known in advance. Recently, some new emerging O2O applications incur new challenges: SC platforms need to assign three types of objects, tasks, workers and workplaces, and support dynamic real-time online scenarios, where the existing solutions cannot handle. In this paper, based on the aforementioned challenges, we formally define a novel dynamic online task assignment problem, called the trichromatic online matching in real-time spatial crowdsourcing (TOM) problem, which is proven to be NP-hard. Thus, we first devise an efficient greedy online algorithm. However, the greedy algorithm can be trapped into local optimal solutions easily. We then present a threshold-based randomized algorithm that not only guarantees a tighter competitive ratio but also includes an adaptive optimization technique, which can quickly learn the optimal threshold for the randomized algorithm. Finally, we verify the effectiveness and efficiency of the proposed methods through extensive experiments on real and synthetic datasets.

The popularity of Online To Offline (O2O) service platforms has spurred the need for online task assignment in real-time spatial data, where streams of spatially distributed tasks and workers are matched in real time such that the total number of assigned pairs is maximized. Existing online task assignment models assume that each worker is either assigned a task immediately or waits for a subsequent task at a fixed location once she/he appears on the platform. Yet in practice a worker may actively move around rather than passively wait in place if no task is assigned. In this paper, we define a new problem Flexible Two-sided Online task Assignment (FTOA). FTOA aims to guide idle workers based on the prediction of tasks and workers so as to increase the total number of assigned worker-task pairs. To address the FTOA problem, we face two challenges: (i) How to generate guidance for idle workers based on the prediction of the spatiotemporal distribution of tasks and workers? (ii) How to leverage the guidance of workers' movements to optimize the online task assignment? To this end, we propose a novel two-step framework, which integrates offline prediction and online task assignment. Specifically, we estimate the distributions of tasks and workers per time slot and per unit area, and design an online task assignment algorithm, Prediction-oriented Online task Assignment in Real-time spatial data (POLAR-OP). It yields a 0.47-competitive ratio, which is nearly twice better than that of the state-of-the-art. POLAR-OP also reduces the time complexity to process each newly-arrived task/worker to O(1). We validate the effectiveness and efficiency of our methods via extensive experiments on both synthetic datasets and real-world datasets from a large-scale taxi-calling platform.

With the rapid development of smartphones, spatial crowdsourcing platforms are getting popular. A foundational research of spatial crowdsourcing is to allocate micro-tasks to suitable crowd workers. Most existing studies focus on offline scenarios, where all the spatiotemporal information of micro-tasks and crowd workers is given. However, they are impractical since micro-tasks and crowd workers in real applications appear dynamically and their spatiotemporal information cannot be known in advance. In this paper, to address the shortcomings of existing offline approaches, we first identify a more practical micro-task allocation problem, called the Global Online Micro-task Allocation in spatial crowdsourcing (GOMA) problem. We first extend the state-of-art algorithm for the online maximum weighted bipartite matching problem to the GOMA problem as the baseline algorithm. Although the baseline algorithm provides theoretical guarantee for the worst case, its average performance in practice is not good enough since the worst case happens with a very low probability in real world. Thus, we consider the average performance of online algorithms, a.k.a online random order model.We propose a two-phase-based framework, based on which we present the TGOA algorithm with 1 over 4 -competitive ratio under the online random order model. To improve its efficiency, we further design the TGOA-Greedy algorithm following the framework, which runs faster than the TGOA algorithm but has lower competitive ratio of 1 over 8. Finally, we verify the effectiveness and efficiency of the proposed methods through extensive experiments on real and synthetic datasets.