Graph Indexing of Road Networks for Shortest Path Queries With Label Restrictions

Date Added: Jan 2011
Format: PDF

The current widespread use of location-based services and GPS technologies has revived interest in very fast and scalable shortest path queries. The authors introduce a new shortest path query type in which dynamic constraints may be placed on the allowable set of edges that can appear on a valid shortest path (e.g., dynamically restricting the type of roads or modes of travel which may be considered in a multimodal transportation network). They formalize this problem as a specific variant of formal language constrained shortest path problems, which they call the Kleene language constrained shortest paths problem. To efficiently support this type of dynamically constrained shortest path query for large-scale datasets, they extend the hierarchical graph indexing technique known as contraction hierarchies.