The diversified route planning finds multiple paths that are sufficiently different from each other while as short as possible. It is of great significance to traffic alleviation through provided alternative routes during navigation. However, it is NP-H to find the optimal result and the existing solutions have either high quality (exact path enumeration-based) or high efficiency (alternative path), which is highly affected by the network properties and query parameters but has never been investigated before. Therefore, this paper proposes a hybrid diversified routing system that can handle any query efficiently with quality as high as possible. Specifically, we first analyze the path enumeration problem from the ground up and unify all the existing algorithms theoretically to identify the factors that affect algorithm performance. After that, we review and select the alternative path methods to identify the suitable ones for our system. Finally, we propose a query classification module to estimate the hardness of a query and determine how it should be processed. Extensive experiments on real-life networks validate the effectiveness and efficiency of our hybrid system compared with state-of-the-art solutions.

Given a source, destination, and required keywords, the Optimal Route with Collective Spatial Keywords ( ORCSK ) query aims to find the shortest route covering all keywords. Existing Point of Interest (POI) candidate set-based and path expansion-based methods frequently produce inferior route quality or excessive time overhead, particularly under large-scale query keywords. To address this challenge, we introduce the DO framework, which pioneers the employ Deep Reinforcement Learning for the ORCSK. Specifically, DO first integrates the spatial index with the H2H index to generate and refine high-quality candidate sets. Subsequently, DO utilizes a Transformer-based model to determine the optimal route from the sets. To effectively combine spatial distance and POI attributes, we propose a novel dual-cross encoder architecture. Furthermore, leveraging this architecture, we introduce a multi-route generating strategy, exploiting parallel computing to enhance route quality. Our experiments on real-life road networks demonstrate superior route quality and response time compared to the state-of-the-art method, with an average improvement of 1-2 orders of magnitude in response time, and maintain high efficiency even under large-scale query keywords or dynamic POI attributes scenarios.

The advancement of navigation systems has generated numerous future route data. However, neglecting such data could deteriorate the future traffic condition, as it reflects the actual state of future traffic flow. In this demonstration, we propose a route data management system (RouteSys), for the efficient and accurate prediction of future traffic conditions. First, a macroscopic traffic simulation algorithm integrated with multiple light weight machine learning models is developed to simulate the future traffic condition of routes. Then, the future temporal information is stored in a route record index structure. In real-world scenarios, it can efficiently update simulated traffic conditions in response to dynamic changed future route data, such as newly added routes. To demonstrate the functionality of RouteSys, we design a front-end platform within a real-world road network scenario with the generated route data. A video demonstration is available at https://youtu.be/3xuF2t_pV2M.

Traffic forecasting is essential for intelligent transportation systems, aiming to predict future traffic dynamics such as speed and travel time through the analysis of past observations. However, mainstream deep learning frameworks, which rely heavily on historical data, often struggle in realworld applications due to their inadaptability to dynamic future changes, neglect of future traffic flow as the root cause of traffic conditions, and the complexity of model structures for city-scale road networks. To solve these limitations, we propose a Route Data Management System (RouteSys) that integrates a macroscopic simulation module with lightweight traffic prediction models to estimate the future traffic conditions on individual road segments by accurately and efficiently simulating vehicle travel sequences and traffic states in advance. Additionally, we integrate the microscopic traffic simulation tool SUMO with the custom route planning logic to generate synthetic route data, supporting model training and application evaluation. RouteSys has been validated on real-world road networks in various scenarios, showing substantial improvements in prediction accuracy, efficiency, and scalability compared to the mainstream structures.

Traffic prediction plays a crucial role in urban transportation systems, yet existing methods face challenges in achieving real-time performance when handling large-scale road networks. This paper introduces a novel Just-In-Time Traffic Prediction framework that integrates traffic condition with routing queries for efficient localized predictions in multi-query urban environments. Unlike traditional approaches that perform global predictions across entire networks, our framework partitions the road network into non-overlapping small regions and selectively updates traffic conditions based on query demands. Specifically, we propose three key components: (i) a Search Space Estimation (SSE) model that reformulates search space determination of routing queries as a binary classification task to accurately identify the searched regions; (ii) a Region-based Traffic Speed Prediction (RTSP) model that incorporates the temporal validity of speed profiles in adjacent regions and comprehensive spatio-temporal features for precise region-based traffic prediction; (iii) a Global Region Prediction Scheduling that efficiently coordinates the SSE and RTSP models to maintain up-to-date traffic data for running queries while minimizing computational overhead from both spatio and temporal dimensions. Experimental results on real-world road networks demonstrate significant improvements in both effectiveness and efficiency compared to state-of-the-arts.

Shortest path (SP) computation is the building block for many location-based services, and achieving high throughput SP query processing with real-time response is crucial for those services. However, existing solutions can hardly handle high throughput queries on large dynamic road networks due to either slow query efficiency or poor dynamic adaption. In this paper, we leverage graph partitioning and propose novel Partitioned Shortest Path (PSP) indexes to address this problem. Specifically, we first put forward a cross-boundary strategy to accelerate the query processing of PSP index and analyze its efficiency upper bound theoretically. After that, we propose a non-trivial Partitioned Multi-stage Hub Labeling (PMHL) that subtly aggregates multiple PSP strategies to achieve fast index maintenance and consecutive query efficiency improvement during index update. Lastly, to further optimize throughput, we design tree decomposition-based graph partitioning and propose Post-partitioned MHL (PostMHL) with faster query processing and index update. Experiments on real-world road networks show that our methods outperform state-of-the-art baselines in query throughput, yielding up to 2 orders of magnitude improvement.

Mining cohesive subgraphs in bipartite graphs is of great importance to various real-world applications such as recommendation in e-commercial systems and fraud detections in social networks. In this paper, we study the problem of Bitruss Decomposition of a given bipartite graph G. The goal is to compute, for each edge e, the largest value of k such that e is still contained in a k-bitruss. Here, a k-bitruss is a maximal subgraph of G such that every edge of it is contained in at least k butterflies (i.e(2,2)-cliques) in the subgraph. All the previous state-of-the-art solutions are based on the well-known Peeling Process framework and have to ''touch'' every butterfly in the graph G for at least once, causing a O(⧖G) cost, where ⧖G is the number of butterflies in G. In the worst case, ⧖G can be as large as O(m2), where m is the number of edges in G. We propose the first algorithm called BiT-DT, whose running time is bounded by O(m^1.5 log m), significantly improving the state-of-the-art bound by roughly a factor of O(√m). The crucial idea of our algorithm is an efficient approach to identify the edges to be peeled next in the Peeling Process without maintaining a precise butterfly support for each edge. To further enhance the practical performance of our BiT-DT algorithm, we propose a heuristic to peel the edges in batch. Extensive experimental results on ten real-world datasets show that our proposed algorithm outperforms the state-of-the-art baselines by up to an order of magnitude in terms of running time.

Automated Guided Vehicles (AGV) are becoming increasingly important in modern warehouses to cope with the enormous logistic demands of developing e-commerce and the growing operational costs. The key component of implementing such a system is planning the paths of a large horde of AGVs to deliver orders from shelves to packing locations. The existing solutions regard it as a Multi Agent PathFinding (MAPF) problem, but they can hardly be applied in practice because none of them could satisfy the continuous (temporal), lifelong (future task unknown and keeps appearing), kinematic (acceleration/deceleration/rotation), online (fast response), and scalability (large network, large AGV number, large task number) at the same time. Therefore, we first propose an AGV routing framework that can satisfy all these properties with its corresponding routing algorithm. Then, to improve the efficiency, we propose the Multi-Hop Conflict-Aware Search method (MHCAS) with action combination, MHSC to reduce the search space, and OHSMD to decompose motions such that routing time is reduced by three orders of magnitude. Extensive experimental studies verify the superiority of our methods compared with the state-of-the-art.

Shortest path computation is ubiquitous in various applications in road networks and the index-based algorithms, especially hub labeling, can boost the query performance dramatically. However, traffic conditions keep changing in real life, making the precomputed index unable to answer the query correctly. In this work, we adopt the state-of-the-arttree decomposition-based hub labeling (TDHL)as the underlying index and design efficient algorithms to incrementally maintain the index. Specifically, we first analyze the structural stability of the index in dynamic road networks which enables us to concentrate on label value maintenance. We then introduce theminimum weight propertyandminimum distance propertyto guarantee index correctness without graph traversal. Moreover, we propose thestar-centric paradigmfor tracing index change and design various pruning techniques to further accelerate index maintenance. We also extend our algorithms to batch mode for shared computation, to structural maintenance for full types of updates, and generalize to all kinds ofTDHL. Finally, we further improve the index maintenance efficiency and scalability of our algorithms by leveraging graph partition. Our experimental results validate the superiority of our proposals over existing solutions on both index maintenance and query processing.

Abstract With the development of location-based services, smart cities, and intelligent transportation, route planning has evolved beyond shortest path finding to satisfy user’s flexible travel purposes through the Optimal Routes with Collective Spatial Keywords (ORCSK) routing. Because different Points of Interest (POIs) contain different sets of keywords, the user usually needs to visit multiple POIs to fulfill all needs. Moreover, the POIs’ stop hardness (time and cost) also influences user experience, but it was ignored by the existing solutions. Therefore, this work proposes to extend the ORCSK problem into Skyline Optimal Routes with Collective Spatial Keyword (Sky-ORCSK) by considering both distance and stop hardness. Specifically, we first propose the IG-Sky algorithm from the spatial keyword search perspective by extending the IG-Tree. Then we propose the DA-Sky algorithm from the path enumeration perspective by extending our previous DA-CSK. Furthermore, five optimization strategies are proposed to improve efficiency by pruning the search space. Extensive experimental evaluations on real-world datasets demonstrate the algorithms’ efficacy and reliability, marking a significant step forward in refined route planning for modern urban environments.

The Constrained Shortest Path (CSP) problem seeks to identify the shortest path between two vertices in a road network while adhering to a specific constraint on another criterion. Solving the CSP problem frequently entails navigating the two-criteria skyline path problem, which incurs a substantial computational expense in large road networks. The primary challenge lies in handling a vast quantity of partial skyline paths, which often hinders index-based solutions from accurately determining the skyline paths. This paper introduces a-FHL, a practical approximation method designed to circumvent the costly skyline path search and hasten computation on skyline path indexing. a-FHL uses tree decomposition to hierarchically assign approximation ratios, thereby facilitating effective pruning within the labelling index. Moreover, we devise various strategies to allocate approximation ratios and an efficient approximation concatenation method to respond to the approximate CSP queries via the a-FHL index. Our method culminates in swift index construction and efficient query response. Comprehensive exper-iments conducted on real-world road networks substantiate the superiority of our approach over contemporary solutions

Route planning and navigation systems have played an increasingly important role in our society and have a growing impact on transportation systems. The current system takes the traffic prediction as input and optimizes the routes individually. However, such a paradigm could generate congestion and deteriorate traffic conditions because the routing algorithms are not aware of their results' influence on the traffic flow. Therefore, in this paper, we identify this flaw in the current paradigm and propose a route data management system to evaluate the influence of the routing results and help improve future downstream tasks. Specifically, we first formulate traffic evaluation as a clear traffic-aware network time calibration problem and propose a simulation-based method to evaluate hundreds of thousands of routes efficiently. To support route updates on the evaluation results, we propose an RR-Index to support high throughput of route insertion, deletion, and temporal update. After that, we propose several techniques like influence terminate condition, propagation merge and ordering, and parallel processing to make it efficient enough to work in real life. Evaluations on real-world road networks verify the necessity, effectiveness, and efficiency of our methods.

In this paper, we revisit the problem of the current routing system in terms of prediction scalability and routing result optimality. Specifically, the current traffic prediction models are not suitable for large urban networks due to the incomplete information of traffic conditions. Besides, existing routing systems can only plan the routes based on the past traffic conditions and struggle to update the optimal route for vehicles in real-time. As a result, the actual route taken by vehicles is different from the ground-truth optimal path. Therefore, we propose a Just-In-Time Predictive Route Planning framework to tackle these two problems. Firstly, we propose a Travel Time Constrained Top-$k^{n}$Shortest Path algorithm which pre-computes a set of candidate paths with several switch points. This empowers vehicles to continuously have the opportunity to switch to better paths taking into account real-time traffic condition changes. Moreover, we present a query-driven prediction paradigm with ellipse-based searching space estimation, along with an efficient multi-queries handling mechanism. This not only allows for targeted traffic prediction by prioritizing regions with valuable yet outdated traffic information, but also provides optimal results for multiple queries based on real-time traffic evolution. Evaluations on two real-life road networks demonstrate the effectiveness and efficiency of our framework and methods.

Shortest path computation is a fundamental operation of many applications in small-world networks, and shortest path index has been extensively studied to achieve high query efficiency. However, small-world networks evolve continuously in real life, and their graph size expands rapidly, necessitating the investigation of efficient shortest path index maintenance and construction for large dynamic graphs. In this paper, we adopt the Core-Tree index, which has exceptional scalability while preserving high query efficiency, as the underlying shortest path index, and put forward efficient algorithms to maintain and construct it for large dynamic small-world networks. Specifically, we first propose update propagation mechanisms for our Dynamic Core-Tree (DCT) algorithm, based on which the global tree index strategy is designed for efficient query processing. Moreover, for the core index, we propose a Propagation-based Dynamic PLL incorporating coarse update and refined update phases to ensure correct and efficient index maintenance. To enhance update efficiency and scalability for the core index, we also propose novel Parallel Canonical 2-hop Labeling (PCL) and Batch PCL (BPCL) to efficiently generate minimal canonical labels and pruning point records. Experimental studies on large real-world datasets demonstrate the superiority of our methods over the state-of-the-art in terms of indexing, updating, and scalability.

Shortest distance computation is a fundamental operation in graph-related applications, especially in location-based services. The most efficient method is hop-labeling, which can answer queries in microseconds. However, when the traffic condition changes dynamically, they need a long time to maintain or an even longer time to re-construct, making it hard to catch up with numerous or frequent updates. As a result, real-life applications still rely on slow graph searching algorithms. To improve the hop labeling construction efficiency, we resort to GPU for its high parallelism power and propose the G2H index. Specifically, we first analyze the relation of the graph partitions, index performance, and parallelism to identify the most suitable partition scheme for G2H, with a hybrid scheme and optimized node ordering for faster contraction. Then, we propose a label-pruning method to reduce the label construction workload with several strategies designed to balance and improve the parallel label construction. Finally, experiments on real-life networks show that our G2H can finish construction within seconds for large urban networks and under one minute for large region networks with 6M vertices, which is several times faster than the state-of-the-art methods. Besides, G2H can answer hundreds of millions of queries per second, achieving two orders of magnitude acceleration.

The uniqueness of trajectory data for user re-identification has received unprecedented attention as the increasing popularity of location-based services boosts the excessive collection of daily trajectories with sufficient spatiotemporal coverage. Consequently, leveraging or releasing personally-sensitive trajectories without proper protection severely threatens individual privacy despite simply removing IDs. Trajectory privacy protection is never a trivial task due to the trade-off between privacy protection, utility preservation, and computational efficiency. Furthermore,recovery attack, one of the most threatening attacks specific to trajectory data, has not been well studied in the current literature. To tackle these challenges, we propose a frequency-based randomization model with a rigorous differential privacy guarantee for privacy-preserving trajectory data publishing. In particular, two randomized mechanisms are introduced for perturbing the local/global frequency distributions of a limited number of significantly essential locations in trajectories by injecting special Laplace noises. To reflect the perturbed distributions on the trajectory level without losing privacy guarantee or data utility, we formulate the trajectory modification tasks as kNN search problems and design two hierarchical indices with powerful pruning strategies and a novel search algorithm to support efficient modification. Extensive experiments on a real-world dataset verify the effectiveness of our approaches in resisting individual re-identification and recovery attacks simultaneously while still preserving desirable data utility. The efficient performance on large-scale data demonstrates the feasibility and scalability in practice.

Travel planning plays an increasingly important role in our society. The travel plans, which consist of the paths each vehicle is suggested to follow and its corresponding departure time, influence the traffic conditions naturally. However, existing travel planning algorithms cannot consider the planning results and their influences simultaneously, so traffic congestion could be created when many vehicles are directed to adopt similar travel plans. In this paper, we propose theGlobal Optimal Travel Planning (GOTP)problem that aims to minimize traffic congestion by continuously evaluating traffic conditions for a set of planning tasks. Achieving this global optimization goal is non-trivial because travel planning and traffic evaluation are time-consuming and interdependent. To break this dependency, we first propose aGOTPparadigm that interleaves travel planning and traffic evaluation for queries, where the planning consists of departure time planning and travel path planning. To implement the paradigm, we propose theserial modelthat optimizes travel plans one by one, followed by thebatch modelthat improves processing efficiency, and theiterative modelthat further optimizes planning quality. Extensive experiments on large real-world networks with synthetic and real workloads validate the effectiveness and efficiency of our methods.

Shortest path computation is a basic operation for many graph-based applications and has been extensively studied. However, most existing works only consider the optimal path of a single criterion but ignore real-world situations involving multiple criteria. This paper investigates a new Multi-Criteria Shortest Paths (MCSPs) problem, aiming to compute the shortest paths of all criteria between a vertex pair. It is significant for real-world applications such as GPS navigation and social network analysis. Nevertheless, the rapid growth of graph size or memory-limited devices poses a memory-constraint challenge, making the adaptation of existing methods extremely time-consuming. To solve the memory-constraint MCSPs problem, we propose a generalSTOP & SHAREscheme to synchronize the search speeds of all criteria for sharing partition accesses. Two algorithms calledOHPandMHP, adopting the one-hop strategy and partition exhaustive strategy, respectively, are proposed for implementing our scheme. Moreover, we develop two optimized algorithms,BMHPandBMHPS, to improve query efficiency by combiningMHPwith the bidirectional technique and a novelin-partition shortcut optimization. We also investigatepartition-oriented I/O management. Experimental studies on large real-world graphs demonstrate the effectiveness of the proposed methods over the multi-pass adaptations of the existing methods.

As more detailed POI (Point of Interest) information has been incorporated into road network, routing has evolved from finding paths from one place to another, to satisfying users’ needs (keywords) along the trip. However, the existing solutions either only support one keyword per POI, or require a fixed visiting order, or only provide one option to choose from. Therefore, we study the top-k Optimal Routes with Collective Spatial Keywords (k-ORCSK) problem, which is the most general keyword-aware routing problem that supports multiple keywords, arbitrary orders, and top-k results. To solve this problem, we apply an enumeration framework and reduce the complexity by contracting non POI-related vertices and taking the keywords into account. After that, we propose a best-first path expansion method DA-CSK based on deviation to convert the enumeration paradigm from the distance-oriented to the keyword-oriented. Finally, several optimization techniques are provided to further improve the query efficiency. Extensive experiments conducted on multiple real-life road networks show that our method can provide higher quality results more efficiently.

Route planning plays an increasingly important role in our society, and the routing results, which are the paths that vehicles actually travel in a road network, which influence the traffic condition naturally. However, the existing routing algorithms cannot consider the routing results and their influence simultaneously, so traffic congestion could be created when many vehicles are directed to follow similar routes. In this paper, we propose the Global Routing Optimization problem that aims to minimize traffic congestion by continuously evaluating traffic conditions for a set of routing tasks. It is non-trivial to achieve this global optimization goal, as routing and traffic condition evaluation is both time-consuming and interdependent. To break this dependency, we propose a global routing optimization paradigm that can evaluate the routing results’ influence on the traffic condition, and then plan the routes accordingly. To implement it, we first propose a serial model to optimize the next route, followed by a batch model to improve processing efficiency. After that, an iterative model is proposed to further optimize route qualities. Extensive experiments on large real-world networks with synthetic and real workloads validate the effectiveness and efficiency of our methods.

Shortest path computation is a fundamental operation in many application domains and is especially challenging in frequently evolving small-world networks (i.e., graphs in which many nodes can be reached from every other node by a small number of hops). Index-based methods, especially ones based on 2-hop labeling are often used for high query efficiency. However, the evolvements of small-world networks in many realistic scenarios pose the challenge of efficient maintenance of the shortest path index. In this work, we adopt the state-of-the-artParallel Shortest-distance Labeling (PSL)as the underlying 2-hop labeling construction method, and design algorithms to support its efficient update given edge weight changes (increase and decrease). Specifically, we focus on weightedPSL (WPSL)and propose a propagation-based update mechanism for both synchronous and asynchronous propagation. We also identify thecurse of pruning powerin the edge weight increase case, and solve it with a balance between index size and effectiveness. Followed by, we extend the asynchronous propagation method toPruned Landmark Labeling (PLL)for faster index maintenance and query processing with a smaller index size. Finally, we further optimize the index performance by reducing the index size through graph contraction and accelerating the index update through parallelized mix index update. Our experimental results on real-life and synthetic networks demonstrate the superiority of our algorithms over the relevant baselines on index maintenance.

Abstract In this paper, we study the Time-Dependent k Nearest Neighbor (TD- k NN) query on moving objects that aims to return k objects arriving at the query location with the least traveling cost departing at a given time t . Although the k NN query on moving objects has been widely studied in the scenario of the static road network, the TD- k NN query tends to be more complicated and challenging because under the time-dependent road network, the cost of each edge is measured by a cost function rather than a fixed distance value. To tackle such difficulty, we adopt the framework of GLAD and develop an advanced index structure to support efficient fastest travel cost query on time-dependent road network. In particular, we propose the Time-Dependent H2H (TD-H2H) index, which pre-computes the aggregated weight functions between each node to some specific nodes in the decomposition tree derived from the road network. Additionally, we establish a grid index on moving objects for candidate object retrieval and location update. To further accelerate the TD- k NN query, two pruning strategies are proposed in our solution. Apart from that, we extend our framework to tackle the time-dependent approachable k NN (TD-A k NN) query on moving objects targeting for the application of taxi-hailing service, where the moving object might have been occupied. Extensive experiments with different parameter settings on real-world road network show that our solutions for both TD- k NN and TD-A k NN queries are superior to the competitors in orders of magnitude.

Multi-Constraint Shortest Path ( MCSP ) generalizes the classic shortest path from single to multiple criteria such that more personalized needs can be satisfied. However, MCSP query is essentially a high-dimensional skyline problem and thus time-consuming to answer. Although the current Forest Hop Labeling (FHL) index can answer MCSP efficiently, it takes a long time to construct and lacks the flexibility to handle arbitrary criteria combinations. In this paper, we propose a skyline-cube-based FHL index that can handle the flexible MCSP efficiently. Firstly, we analyze the relation between low and high-dimensional skyline paths theoretically and use a cube to organize them hierarchically. After that, we propose methods to derive the high-dimensional path from the lower ones, which can adapt to the flexible scenario naturally and reduce the expensive high dimensional path concatenation. Then we introduce efficient methods for both single and multi-hop cube concatenations and propose pruning methods to further alleviate the computation. Finally, we improve the FHL structure with lower height for faster construction and query. Experiments on real-life road networks demonstrate the superiority of our method over the state-of-the-art.

Route planning is ubiquitous and has a profound impact on our daily life. However, the existing path algorithms tend to produce similar paths between similar OD (Origin-Destination) pairs because they optimize query results without considering their influence on the whole network, which further introduces congestions. Therefore, we investigate the problem of diversifying the top-k paths between an OD pair such that their similarities are under a threshold while their total length is minimal. However, the current solutions all depend on the expensive graph traversal which is too slow to apply in practice. Therefore, we first propose an edge deviation and concatenation-based method to avoid the expensive graph search in path enumeration. After that, we dive into the path relations and propose a path similarity computation method with constant complexity, and propose a pruning technique to improve efficiency. Finally, we provide the completeness and efficiency-oriented solutions to further accelerate the query answering. Evaluations on the real-life road networks demonstrate the effectiveness and efficiency of our algorithm over the state-of-the-art.

Finding the fastest path in the time-dependent road network is time consuming because its problem complexity is$\Omega (T(|V|\log |V|+|E|))$, where$T$is the size of the result's time-dependent function,$|V|$and$|E|$are the number of vertices and edges. There are three kinds of fastest path problems:SSFP (Single-Staring Time Fastest Path)that has a fixed departure time,ISFP (Interval-Staring Time Fastest Path)that selects the best departure time from an interval, andFPP (Fastest Path Profile)that returns the travel time of the entire time domain. In this paper, we aim to answer these three queries in time-dependent road network faster by extending the2-hop labelingapproach, which is fast in answering shortest distance query in the static graph. However, it is hard to construct index forSSFPandISFPbecause there are$|\mathcal {T}|$and$|\mathcal {T}|^2$possible time points and intervals, where$\mathcal {T}$is the time domain. Therefore, we first propose thetime-dependent hop-labelingforFPP, then provide the specific optimizations forSSFPandISFPquery answering. Moreover, it is both time and space consuming to build an index in a large time-dependent graph, so we partition road network into smaller sub-graphs and build indexes within and between the partitions. Furthermore, we propose an online approximation techniqueAT-Dijkstraand abottom-upcompression method to further reduce the label size, save construction time and speedup query answering. Experiments on real world road network show that our approach outperforms the state-of-art fastest path index approaches and can speed up the query answering by hundreds of times.

Shortest path query in road network is pervasive in various location-based services nowadays. As the business expands, the scalability issue becomes severer and more servers are deployed to cope with it. Moreover, as the traffic condition keeps changing over time, the existing index-based approaches can hardly adapt to the real-life dynamic environment. Therefore, batch shortest path algorithms have been proposed recently to answer a set of queries together using shareable computation. Besides, they can also work in a highly dynamic environment as no index is needed. However, the existing batch algorithms either assume the batch queries are finely decomposed or just process them without differentiation, resulting in poor query efficiency. In this work, we assume the traffic condition is stable over a short period and treat the issued queries within that period as a stream of query sets. Specifically, we first propose three query set decomposition methods to cluster one query set into multiple query subsets:Zigzagthat considers the1-Nshared computation;Co-Clusteringthat considers the source and target's spatial locality; andSearch-Space-Awarethat further incorporates search space estimation. After that, we propose two batch algorithms that take advantage of the previously decomposed query sets for efficient query answering:R2Rthat finds a set of approximate shortest paths from one region to another with bounded error; andLocal Cachethat improves the existingGlobal Cachewith higher cache hit ratio. Finally, we design three efficient stream processing methods for intra-batch shared computation. The experiments on a large real-world query sets verify the effectiveness and efficiency of our decomposition methods compared with the state-of-the-art batch algorithms.

The Constrained Shortest Path (CSP) problem aims to find the shortest path between two nodes in a road network subject to a given constraint on another attribute. It is typically processed as a skyline path problem on the two attributes, resulting in very high computational cost which can be prohibitive for large road networks. The main bottleneck is to deal with a large amount of partial skyline paths, which further makes the existing index-based methods incapable to obtain the complete exact skyline paths. In this paper, we propose a novel skyline path concatenation approach to avoid the expensive skyline path search, which is then used to efficiently construct a 2-hop labeling index for the CSP queries. Specifically, a rectangle-based technique is designed to prune the concatenation space from multiple hops, and a constraint pruning method is used to further speed up the CSP query processing. To further scale up to larger networks, we propose a novel forest hop labeling that constructs labels from different partitions in parallel. Our approach is the first method that can achieve both accuracy and efficiency for CSP query answering. Extensive experiments on real-life road networks demonstrate that our method outperforms the state-of-the-art CSP solutions by several orders of magnitude.

Shortest path computation is a fundamental operation in small-world networks and index-based methods, especially 2-hop labeling, are commonly applied which have achieved high query efficiency. However, small-world networks keep evolving in real life, making it indispensable to study the maintenance of shortest path index. In this work, we adopt the state-of-the-art Parallel Shortest-distance Labeling (PSL) as the underlying 2-hop labeling construction method, and design algorithms to support efficient update of the index given edge weight change (increase and decrease) in the network. Specifically, we focus on weighted PSL (WPSL) and propose the update propagation mechanism for both synchronous propagation and asynchronous propagation. We then identify the curse of pruning power generated for the propagation under edge weight increase, and solve this problem with a balance between index size and effectiveness. Finally, we extend the proposed asynchronous propagation method to Pruned Landmark Labeling (PLL) for faster index maintenance and query processing with smaller index size. Our experimental results on real-life and synthetic networks demonstrate the superiority of our algorithms on index maintenance.

Shortest path finding is the building block of various applications in road networks and the index-based algorithms, especially hub labeling, can boost the query performance dramatically. However, the traffic condition keeps changing in real life, making the pre-computed index unable to answer the query correctly. In this work, we adopt the state-of-the-art tree decomposition-based hub labeling as the underlying index, and design efficient algorithms to incrementally maintain the index. Specifically, we first analyze the structural stability of the index in dynamic road networks which enables us to concentrate on label value maintenance. We then introduce the minimum weight property and minimum distance property to guarantee the index correctness without graph traversal. Moreover, we propose the star-centric paradigm for tracing index change and design various pruning techniques to further accelerate the index maintenance. Finally, we extend our algorithms to batch mode for shared computation, extend to structural maintenance for full types of update, and generalize to all kinds of TDHL. Our experimental results validate the superiority of our proposals over existing solutions on both index maintenance and query processing.

Shortest path computation is a building block of various network applications. Since real-life networks evolve as time passes, the Dynamic Shortest Path (DSP) problem has drawn lots of attention in recent years. However, as DSP has many factors related to network topology, update patterns, and query characteristics, existing works only test their algorithms on limited situations without sufficient comparisons with other approaches. Thus, it is still hard to choose the most suitable method in practice. To this end, we first identify the determinant dimensions and constraint dimensions of the DSP problem and create a complete problem space to cover all possible situations. Then we evaluate the state-of-the-art DSP methods under the same implementation standard and test them systematically under a set of synthetic dynamic networks. Furthermore, we propose the concept of dynamic degree to classify the dynamic environments and use throughput to evaluate their performance. These results can serve as a guideline to find the best solution for each situation during system implementation and also identify research opportunities. Finally, we validate our findings on real-life dynamic networks.

Shortest path query is a fundamental operation in various location-based services (LBS) and most of them process queries on the server-side. As the business expands, scalability becomes a severe issue. Instead of simply deploying more servers to cope with the quickly increasing query number, batch shortest path algorithms have been proposed recently to answer a set of queries together using shareable computation. Besides, they can also work in a highly dynamic environment as no index is needed. However, the existing batch algorithms either assume the batch queries are finely decomposed or just process them without differentiation, resulting in poor query efficiency. In this paper, we aim to improve the performance of batch shortest path algorithms by revisiting the problem of query clustering. Specifically, we first propose three query decomposition methods to cluster queries: Zigzag that considers the 1-N shared computation; Search-Space Estimation that further incorporates search space estimation; and Co-Clustering that considers the source and target's spatial locality. After that, we propose two batch algorithms that take advantage of the previously decomposed query sets for efficient query answering: Local Cache that improves the existing Global Cache with higher cache hit ratio, and R2R that finds a set of approximate shortest paths from one region to another with bounded error. Experiments on a large real-world query sets verify the effectiveness and efficiency of our decomposition methods compared with the state-of-the-art batch algorithms.

Route scheduling on time-dependent road network is slow due to its problem complexity of Ω(T(|V|log |V|+|E|)), where T is the size of the result's time-dependent function, |V| is the number of vertices and |E| is the number of edges. To make things worse, T grows larger as the route becomes longer or the query time interval becomes bigger, especially for a fastest path profile query whose time interval is 24 hours. In this paper, we aim to answer the fastest path profile query on time-dependent road network faster by extending the 2-hop labeling approach, which is fast in answering shortest distance query on the static graph. However, building an index on a time-dependent graph is both time and space consuming, so currently only online-search approach exist. Apparently, its query answering power is limited by the online searching. To solve this problem, we first propose the time-dependent hop on large road network by partitioning it into smaller sub-graphs. The index is built within and between the partitions, and is retrieved from disk during query answering with the help of sampling. Moreover, we propose an online approximation technique AT-Dijkstra and a bottom-up compression method to further reduce the label size, save construction time and speedup query answering. Experiments on real world road network show that our approach outperforms the state-of-art fastest path index approaches and can speed up the query answering by hundreds of times.

Finding the shortest path from one place to another is an essential operation for various location-based services (LBS), and most of the computations run on the server side. However, as the business grows, the service providers are facing an increasing swarm of path requests submitted during a short time period. The most straightforward solution is deploying more servers, while the operation cost increases at the same time. Therefore, in this work, we aim to improve the efficiency algorithmically by answering a large set of shortest path queries in a batch and reusing sharable computations. Specifically, we first propose the petal A*-1N algorithm to process 1-N shortest path queries by batch without repeated computation. Then we introduce several decomposition methods to cluster the start/target set and answer the whole query set with zigzag scheduling methods to further reduce the total running time. Extensive evaluations on both synthetic and real-world data verify the superiority of our algorithm compared with state-of-the-art methods.

On time-dependent graphs, fastest path query is an important problem and has been well studied. It focuses on minimizing the total travel time (waiting time + on-road time) but does not allow waiting on any intermediate vertex if the FIFO property is applied. However, in practice, waiting on a vertex can reduce the time spent on the road (for example, resuming traveling after a traffic jam). In this paper, we study how to find a path with the minimal on-road time on time-dependent graphs by allowing waiting on some predefined parking vertices. The existing works are based on the following fact: the arrival time of a vertex v is determined by the arrival time of its in-neighbor u , which does not hold in our scenario since we also consider the waiting time on u if u allows waiting. Thus, determining the waiting time on each parking vertex to achieve the minimal on-road time becomes a big challenge, which further breaks FIFO property. To cope with this challenging problem, we propose two efficient algorithms using minimum on-road travel cost function to answer the query. The evaluations on multiple real-world time-dependent graphs show that the proposed algorithms are more accurate and efficient than the extensions of existing algorithms. In addition, the results further indicate, if the parking facilities are enabled in the route scheduling algorithms, the on-road time will reduce significantly compared to the fastest path algorithms.