PaperlayerView exact revision on arXiv

Source-linked AI summary

Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation

Lingkun Wu, Xiaokui Xiao, Dingxiong Deng, Gao Cong, Andy Diwen Zhu, Shuigeng Zhou

arXiv:1201.6564v1cs.DB

TL;DR

Shortest-path research lacked a systematic comparison of spatial-coherence-based and vertex-importance-based methods across realistic scales and both query types. This paper evaluates the techniques on real road networks with up to twenty million vertices, measuring preprocessing, space, and query efficiency, and derives scenario-specific selection guidance from the results.

  • Problem

    Prior evaluations did not systematically compare the two method categories and omitted large networks, shortest-path queries, or correct TNR results.

  • Method

    The paper experimentally compares SILC, PCPD, CH, and TNR on real road networks with up to twenty million vertices across preprocessing time, space overhead, and shortest-path and distance-query efficiency.

  • Results

    CH offers the best space efficiency while remaining the second most efficient for both query types; TNR improves distance-query performance over CH at substantial preprocessing and space cost.

  • Takeaways & Limitations

    CH is preferable when both space and time efficiency matter, while combining TNR with CH can provide significant distance-query speedups when extra resources are acceptable.

  • Takeaways & Limitations

    CH performance depends on vertex ordering, and an inferior ordering can cause O(n^2) shortcuts and O(n^2logn) query time.

Abstract

from arXiv · show

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.

1. INTRODUCTION

Shortest-path methods for road networks fall into spatial-coherence-based and vertex-importance-based categories, but prior evaluations did not compare them systematically or cover all relevant settings. The paper motivates a broader evaluation addressing scale, query type, and correctness concerns.

  • Motivation: Dijkstra’s algorithm can become inefficient because it visits every vertex closer to the source than the destination.This inefficiency is especially problematic when the source and destination are far apart in a large road network.
  • Approach categories: Road-network shortest-path algorithms are commonly grouped into spatial-coherence-based methods and vertex-importance-based methods.Spatial-coherence methods exploit geographic regularities, whereas vertex-importance methods prioritize selected vertices and precompute paths among them.
  • Evaluation gap: Prior work had not systematically compared the two method categories under a shared experimental framework.The paper attributes this gap to their development along independent research lines.
  • Evaluation gap: Previous evaluations were limited by small spatial-coherence datasets, emphasis on distance rather than shortest-path queries, and faulty TNR preprocessing.These issues left scalability, shortest-path efficiency, and previously reported TNR results needing reassessment.
  • Evaluation goal: The paper therefore calls for a comprehensive evaluation of existing road-network shortest-path techniques.The stated evaluation scope includes larger networks and the unresolved experimental issues identified above.

2. PROBLEM DEFINITION

The paper models a road network as a weighted, degree-bounded connected graph and distinguishes shortest-path queries from distance queries. The former returns the minimizing edge sequence, while the latter returns only its total length.

  • Road-network model: A road network is modeled as a degree-bounded connected graph with weighted edges and n vertices.The paper treats edge weights as edge lengths and considers undirected graphs for exposition.
  • Query types: A shortest-path query returns an edge sequence connecting s to t with minimum total weight.The returned sequence comprises edges whose summed weights are minimized.
  • Query types: A distance query returns only the minimum total weight between s and t, rather than the edge sequence.This query type is useful when the distance between locations matters more than the route itself.

3. ALGORITHMS

The evaluated algorithms accelerate road-network queries through vertex importance, spatial coherence, or grid-based access nodes, with different preprocessing and query mechanisms. The section also highlights implementation and parameter choices that constrain efficiency.

  • The experiments evaluate bidirectional Dijkstra, CH, TNR, SILC, and PCPD as baseline, vertex-importance-based, and spatial-coherence-based approaches.
  • Contraction Hierarchies: Contraction Hierarchies orders vertices by importance, adds shortcuts during contraction, and restricts bidirectional search to upward-ranked edges.Shortcut tags are later expanded to recover the original shortest path.
  • Contraction Hierarchies: CH efficiency depends on vertex ordering: an inferior order can create O(n^2) shortcuts and O(n^2logn) query time.Existing work proposes heuristics for deriving better orderings from graph structure.
  • Transit Node Routing: Transit Node Routing overlays a grid, assigns access nodes to cells, and precomputes distances from vertices to access nodes and between access nodes.Its distance formula combines source-to-access, access-to-access, and access-to-destination distances when cells are sufficiently separated.
  • Transit Node Routing: TNR cannot use its precomputed distances when the destination cell lies inside the source cell’s outer shell, requiring another method such as CH or bidirectional Dijkstra.
  • Path-Coherent Pairs Decomposition: PCPD recursively decomposes a source–destination path through path-coherent pairs, computing a shortest path with O(k) lookups for a path containing k vertices.Each pair identifies a vertex or edge lying on shortest paths between two square regions.

4. EXPERIMENTS

The experiments compare five techniques across space, preprocessing time, and shortest-path and distance-query efficiency on real road networks. Results expose trade-offs among CH, TNR, SILC, and PCPD across network size and query distance.

  • The evaluation measures five techniques using space overhead, preprocessing time, and both shortest path and distance-query efficiency.The study includes bidirectional Dijkstra, CH, TNR, SILC, and PCPD.
  • Space Overhead and Preprocessing Time: CH has the smallest space overhead, while SILC and PCPD use orders of magnitude more space and exceed 24 GB on networks larger than one million vertices.SILC and PCPD each exceed 4 GB on the 0.4-million-vertex CO dataset.
  • Space Overhead and Preprocessing Time: CH also has the lowest preprocessing cost, requiring 30 minutes for the US dataset with more than 20 million vertices.TNR is consistently slower, while SILC and PCPD require orders of magnitude more preprocessing time.
  • SILC vs. PCPD: SILC consistently outperforms PCPD in query efficiency and preprocessing time, despite similar practical space overheads.This practical result contrasts with PCPD’s better asymptotic space complexity.
  • Query Efficiency: SILC is strongest for shortest path queries on smaller datasets, whereas CH and TNR are more efficient for distance queries and CH improves for far-apart endpoints.TNR considerably outperforms CH on distance-query sets Q7–Q10, while CH outperforms SILC when endpoints are far apart for shortest-path queries.
  • Query Efficiency: For shortest path queries, CH incurs extra overhead because shortcut-based paths must be expanded into paths containing only original edges.Its shortest-path query time is therefore higher than its distance-query time.
  • Summary of Experimental Results: Overall, SILC and PCPD are impractical for million-vertex road networks, while CH provides low preprocessing and space costs with strong performance across both query types.TNR improves distance-query performance over CH but requires considerable preprocessing and space overhead.

5. CONCLUSIONS

The paper compares SILC, PCPD, CH, and TNR on shortest path and distance queries using real road networks with up to twenty million vertices. It reports trade-offs across preprocessing, space, and query efficiency that guide method selection.

  • The evaluation compares SILC, PCPD, CH, and TNR on shortest path and distance queries across real datasets with up to twenty million vertices.
  • CH is the most space-economic technique and the second most efficient for both query types, making it preferable when space and time efficiency both matter.
  • TNR can combine with CH to speed distance queries, especially for far-apart vertices, but has considerable space overhead and is less efficient for shortest path queries.
  • SILC has significant preprocessing time and space consumption but superior shortest path query efficiency.

A. ADDITIONAL RELATED WORK

The paper situates its evaluated methods among alternative shortest path techniques, including landmarks, reach values, grid-based edge labels, hierarchies, and partition boundaries. It also explains why several combinations and variants are outside the study’s scope.

  • ALT selects landmarks and precomputes distances from every vertex to each landmark to accelerate shortest path processing.
  • RE assigns each vertex a reach-based bound that can exclude vertices from shortest paths when the bound is smaller than both endpoint distances.
  • Arc Flags labels edges by grid cells whose shortest paths use them, enabling revised Dijkstra searches to avoid irrelevant edges.
  • Highway Hierarchies organize vertices by relative importance and add same-level shortcuts, while HiTi precomputes distances between partition-boundary vertices.
  • The study excludes combinations such as Arc Flags with CH and hybrid Highway Hierarchies–TNR because they incur significantly higher preprocessing overhead or space consumption.
  • Other work includes theoretical studies and variants extending PCPD, SILC, and CH to approximate distance or nearest-neighbor queries.

B. DEFECTS OF TNR

The paper identifies a defect in Bast et al.’s access-node computation for TNR and replaces it with a CH-assisted method. The defect can produce incomplete access-node sets and incorrect query results.

  • DEFECTS OF TNR: TNR access-node preprocessing derives shortest paths from each cell vertex to vertices on the boundary of the outer shell before selecting access nodes.
  • DEFECTS OF TNR: Bast et al.’s approach uses shortest-path tests involving inner-shell vertices, cell vertices, and outer-shell vertices to identify access nodes.
  • DEFECTS OF TNR: Bast et al.’s access-node set can be incomplete because an access node need not lie on a shortest path from a cell vertex to an outer-shell vertex.
  • DEFECTS OF TNR: An incomplete access-node set can leave shortest paths uncovered and lead to incorrect shortest path and distance query results.
  • DEFECTS OF TNR: The remedy computes shortest paths from each cell vertex to the outer-shell boundary using contraction hierarchies rather than directly applying Dijkstra’s algorithm.
  • DEFECTS OF TNR: The experiments find the preprocessing overhead of constructing contraction hierarchies negligible compared with the reduction in access-node computation cost.

C. SPACE COMPLEXITY OF PCPD

PCPD’s space-complexity guarantee relies on δ-redundancy, but the paper notes that real road networks may not satisfy this assumption and that δ can be close to 1.

  • PCPD’s space-complexity analysis assumes every shortest path is δ-redundant, meaning every core-disjoint alternative path is at least δ times as long.
  • Under the stated assumption, the derived space bound is linear in n when δ is treated as a constant.
  • Real road networks may not always be δ-redundant, limiting the direct applicability of PCPD’s space-complexity guarantee.
  • Even when δ-redundancy holds, δ close to 1 produces an enormous constant factor in PCPD’s space complexity.
  • The paper evaluates the assumption by measuring the shortest core-disjoint path length relative to the shortest path across datasets and query pairs.

D. IMPLEMENTATIONS

The implementations construct TNR, SILC, and PCPD using distinct data structures and preprocessing procedures tailored to their underlying approaches.

  • TNR’s implementation uses the graph data structure from the inventors’ CH source code, including two arrays linking vertices to adjacent-edge blocks.Each edge is stored repeatedly in the structures for its incident vertices.
  • TNR stores grid-cell access nodes and associated vertex-to-node and node-to-node distances in three hash tables.The tables map cells to access-node sets, vertices to access-node distances, and access-node pairs to distances.
  • SILC derives vertex partitions with Dijkstra’s algorithm and recursively subdivides grid cells to represent those partitions concisely.A cell is divided into four quadrants when it contains vertices from different equivalence classes.
  • PCPD constructs square region pairs and identifies path-coherent pairs when all shortest paths share a common vertex or edge.The shared vertex or edge is recorded as ψ.

E.1 Alternative Implementations of TNR

Experiments compare TNR grid configurations and fallback query techniques, finding that the 128 × 128 grid combined with CH provides the preferred overall setting. The 256 × 256 grid is excluded because of excessive space without additional query coverage.

  • TNR’s hybrid grid consumes more space than D128 but less than D256 because it stores only selected distances from the two grids.D128 stores a strict subset of the hybrid grid’s distance information, while D256 stores pairwise distances among all access nodes.
  • The hybrid grid has the largest preprocessing overhead because it processes access nodes from both D128 and D256.D256 also costs more to preprocess than D128 because it derives more access nodes.
  • D256 exceeds 24 GB on the W-US and C-US datasets and does not answer more queries than the hybrid grid without an alternative technique.The paper therefore omits D256 from subsequent experiments.
  • TNR performs significantly better with CH than with bidirectional Dijkstra’s algorithm for distance queries under both D128 and the hybrid grid.The hybrid grid is slightly faster on query sets Q5 and Q6 when bidirectional Dijkstra’s algorithm handles fallback queries.
  • TNR performs most efficiently with a 128 × 128 grid and CH as the alternative query-answering technique.The paper adopts this configuration in its experiments.

E.2 Alternative Query Sets

The alternative query sets are generated from road-network distances rather than L∞ distances, and the resulting efficiency patterns are qualitatively consistent with earlier experiments for both query types.

  • The alternative query sets R1, . . . , R10 are generated using road-network distances among vertices rather than L∞ distances.The construction begins by estimating the maximum distance between vertices in each dataset.
  • Figures 16 and 17 report running times for distance and shortest path queries, respectively, across the ten alternative query sets.Figure 16 covers distance queries, while Figure 17 covers shortest path queries.
  • The alternative-query results are qualitatively similar to those in Figures 8 and 10, confirming the earlier findings about the relative superiority of the techniques.Figures 14 and 15 separately present efficiency against query sets for distance and shortest path queries.
  • The plotted comparisons distinguish Hybrid and 128×128 grids combined with either CH or bidirectional Dijkstra’s algorithm.These configurations correspond to the four alternatives shown for the TNR experiments.
Loading 1201.6564v1…