Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userShortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice
322
0
0.0
(
0
)
Added by
Xiaokui Xiao
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Given two locations $s$ and $t$ in a road network, a distance query returns the minimum network distance from $s$ to $t$, while a shortest path query computes the actual route that achieves the minimum distance. These two types of queries find important applications in practice, and a plethora of solutions have been proposed in past few decades. The existing solutions, however, are optimized for either practical or asymptotic performance, but not both. In particular, the techniques with enhanced practical efficiency are mostly heuristic-based, and they offer unattractive worst-case guarantees in terms of space and time. On the other hand, the methods that are worst-case efficient often entail prohibitive preprocessing or space overheads, which render them inapplicable for the large road networks (with millions of nodes) commonly used in modern map applications. This paper presents {em Arterial Hierarchy (AH)}, an index structure that narrows the gap between theory and practice in answering shortest path and distance queries on road networks. On the theoretical side, we show that, under a realistic assumption, AH answers any distance query in $tilde{O}(log r)$ time, where $r = d_{max}/d_{min}$, and $d_{max}$ (resp. $d_{min}$) is the largest (resp. smallest) $L_infty$ distance between any two nodes in the road network. In addition, any shortest path query can be answered in $tilde{O}(k + log r)$ time, where $k$ is the number of nodes on the shortest path. On the practical side, we experimentally evaluate AH on a large set of real road networks with up to twenty million nodes, and we demonstrate that (i) AH outperforms the state of the art in terms of query time, and (ii) its space and pre-computation overheads are moderate.
rate research
Read More
Computing the shortest path between two given locations in a road network is an important problem that finds applications in various map services and commercial navigation products. The state-of-the-art solutions for the problem can be divided into two categories: spatial-coherence-based methods and vertex-importance-based approaches. The two categories of techniques, however, have not been compared systematically under the same experimental framework, as they were developed from two independent lines of research that do not refer to each other. This renders it difficult for a practitioner to decide which technique should be adopted for a specific application. Furthermore, the experimental evaluation of the existing techniques, as presented in previous work, falls short in several aspects. Some methods were tested only on small road networks with up to one hundred thousand vertices; some approaches were evaluated using distance queries (instead of shortest path queries), namely, queries that ask only for the length of the shortest path; a state-of-the-art technique was examined based on a faulty implementation that led to incorrect query results. To address the above issues, this paper presents a comprehensive comparison of the most advanced spatial-coherence-based and vertex-importance-based approaches. Using a variety of real road networks with up to twenty million vertices, we evaluated each technique in terms of its preprocessing time, space consumption, and query efficiency (for both shortest path and distance queries). Our experimental results reveal the characteristics of different techniques, based on which we provide guidelines on selecting appropriate methods for various scenarios.
The determination of time-dependent collision-free shortest paths has received a fair amount of attention. Here, we study the problem of computing a time-dependent shortest path among growing discs which has been previously studied for the instance where the departure times are fixed. We address a more general setting: For two given points $s$ and $d$, we wish to determine the function $mathcal{A}(t)$ which is the minimum arrival time at $d$ for any departure time $t$ at $s$. We present a $(1+epsilon)$-approximation algorithm for computing $mathcal{A}(t)$. As part of preprocessing, we execute $O({1 over epsilon} log({mathcal{V}_{r} over mathcal{V}_{c}}))$ shortest path computations for fixed departure times, where $mathcal{V}_{r}$ is the maximum speed of the robot and $mathcal{V}_{c}$ is the minimum growth rate of the discs. For any query departure time $t geq 0$ from $s$, we can approximate the minimum arrival time at the destination in $O(log ({1 over epsilon}) + loglog({mathcal{V}_{r} over mathcal{V}_{c}}))$ time, within a factor of $1+epsilon$ of optimal. Since we treat the shortest path computations as black-box functions, for different settings of growing discs, we can plug-in different shortest path algorithms. Thus, the exact time complexity of our algorithm is determined by the running time of the shortest path computations.
Sampling theory encompasses all aspects related to the conversion of continuous-time signals to discrete streams of numbers. The famous Shannon-Nyquist theorem has become a landmark in the development of digital signal processing. In modern applications, an increasingly number of functions is being pushed forward to sophisticated software algorithms, leaving only those delicate finely-tuned tasks for the circuit level. In this paper, we review sampling strategies which target reduction of the ADC rate below Nyquist. Our survey covers classic works from the early 50s of the previous century through recent publications from the past several years. The prime focus is bridging theory and practice, that is to pinpoint the potential of sub-Nyquist strategies to emerge from the math to the hardware. In that spirit, we integrate contemporary theoretical viewpoints, which study signal modeling in a union of subspaces, together with a taste of practical aspects, namely how the avant-garde modalities boil down to concrete signal processing systems. Our hope is that this presentation style will attract the interest of both researchers and engineers in the hope of promoting the sub-Nyquist premise into practical applications, and encouraging further research into this exciting new frontier.
Finding the shortest paths in road network is an important query in our life nowadays, and various index structures are constructed to speed up the query answering. However, these indexes can hardly work in real-life scenario because the traffic condition changes dynamically, which makes the pathfinding slower than in the static environment. In order to speed up path query answering in the dynamic road network, we propose a framework to support these indexes. Firstly, we view the dynamic graph as a series of static snapshots. After that, we propose two kinds of methods to select the typical snapshots. The first kind is time-based and it only considers the temporal information. The second category is the graph representation-based, which considers more insights: edge-based that captures the road continuity, and vertex-based that reflects the region traffic fluctuation. Finally, we propose the snapshot matching to find the most similar typical snapshot for the current traffic condition and use its index to answer the query directly. Extensive experiments on real-life road network and traffic conditions validate the effectiveness of our approach.
In two-stage robust optimization the solution to a problem is built in two stages: In the first stage a partial, not necessarily feasible, solution is exhibited. Then the adversary chooses the worst scenario from a predefined set of scenarios. In the second stage, the first-stage solution is extended to become feasible for the chosen scenario. The costs at the second stage are larger than at the first one, and the objective is to minimize the total cost paid in the two stages. We give a 2-approximation algorithm for the robust mincut problem and a ({gamma}+2)-approximation for the robust shortest path problem, where {gamma} is the approximation ratio for the Steiner tree. This improves the factors (1+sqrt2) and 2({gamma}+2) from [Golovin, Goyal and Ravi. Pay today for a rainy day: Improved approximation algorithms for demand-robust min-cut and shortest path problems. STACS 2006]. In addition, our solution for robust shortest path is simpler and more efficient than the earlier ones; this is achieved by a more direct algorithm and analysis, not using some of the standard demand-robust optimization techniques.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
