Computing the shortest path between two locations in a road network is an important problem that has found numerous applications. The classic solution for the problem is Dijkstra's algorithm [1]. Although simple and elegant, the algorithm has proven to be inefficient for very large road networks. To address this deficiency of Dijkstra's algorithm, a plethora of techniques that introduce some preprocessing to reduce the query time have been proposed. In this paper, we propose Partition-based Shortcuts (PbS), a technique based on graph-partitioning which offers fast query processing and supports efficient edge weight updates. We present a shortcut computation scheme, which exploits the traits of a graph partition. We also present a modified version of the bidirectional search [2], which uses the precomputed shortcuts to efficiently answer shortest path queries. Moreover, we introduce the Corridor Matrix (CM), a partition-based structure which is exploited to reduce the search space during the processing of shortest path queries when the source and the target point are close. Finally, we evaluate the performance of our modified algorithm in terms of preprocessing cost and query runtime for various graph partitioning configurations.
Computing the shortest path between two locations in a road network is a fundamental problem and has found numerous applications. The problem can be formally defined as follows. Let G(V; E) be a directed weighted graph with vertices V and edges E. For each edge e 2 E, a weight l(e) is assigned, which usually represents the length of e or the time required to cross e. A path p between two vertices s; t 2 V is a sequence of connected edges, p(s; t) = h(s; v1); (v1; v2); : : : ; (vk; vt)i where (vk; vk+1) 2 E, that connects s and t. The shortest path between two vertices s and t is the path p(s; t) that has the shortest distance among all paths that connect s and t.
The classic solution for the shortest path problem is Dijkstra’s
algorithm [
Although most of the proposed techniques offer fast query
processing, the preprocessing is always performed under the
assumption that the weights of a road network remain unchanged over
time. Moreover, the preprocessing is metric-specific, thus for
different metrics the preprocessing needs to be performed for each
metric. The recently proposed Customizable Route Planning [
The contributions of this paper can be summarized as follows: We present Partitioned-based Shortcuts (PbS), a preprocessing method which is based on Customizable Route Planning (CRP), but computes more shortcuts in order to reduce the query processing time.
We propose the Corridor Matrix (CM), a pruning technique which can be used for shortest path queries when the source and the target are very close and the precomputed shortcuts cannot be exploited.
We run experiments for several different partition configurations and we evaluate our approach in terms of both preprocessing and query processing cost.
The rest of the paper is organized as follows. In Section 2, we discuss related work. In Section 3, we describe in detail the preprocessing phase of our method. In Section 5, we present a modified version of the bidirectional search algorithm. In Section 6, we show preliminary results of an empirical evaluation. Section 7 concludes the paper and points to future research directions.
The preprocessing based techniques that have been proposed
in order to reduce the time required for processing shortest path
queries can be classified into different categories [
Path Coherent techniques take advantage of the fact that shortest
paths in road networks are often spatially coherent. To illustrate the
concept of spatial coherence, let us consider four locations s, s0, t
and t0 in a road network. If s is close to s0 and t is close to t0, the
shortest path from s to t is likely to share vertices with the shortest
path from s0 to t0. Spatial coherence methods precompute all
shortest paths and use then some data structures to index the paths and
answer queries efficiently. For example, Spatially Induced Linkage
Cognizance (SILC) [
Bounded-hop techniques aim to reduce a shortest path query to
a number of look-ups. Transit Node Routing (TNR) [
Finally, Hierarchical techniques aim to impose a total order on
the nodes as they deem nodes that are crossed by many shortest
paths as more important. Highway Hierarchies (HH) [
The recent Customizable Route Planning (CRP) [
The Partition-based Shortcuts (PbS) method we propose
exploits graph partitioning to produce shortcuts in a preprocessing
phase, which during the query phase are used to efficiently
compute shortest path queries. The idea is similar to the concept of
transit nodes [
The first step in the pre-processing phase is the graph partitioning. Let G(V; E) be a graph with vertices V and edges E. A partition of G is a set P (G) = fC1; : : : ; Ckg of connected subgraphs Ci of G, also referred to as components of G. For the set P (G), all components must be disjoint, i.e., C1 \ : : : \ Ck = ;. Moreover, let V1; : : : ; VjP (G)j be the sets of vertices of each component. The vertex sets of all components must cover the vertex set of the graph, i.e., V1 [ : : : [ VjP (G)j = V . We assign a tag to each node of the original graph, which indicates the component the node is located in. The set of connecting edges, EC E, is the set of all edges in the graph for which the source and target nodes belong to different components, i.e., (n; n0) 2 E such that n 2 Ci, n0 2 Cj and Ci 6= Cj . Finally, we define the border nodes of a component C. A node n 2 C is a border node of C if there exists a connecting edge e = (n; n0) or e = (n0; n), i.e., n0 is not in C. If e = (n; n0), n is called outgoing border node of C, whereas if e = (n0; n), n is called incoming border node of C. The set of all border nodes of a graph is referred to as B. Figure 1 illustrates a graph partitioned into five components. The filled nodes are the border nodes. Note that for ease of exposition we use only undirected graphs in the examples.
We characterize a graph partition as good if it minimizes the
number of connecting edges between the components. However,
graph partitioning is an N P -hard problem, thus an optimal
solution is out of the question [
The second step of the preprocessing phase is the computation of the in-component shortcuts. For each node n in the original graph, we compute the shortest path from the node to every outgoing border node of the component in which n is located. Then we create outgoing shortcuts which abstract the shortest path from n to each outgoing border node. The incoming shortcuts are computed in a similar fashion. Thus, the total number of in-component shortcuts, S, is
k S = X Ni i=1
(jBiinc j + jBiout j); where Ni is the number of nodes in component Ci and Biinc , Biout are the incoming and outgoing border nodes of Ci, respectivelly. Figure 2 shows the in-component shortcuts for a node located in component C2.
For each border node in a component, b 2 C, we execute Dijkstra’s algorithm with b as source and all other nodes (including border nodes) in C as targets. Depending on the type of the source node, the expansion strategy is different. When an incoming border node is the source, forward edges are expanded; vice versa, when an outgoing border node is the source, incoming edges are expanded. This strategy ensures that the maximum number of node expansions is at most twice the number of border nodes of G. 3.3
The third step of the preprocessing phase of our approach is the construction of the shortcut graph. Given a graph G, the shortcut graph of G is a graph Gsc(B; Esc), where B is the set of border nodes of G and Esc = EC [ SG is the union of the connecting edges, EC , of G and the shortcuts, SG, from every incoming border node to every outgoing border node of the same component. Thus, the number of vertices and edges in the shortcut graph is, respectively,
k jBj = X jEscj =
In Section 3 we presented how PbS creates shortcuts in order to
answer queries when the source and the target points are in
different components. However, when the source and the target points
of a query are located in the same component, the shortest path
may lie entirely inside the component. Therefore, the search
algorithm will never reach the border nodes and the shortcuts will not
be expanded. In such a case, the common approach is to use
bidirectional search to return the shortest path. However, if the
components of the partitioned graph are large, the query processing can be
quite slow. In order to improve the processing time of such queries,
we partition each component again into sub-components, and for
each component, we compute its Corridor Matrix (CM). In
general, given a partition of a graph G in k components, the Corridor
Matrix (CM) of G is a k k matrix, where each cell C(i; j) of
CM contains a list of components that are crossed by some
shortest path from a node s 2 Ci to a node t 2 Cj . We call such a
list the corridor from Ci to Cj . The concept of the CM is similar
to Arc-Flags [
C1 C2 C3 C4 C5 C1 ; C2 ; C3 ; C4 ; C5 ;
fC2; C3g
To optimize the look-up time in CM, we implemented each
component list using a bitmap of length k. Therefore, the space
complexity of the CM in the worst case is O(k3). The actual space
occupied by the CM is smaller, since we do not allocate space for
bitmaps when the component list is empty. For the computation of
the Corridor Matrix, we generate the Shortcut Graph in the same
way as described in Section 3.3. To compute the distances between
all pairs of vertices, we use the Floyd-Warshall algorithm [
In order to process a shortest path query from a source point s to a target point t, we first determine the components of the graph the nodes s 2 Cs and t 2 Ct are located in. If Cs = Ct, we execute a modified bidirectional search from s to t. Note that the shortcuts are not used for processing queries for which the source and target are located in the same component C. Instead, we retrieve the appropriate corridor from the CM of C, which contains a list of sub-components. Then, we apply bidirectional search and prune all nodes that belong to sub-components which are not in the retrieved corridor.
In the case that the points s and t are not located in the same component, we exploit the pre-computed shortcuts. First, we retrieve the lengths of the in-component outgoing shortcuts from s to all the outgoing borders of Cs and the length of the in-component incoming shortcuts from all the incoming borders of Ct to t. Then we apply a many-to-many bidirectional search in the overlay graph from all the outgoing borders of Cs to all the incoming borders of Ct. We use the length of the in-component shortcuts (retrieved in the first step) as initial weights for the source and target nodes of the bidirectional search in the Shortcut Graph. The list of edges consisting the path is a set of connecting edges of the original graph and in-component shortcuts. For each shortcut we retrieve the precomputed set of the original edges. The cost to retrieve the original path is linear to the size of the path. After the retrieval we replace the shortcuts with the list of edges in the original graph and we return the new edge list, which is the shortest path from s to t in the original graph.
In this section, we compare our PbS method with CRP, the
method our own approach is based on, and CH, a lightweight yet
very efficient state-of-the-art approach for shortest path queries in
road networks [
For the experiments we follow the same evaluation setting as
in [
1 0:5
0
CAL FLA BAY
NY ROME
California/Nevada
Florida SF Bay Area New York City Center of Rome contain 1000 queries each. We make sure that the distance of every query in set Qi is smaller than the distance of every query in set Qi+1. We also evaluate the CM separately by comparing our CM implementation against Arc Flags and the original bidirectional search for a set of 1000 random queries in the ROME dataset. We use a small dataset in order to simulate in-component query processing. 6.1
Figures 5 and 6 show a series of measurements for the preprocessing cost of our approach in comparison to CRP and CH over the four largest datasets. Figure 5 shows how many shortcuts are created by each approach. The extra shortcuts can be translated into the space overhead required in order to speed-up shortest path queries. CH uses shortcuts which represent only two edges, while the shortcuts in PbS and CRP are composed of much longer sequences. The difference between the shortcuts produced by CRP and CH is much less. In short, PbS produces about two orders of magnitude more shortcuts than CRP and CH. Moreover, we can observe that the number of shortcuts produced by PbS is getting lower as the number of components is increasing.
CH
CRP
PbS 3 107 shortcuts 3 107 shortcuts 128 256 384 512 128 256 384 512 (a) NY 1 108 shortcuts (b) BAY 2 108 shortcuts 2 1 0 0:75 0:5 0:25 0 256 512
The same tendency as observed for the number of shortcuts can be observed for the preprocessing time. In Figure 6, we can see that PbS requires much more time than CRP and CH in order to create shortcuts. However, we should also notice that the update cost for CRP and PbS is only a small portion of the preprocessing cost. When an edge weight changes, we need to update only the shortcuts that contains that particular edge. In contrast, for CH the the update cost is the same as the preprocesing cost since a change in a single weight can influence the entire hierarchy.
Figure 7 shows a series of measurements of the performance of CRP and PbS. We evaluate both techniques for different partitions and various numbers of components. An important observation is the tendency of the performance for CRP and PbS. The performance of CRP gets worse for partitions with many components while the opposite happens for PbS. The reason is that for partitions with few components, PbS manages to process many queries with two look-ups (the case where the source and the target are in adjacent components).
In Figure 8 we compare CH with CRP (we choose the best result) and two configurations of PbS: PbS-BT, which is the configuration that leads to the best performance, and PbS-AVG, which is the average performance of PbS among all configurations. We can see that PbS outperforms CRP in all datasets from Q1 to Q5. However, CH is faster in terms of query processing than our PbS approach. CH is more suitable for static networks as the constructed hierarchy of shortcuts enables the shortest path algorithm to expand much fewer nodes. 6.3
In Figure 9, we compare the performance of our bidirectional algorithm using the proposed CM, the original bidirectional search and the bidirectional algorithm using Arc Flags. We observe that the bidirectional search is the slowest since no pruning is applied. Between Arc Flags and CM, the Arc Flags provide slightly better pruning thus fewer expanded nodes by the bidirectional search. On the other hand, the preprocessing time required to compute the Arc Flags is significantly higher than the time required to compute the CM. 104 expanded nodes 104 expanded nodes 1
In this paper we presented PbS, an approach which uses graph partitioning in order to compute shortcuts and speed-up shortest path queries in road networks. Our aim was a solution which supports efficient and incremental updates of edge weights, yet is efficient enough in many real-world applications. In the evaluation, we showed that our PbS approach outperforms CRP. PbS supports edge weight updates as any change in the weight of an edge can influence only shortcuts in a single component. On the other hand, CH is faster than our PbS approach. However, CH cannot handle well edge weight updates as almost the entire hierarchy of shortcuts has to be recomputed every time a single weight changes. For queries where the source and the target are in the same component, we introduced the CM. The efficiency of the CM in query processing approaches the efficiency of Arc Flags, while consuming much less space.
In future work, we plan to extend our approach to support multimodal transportation networks, where the computation has to consider a time schedule, and dynamic and traffic aware networks, where the weights of the edges change over time. We will also improve the preprocessing phase of our approach both in terms of time overhead, by using parallel processing, and space overhead, by using compression techniques or storing some of the precomputed information on the disk. 8. 2;000 0 Q1 104 1:5 12 9 6 3 Q2
Q3
Q4
Q5 (a) NY
Q2
Q3 (b) BAY
Q4
Q5