=Paper=
{{Paper
|id=Vol-1313/paper_13
|storemode=property
|title=Exploring Graph Partitioning for Shortest Path Queries on Road Networks
|pdfUrl=https://ceur-ws.org/Vol-1313/paper_13.pdf
|volume=Vol-1313
|dblpUrl=https://dblp.org/rec/conf/gvd/ChondrogiannisG14
}}
==Exploring Graph Partitioning for Shortest Path Queries on Road Networks==
https://ceur-ws.org/Vol-1313/paper_13.pdf
Exploring Graph Partitioning for
Shortest Path Queries on Road Networks
Theodoros Chondrogiannis Johann Gamper
Free University of Bozen-Bolzano Free University of Bozen-Bolzano
tchond@inf.unibz.it gamper@inf.unibz.it
ABSTRACT The classic solution for the shortest path problem is Dijkstra’s al-
Computing the shortest path between two locations in a road net- gorithm [1]. Given a source s and a destination t in a road network
work is an important problem that has found numerous applica- G, Dijkstra’s algorithm traverses the vertices in G in ascending or-
tions. The classic solution for the problem is Dijkstra’s algo- der of their distances to s. However, Dijkstra’s algorithm comes
rithm [1]. Although simple and elegant, the algorithm has proven with a major shortcoming. When the distance between the source
to be inefficient for very large road networks. To address this defi- and the target vertex is high, the algorithm has to expand a very
ciency of Dijkstra’s algorithm, a plethora of techniques that intro- large subset of the vertices in the graph. To address this short-
duce some preprocessing to reduce the query time have been pro- coming, several techniques have been proposed over the last few
posed. In this paper, we propose Partition-based Shortcuts (PbS), a decades [3]. Such techniques require a high start-up cost, but in
technique based on graph-partitioning which offers fast query pro- terms of query processing they outperform Dijkstra’s algorithm by
cessing and supports efficient edge weight updates. We present a orders of magnitude.
shortcut computation scheme, which exploits the traits of a graph Although most of the proposed techniques offer fast query pro-
partition. We also present a modified version of the bidirectional cessing, the preprocessing is always performed under the assump-
search [2], which uses the precomputed shortcuts to efficiently an- tion that the weights of a road network remain unchanged over
swer shortest path queries. Moreover, we introduce the Corridor time. Moreover, the preprocessing is metric-specific, thus for dif-
Matrix (CM), a partition-based structure which is exploited to re- ferent metrics the preprocessing needs to be performed for each
duce the search space during the processing of shortest path queries metric. The recently proposed Customizable Route Planning [4]
when the source and the target point are close. Finally, we evaluate applies preprocessing for various metrics, i.e., distance, time, turn
the performance of our modified algorithm in terms of preprocess- cost and fuel consumption. Such an approach allows a fast com-
ing cost and query runtime for various graph partitioning configu- putation of shortest path queries using any metric desired by the
rations. user, at the cost of some extra space. Moreover, the update cost for
the weights is low since the structure is designed such that only a
small part of the preprocessed information has to be recomputed.
Keywords In this paper, our aim is to develop an approach which offers even
Shortest path, road networks, graph partitioning faster query processing, while keeping the update cost of the pre-
processed information low. This is particularly important in dy-
namic networks, where edge weights might frequently change, e.g.,
1. INTRODUCTION due to traffic jams.
Computing the shortest path between two locations in a road The contributions of this paper can be summarized as follows:
network is a fundamental problem and has found numerous ap-
• We present Partitioned-based Shortcuts (PbS), a preprocess-
plications. The problem can be formally defined as follows. Let
ing method which is based on Customizable Route Planning
G(V, E) be a directed weighted graph with vertices V and edges
(CRP), but computes more shortcuts in order to reduce the
E. For each edge e ∈ E, a weight l(e) is assigned, which usually
query processing time.
represents the length of e or the time required to cross e. A path p
between two vertices s, t ∈ V is a sequence of connected edges, • We propose the Corridor Matrix (CM), a pruning technique
p(s, t) = h(s, v1 ), (v1 , v2 ), . . . , (vk , vt )i where (vk , vk+1 ) ∈ E, which can be used for shortest path queries when the source
that connects s and t. The shortest path between two vertices s and and the target are very close and the precomputed shortcuts
t is the path p(s, t) that has the shortest distance among all paths cannot be exploited.
that connect s and t.
• We run experiments for several different partition configura-
tions and we evaluate our approach in terms of both prepro-
cessing 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 prepro-
In: G. Specht, H. Gamper, F. Klan (eds.): Proceedings of the 26 GI- cessing phase of our method. In Section 5, we present a modified
Workshop on Foundations of Databases (Grundlagen von Datenbanken), version of the bidirectional search algorithm. In Section 6, we show
21.10.2014 - 24.10.2014, Bozen, Italy, published at http://ceur-ws.org.
Copyright c by the paper’s authors. Copying permitted only for private preliminary results of an empirical evaluation. Section 7 concludes
and academic purposes.. the paper and points to future research directions.
2. RELATED WORK in each component and then CRP applies a modified bidirectional
The preprocessing based techniques that have been proposed search algorithm which expands only the shortcuts and the edges in
in order to reduce the time required for processing shortest path the source or the target component. The main difference between
queries can be classified into different categories [3]. Goal-directed our approach and CRP is that, instead of computing only shortcuts
techniques use either heuristics or precomputed information in or- between border nodes in each component, we compute shortcuts
der to limit the search space by excluding vertices that are not in from every node of a component to the border nodes of the same
the direction of the target. For example, A∗ [5] search uses the component. The extra shortcuts enable the bidirectional algorithm
Euclidean distance as a lower bound. ALT [6] uses precomputed to start directly from the border nodes, while CRP has to scan the
shortest path distances to a carefully selected set of landmarks and original edges of the source and the target component.
produces the lower bound using the triangle inequality. Some goal-
directed techniques exploit graph partitioning in order to prune the 3. PBS PREPROCESSING
search space and speed-up queries. Precomputed Cluster Distances The Partition-based Shortcuts (PbS) method we propose ex-
(PCD) [7] partitions the graph into k components, computes the ploits graph partitioning to produce shortcuts in a preprocessing
distance between all pairs of components and uses the distances be- phase, which during the query phase are used to efficiently com-
tween components to compute lower bounds. Arc Flags [8] main- pute shortest path queries. The idea is similar to the concept of
tains a vector of k bits for each edge, where the i-th bit is set if the transit nodes [12]. Every shortest path between two nodes lo-
arc lies on a shortest path to some vertex of component i. Other- cated in different partitions (also termed components) can be ex-
wise, all edges of component i are pruned by the search algorithm. pressed as a combination of three smaller shortest paths. Con-
Path Coherent techniques take advantage of the fact that shortest sider the graph in Figure 1 and a query q(s, t), where s ∈ C1
paths in road networks are often spatially coherent. To illustrate the and t ∈ C5 . The shortest path from s to t can be expressed as
concept of spatial coherence, let us consider four locations s, s0 , t p(s, bs ) + p(bs , bt ) + p(bt , t), where bs ∈ {b1 , b2 } and bt ∈
and t0 in a road network. If s is close to s0 and t is close to t0 , the {b3 , b4 , b5 }. Before PbS is able to process shortest path queries,
shortest path from s to t is likely to share vertices with the shortest a preprocessing phase is required, which consists of three steps:
path from s0 to t0 . Spatial coherence methods precompute all short- graph partitioning, in-component shortcut computation and short-
est paths and use then some data structures to index the paths and cut graph construction.
answer queries efficiently. For example, Spatially Induced Linkage
Cognizance (SILC) [9] use a quad-tree [10] to store the paths. Path- 3.1 Graph Partitioning
Coherent Pairs Decomposition (PCPD) [11] computes unique path
The first step in the pre-processing phase is the graph partition-
coherent pairs and retrieves any shortest path recursively in almost
ing. Let G(V, E) be a graph with vertices V and edges E. A
linear time to the size of the path.
partition of G is a set P (G) = {C1 , . . . , Ck } of connected sub-
Bounded-hop techniques aim to reduce a shortest path query to
graphs Ci of G, also referred to as components of G. For the set
a number of look-ups. Transit Node Routing (TNR) [12] is an in-
P (G), all components must be disjoint, i.e., C1 ∩ . . . ∩ Ck = ∅.
dexing method that imposes a grid on the road network and re-
Moreover, let V1 , . . . , V|P (G)| be the sets of vertices of each com-
computes the shortest paths from within each grid cell C to a set
ponent. The vertex sets of all components must cover the vertex set
of vertices that are deemed important for C (so-called access nodes
of the graph, i.e., V1 ∪ . . . ∪ V|P (G)| = V . We assign a tag to each
of C). More approaches are based on the theory of 2-hop label-
node of the original graph, which indicates the component the node
ing [13]. During preprocessing, a label L(u) is computed for each
is located in. The set of connecting edges, EC ⊆ E, is the set of all
vertex u of the graph such that for any pair u, v of vertices, the
edges in the graph for which the source and target nodes belong to
distance dist(u, v) can be determined by only looking at the labels
different components, i.e., (n, n0 ) ∈ E such that n ∈ Ci , n0 ∈ Cj
L(u) and L(v). A natural special case of this approach is Hub La-
and Ci 6= Cj . Finally, we define the border nodes of a component
beling (HL) [14], in which the label L(u) associated with vertex
C. A node n ∈ C is a border node of C if there exists a connecting
u consists of a set of vertices (the hubs of u), together with their
edge e = (n, n0 ) or e = (n0 , n), i.e., n0 is not in C. If e = (n, n0 ),
distances from u.
n is called outgoing border node of C, whereas if e = (n0 , n), n
Finally, Hierarchical techniques aim to impose a total order on
is called incoming border node of C. The set of all border nodes
the nodes as they deem nodes that are crossed by many shortest
of a graph is referred to as B. Figure 1 illustrates a graph parti-
paths as more important. Highway Hierarchies (HH) [15] and its
tioned into five components. The filled nodes are the border nodes.
direct descendant Contraction Hierarchies (CH) organize the nodes
Note that for ease of exposition we use only undirected graphs in
in the road network into a hierarchy based on their relative im-
the examples.
portance, and create shortcuts among vertices at the same level
of the hierarchy. Arterial Hierarchies (AH) [16] are inspired by
CH, but produce shortcuts by imposing a grid on the graph. AH
outperform CH in terms of both asymptotic and practical perfor-
mance [17]. Some hierarchical approaches exploit graph partition
to create shortcuts. HEPV [18] and HiTi [19] are techniques that
pre-computes the distance between any two boundary vertices and
create a new overlay graph. By partitioning the overlay graph and
repeating the process several times, a hierarchy of partitions is cre-
ated, which is used to process shortest path queries.
The recent Customizable Route Planning (CRP) [4] is the clos-
est work to our own. CRP is able to handle various arbitrary met-
rics and can also handle dynamic edge weight updates. CRP uses
PUNCH [20], a graph partitioning algorithm tailored to road net-
works. CRP pre-computes distances between boundary vertices Figure 1: Partitioned graph into five components.
We characterize a graph partition as good if it minimizes the Thus, the number of vertices and edges in the shortcut graph is,
number of connecting edges between the components. However, respectively,
graph partitioning is an N P -hard problem, thus an optimal solu- k
tion is out of the question [21]. A popular approach is multilevel X
|B| = |Biinc ∪ Biout | and
graph partitioning (MGP), which can be found in many software
i=1
libraries, such as METIS [22]. Algorithms such as PUNCH [20]
k
and Spatial Partition Clustering (SPC) [23] take advantage of road X
|Esc | = (|Biinc | × |Biout |) + EC .
network characteristics in order to provide a more efficient graph
i=1
partitioning. We use METIS for graph partitioning since it is the
most efficient approach out of all available ones [24]. METIS re- Figure 3 shows the shortcut graph of our running example. Notice
quires only the number of components as an argument in order to that only border nodes are vertices of the shortcut graph. The set of
perform the partitioning. The number of components influences edges consists of connecting edges and the in-component shortcuts
both the number of the in-component shortcuts and the size of the between the border nodes of the same component. Note that there
shortcut graph. is no need for extra computations in order to populate the shortcut
graph.
3.2 In-component Shortcuts
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 bor-
der 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
X
S= Ni × (|Biinc | + |Biout |),
i=1
where Ni is the number of nodes in component Ci and Biinc ,
Biout are the incoming and outgoing border nodes of Ci , respectiv- Figure 3: Shortcut Graph illustrated over the original.
elly. Figure 2 shows the in-component shortcuts for a node located
in component C2 .
4. CORRIDOR MATRIX
In Section 3 we presented how PbS creates shortcuts in order to
answer queries when the source and the target points are in differ-
ent 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 algo-
rithm will never reach the border nodes and the shortcuts will not
be expanded. In such a case, the common approach is to use bidi-
rectional search to return the shortest path. However, if the compo-
nents 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 gen-
Figure 2: In-component shortcuts for a given node. eral, 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
For each border node in a component, b ∈ C, we execute Di- CM contains a list of components that are crossed by some short-
jkstra’s algorithm with b as source and all other nodes (including est path from a node s ∈ Ci to a node t ∈ Cj . We call such a
border nodes) in C as targets. Depending on the type of the source list the corridor from Ci to Cj . The concept of the CM is similar
node, the expansion strategy is different. When an incoming bor- to Arc-Flags [8], but the CM requires much less space. The space
der node is the source, forward edges are expanded; vice versa, complexity of the CM is O(k3 ), where k is the number of compo-
when an outgoing border node is the source, incoming edges are nents in the partition, while the space complexity of Arc-Flags is
expanded. This strategy ensures that the maximum number of node |E| × k2 , where |E| is the number of edges in the original graph.
expansions is at most twice the number of border nodes of G.
C1 C2 C3 C4 C5
3.3 Shortcut Graph Construction C1 ∅ {C2 , C3 }
The third step of the preprocessing phase of our approach is the C2 ∅
construction of the shortcut graph. Given a graph G, the shortcut C3 ∅
graph of G is a graph Gsc (B, Esc ), where B is the set of border C4 ∅
nodes of G and Esc = EC ∪ SG is the union of the connecting C5 ∅
edges, EC , of G and the shortcuts, SG , from every incoming bor-
der node to every outgoing border node of the same component. Figure 4: Corridor Matrix example.
To optimize the look-up time in CM, we implemented each com- Name Region # Vertices # Edges
ponent list using a bitmap of length k. Therefore, the space com- CAL California/Nevada 1,890,815 4,657,742
plexity of the CM in the worst case is O(k3 ). The actual space FLA Florida 1,070,376 2,712,798
occupied by the CM is smaller, since we do not allocate space for BAY SF Bay Area 321,270 800,172
bitmaps when the component list is empty. For the computation of NY New York City 264,346 733,846
the Corridor Matrix, we generate the Shortcut Graph in the same ROME Center of Rome 3353 8,859
way as described in Section 3.3. To compute the distances between
all pairs of vertices, we use the Floyd-Warshall algorithm [25], Table 1: Dataset characteristics.
which is specifically designed to compute the all-pair shortest path
distance efficiently. After having computed the distances between
the nodes, instead of retrieving each shortest path, we retrieve only
the components that are crossed by each path, and we update the contain 1000 queries each. We make sure that the distance of ev-
CM accordingly. ery 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 bidi-
5. SHORTEST PATH ALGORITHM rectional search for a set of 1000 random queries in the ROME
In order to process a shortest path query from a source point s dataset. We use a small dataset in order to simulate in-component
to a target point t, we first determine the components of the graph query processing.
the nodes s ∈ Cs and t ∈ Ct are located in. If Cs = Ct , we
execute a modified bidirectional search from s to t. Note that the 6.1 Preprocessing and Space Overhead
shortcuts are not used for processing queries for which the source Figures 5 and 6 show a series of measurements for the prepro-
and target are located in the same component C. Instead, we re- cessing cost of our approach in comparison to CRP and CH over
trieve the appropriate corridor from the CM of C, which contains the four largest datasets. Figure 5 shows how many shortcuts are
a list of sub-components. Then, we apply bidirectional search and created by each approach. The extra shortcuts can be translated
prune all nodes that belong to sub-components which are not in the into the space overhead required in order to speed-up shortest path
retrieved corridor. queries. CH uses shortcuts which represent only two edges, while
In the case that the points s and t are not located in the same the shortcuts in PbS and CRP are composed of much longer se-
component, we exploit the pre-computed shortcuts. First, we re- quences. The difference between the shortcuts produced by CRP
trieve the lengths of the in-component outgoing shortcuts from s to and CH is much less. In short, PbS produces about two orders of
all the outgoing borders of Cs and the length of the in-component magnitude more shortcuts than CRP and CH. Moreover, we can ob-
incoming shortcuts from all the incoming borders of Ct to t. Then serve that the number of shortcuts produced by PbS is getting lower
we apply a many-to-many bidirectional search in the overlay graph as the number of components is increasing.
from all the outgoing borders of Cs to all the incoming borders
of Ct . We use the length of the in-component shortcuts (retrieved CH CRP PbS
in the first step) as initial weights for the source and target nodes
7 shortcuts
of the bidirectional search in the Shortcut Graph. The list of edges ·10 ·107 shortcuts
3 3
consisting the path is a set of connecting edges of the original graph
and in-component shortcuts. For each shortcut we retrieve the pre-
computed set of the original edges. The cost to retrieve the original 2 2
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 re- 1 1
turn the new edge list, which is the shortest path from s to t in the
original graph.
0 0
128 256 384 512 128 256 384 512
6. PRELIMINARY RESULTS (a) NY (b) BAY
In this section, we compare our PbS method with CRP, the ·108 shortcuts ·108 shortcuts
1 2
method our own approach is based on, and CH, a lightweight yet
very efficient state-of-the-art approach for shortest path queries in 0.75 1.5
road networks [17]. CRP can handle arbitrary metrics and edge
weight updates, while CH is a technique with fast pre-processing 0.5 1
and relatively low query processing time. We implemented in Java
the basic version of CRP and PbS. The CH algorithm in the ex- 0.25 0.5
periments is from Graphhopper Route Planner [26]. Due to the
different implementations of the graph models between ours and 0
256 512 768 1,024
0
512 1,024 1,536 2,048
CH, we do not measure the runtime. Instead, for preprocessing we
count the extra shortcuts created by each algorithm, while for query (c) FLA (d) CAL
processing we count the number of expanded nodes.
For the experiments we follow the same evaluation setting as Figure 5: Preprocessing: # of shortcuts vs. # of components.
in [17]. We use 5 publicly available datasets [27], four of of which
are a part of the US road network, and the smallest one represents The same tendency as observed for the number of shortcuts can
the road network of Rome. We present the characteristics of each be observed for the preprocessing time. In Figure 6, we can see
dataset in Table 1. In order to compare our PbS approach and CRP that PbS requires much more time than CRP and CH in order to
with CH, we run our experiments over 5 query sets Q1 –Q5, which create shortcuts. However, we should also notice that the update
cost for CRP and PbS is only a small portion of the preprocessing CRP PbS
cost. When an edge weight changes, we need to update only the ·104 expanded nodes
·104 expanded nodes
shortcuts that contains that particular edge. In contrast, for CH the 1 1
the update cost is the same as the preprocesing cost since a change
0.75 0.75
in a single weight can influence the entire hierarchy.
0.5 0.5
CH CRP PbS
preprocessing time(sec) preprocessing time(sec) 0.25 0.25
300 300
0 0
128 256 384 512 128 256 384 512
200 200
(a) NY (b) BAY
·104 expanded nodes ·104 expanded nodes
2 3
100 100
1.5
2
0 0
128 256 384 512 128 256 384 512
1
(a) NY (b) BAY
1
preprocessing time(sec) preprocessing time(sec) 0.5
1,500 3,000
0 0
256 512 768 1,024 512 1,024 1,536 2,048
1,000 2,000
(c) FLA (d) CAL
500 1,000 Figure 7: Performance of shortest path queries vs. # of components.
0 0
256 512 768 1,024 512 1,024 1,536 2,048 7. CONCLUSION
(c) FLA (d) CAL In this paper we presented PbS, an approach which uses graph
partitioning in order to compute shortcuts and speed-up shortest
Figure 6: Preprocessing: time vs. # of components. path queries in road networks. Our aim was a solution which sup-
ports efficient and incremental updates of edge weights, yet is ef-
ficient enough in many real-world applications. In the evaluation,
6.2 Query Processing we showed that our PbS approach outperforms CRP. PbS supports
Figure 7 shows a series of measurements of the performance of edge weight updates as any change in the weight of an edge can
CRP and PbS. We evaluate both techniques for different partitions influence only shortcuts in a single component. On the other hand,
and various numbers of components. An important observation is CH is faster than our PbS approach. However, CH cannot handle
the tendency of the performance for CRP and PbS. The perfor- well edge weight updates as almost the entire hierarchy of short-
mance of CRP gets worse for partitions with many components cuts has to be recomputed every time a single weight changes. For
while the opposite happens for PbS. The reason is that for parti- queries where the source and the target are in the same component,
tions with few components, PbS manages to process many queries we introduced the CM. The efficiency of the CM in query process-
with two look-ups (the case where the source and the target are in ing approaches the efficiency of Arc Flags, while consuming much
adjacent components). less space.
In Figure 8 we compare CH with CRP (we choose the best result) In future work, we plan to extend our approach to support multi-
and two configurations of PbS: PbS-BT, which is the configuration modal transportation networks, where the computation has to con-
that leads to the best performance, and PbS-AVG, which is the aver- sider a time schedule, and dynamic and traffic aware networks,
age performance of PbS among all configurations. We can see that where the weights of the edges change over time. We will also
PbS outperforms CRP in all datasets from Q1 to Q5 . However, CH improve the preprocessing phase of our approach both in terms of
is faster in terms of query processing than our PbS approach. CH time overhead, by using parallel processing, and space overhead,
is more suitable for static networks as the constructed hierarchy of by using compression techniques or storing some of the precom-
shortcuts enables the shortest path algorithm to expand much fewer puted information on the disk.
nodes.
6.3 In-component Queries 8. REFERENCES
In Figure 9, we compare the performance of our bidirectional [1] E. W. Dijkstra. A note on two problems in connexion with
algorithm using the proposed CM, the original bidirectional search graphs. Numerische Mathematik, 1(1):269–271, December
and the bidirectional algorithm using Arc Flags. We observe that 1959.
the bidirectional search is the slowest since no pruning is applied. [2] I. S. Pohl. Bi-directional and Heuristic Search in Path
Between Arc Flags and CM, the Arc Flags provide slightly better Problems. PhD thesis, Stanford, CA, USA, 1969.
pruning thus fewer expanded nodes by the bidirectional search. On AAI7001588.
the other hand, the preprocessing time required to compute the Arc [3] H. Bast, D. Delling, A. Goldberg, M. Müller, T. Pajor,
Flags is significantly higher than the time required to compute the P. Sanders, D. Wagner, and R Werneck. Route planning in
CM. transportation networks. (MSR-TR-2014-4), January 2014.
CH CRP PbS-BT PbS-AVG Int. Workshop on Geographic Information Systems (GIS),
page 200, 2005.
8,000 [10] R.A. Finkel and J. L. Bentley. Quad trees: A data structure
8,000
for retrieval on composite keys. Acta Informatica, 4(1):1–9,
6,000 6,000 1974.
[11] J. Sankaranarayanan and H. Samet, H. andi Alborzi. Path
4,000 4,000 Oracles for Spatial Networks. In Proc. of the 35th VLDB
2,000 2,000
Conf., pages 1210–1221, 2009.
[12] H. Bast, S. Funke, D Matijevic, P. Sanders, and D. Schultes.
0
Q1 Q2 Q3 Q4 Q5
0
Q1 Q2 Q3 Q4 Q5
In Transit to Constant Time Shortest-Path Queries in Road
Networks. In Proc. of the Workshop on Algorithm
(a) NY (b) BAY Engineering and Experiments, pages 45–59, 2007.
·104 ·104 [13] E. Cohen, E. Halperin, H. Kaplan, and U. Zwick.
3 Reachability and distance queries via 2-hop labels. In Proc.
1.5 of the 13th ACM-SIAM Symposium on Discrete Algorithms
2
(SODA), pages 937–946, 2002.
1
[14] I. Abraham, D. Delling, A. V. Goldberg, and R. F. Werneck.
A hub-based labeling algorithm for shortest paths in road
0.5 1
networks. In Proc. of the 10th Int. Symposium on
Experimental Algorithms, pages 230–241, 2011.
0 0
Q1 Q2 Q3 Q4 Q5 Q1 Q2 Q3 Q4 Q5 [15] P. Sanders and D. Schultes. Highway Hierarchies Hasten
(c) FLA (d) CAL
Exact Shortest Path Queries. In Proc. of the 13th European
Conf. on Algorithms (ESA), pages 568–579, 2005.
Figure 8: Performance of shortest path queries vs. query sets. [16] A. D. Zhu, H. Ma, X. Xiao, S. Luo, Y. Tang, and S. Zhou.
Shortest Path and Distance Queries on Road Networks:
Towards Bridging Theory and Practice. In Proc. of the 32nd
Bidirectional Arc Flags CM
SIGMOD Conf., pages 857–868, 2013.
12 3,000 [17] L. Wu, X. Xiao, D. Deng, G. Cong, and A. D. Zhu. Shortest
Path and Distance Queries on Road Networks : An
9 Experimental Evaluation. In Proc. of the 39th VLDB Conf.,
2,000
pages 406–417, 2012.
6
[18] Y. W. Huang, N. Jing, and E. A. Rundensteiner. Hierarchical
1,000 path views : A model based on fragmentation and
3
transportation road types. In Proc. of the 3rd ACM Workshop
0 0 Geographic Information Systems (GIS),, 1995.
8 16 24 32 40 48 8 16 24 32 40 48
[19] S. Jung and S. Pramanik. Hiti graph model of topographical
(a) Preprocessing time (ms) (b) Visited nodes roadmaps in navigation systems. In Proc. of the 12th ICDE
Conf., pages 76–84, 1996.
Figure 9: Evaluation of Arc Flags & CM using ROME dataset. [20] D. Delling, A. V. Goldberg, I. Razenshteyn, and R. F.
Werneck. Graph Partitioning with Natural Cuts. In Proc. of
the 35th Int. Parallel & Distributed Processing Symposium
[4] D. Delling, A. V. Goldberg, T. Pajor, and R. F. Werneck. (IPDPS), pages 1135–1146, 2011.
Customizable route planning. In Proc. of the 10th Int. [21] A. E. Feldmann and L/ Foschini. Balanced Partitions of
Symposium on Experimental Algorithms (SEA), pages Trees and Applications. In 29th Symp. on Theoretical
376–387, 2011. Aspects of Computer Science, volume 14, pages 100–111,
[5] P. Hart, N. Nilsson, and B. Raphael. Formal Basis for the Paris, France, 2012.
Heuristic Determination of Minimum Cost PAths. IEEE [22] G. Karypis and V. Kumar. A Fast and High Quality
Transactions of Systems Science and Cybernetics, Multilevel Scheme for Partitioning Irregular Graphs. SIAM
4(2):100–107, 1968. Journal on Scientific Computing, 20(1):359–392, 1998.
[6] A. V. Goldberg and C. Harrelson. Computing the Shortest [23] Y. W. Huang, N. Jing, and E. Rundensteiner. Effective Graph
Path : A * Search Meets Graph Theory. In Proc. of the 16th Clustering for Path Queries in Digital Map Databases. In
ACM-SIAM Symposium on Discrete Algorithms (SODA), Proc. of the 5th Int. Conf. on Information and Knowledge
pages 156–165, 2005. Management, pages 215–222, 1996.
[7] J. Maue, P. Sanders, and D. Matijevic. Goal-directed [24] X. Sui, D. Nguyen, M. Burtscher, and K. Pingali. Parallel
shortest-path queries using precomputed cluster distances. graph partitioning on multicore architectures. In Proc. of the
Journal on Experimental Algorithms, 14:2:3.2–2:3.27, 23rd Int. Conf. on Languages and Compilers for Parallel
January 2010. Computing, pages 246–260, 2011.
[8] E. Köhler, R. H. Möhring, and H. Schilling. Fast [25] R. W. Floyd. Algorithm 97: Shortest path. Communications
point-to-point shortest path computations with arc-flags. In of the ACM, 5:345, 1962.
Proc. of the 9th DIMACS Implementation Challenge, 2006. [26] https://graphhopper.com.
[9] J. Sankaranarayanan, H. Alborzi, and H. Samet. Efficient [27] http://www.dis.uniroma1.it/challenge9/.
query processing on spatial networks. In Proc. of the 2005