Title: Solving Massive Graph Problems using Petascale Computing

Graph theoretic problems are representative of fundamental kernels in traditional and emerging computational sciences such as chemistry, biology, and medicine, as well as applications in national security. Yet they pose serious challenges for parallel machines due to non-contiguous, concurrent accesses to global data structures with low degrees of locality. Few parallel graph algorithms outperform their best sequential implementation due to long memory latencies and high synchronization costs. In this talk, we consider several graph theoretic kernels for connectivity and centrality and discuss how the features of petascale architectures will affect algorithm development, ease of programming, performance, and scalability.

Title: Highway Hierarchies Star

We combine two speedup techniques for route planning in road networks: highway hierarchies (HH) and goal directed search using landmarks (ALT). It turns out that there are several interesting synergies and one incompatibility. Highway hierarchies yield a way to implement landmark selection more efficiently and to store landmark information more space efficiently than before. ALT gives queries in highway hierarchies an excellent sense of direction. However, proving the optimality of paths takes longer than one might expect. In particular, a much simpler speedup technique for highway hierarchies---distance tables for the highest level of the hierarchy---yield better relative speedups than landmarks. Combining all three techniques is not worth the effort. In contrast, all three techniques harmonise well for approximate queries where they yield query time almost four times smaller than for exact queries and a total error of only 0.06%.

Title: Single-Source Shortest Paths with the Parallel Boost Graph Library

The Parallel Boost Graph Library (Parallel BGL) is a library of graph algorithms and data structures for distributed-memory computation on large graphs. Developed with the Generic Programming paradigm, the Parallel BGL is highly customizable, supporting various graph data structures, arbitrary vertex and edge properties, and different communication media. In this paper, we describe the implementation of two parallel variants of Dijkstra's single-source shortest paths algorithm in the Parallel BGL. We also provide an experimental evaluation of these implementations using synthetic and real-world benchmark graphs from the 9th DIMACS Implementation Challenge.

Title: Implementations of Routing Algorithms for Transportation Networks

We describe theoretical and experimental results on a generalization of Dijkstra's algorithm to finding regular-language-constrained shortest paths. This algorithm forms a model for single-source shortest paths and point-to-point problems that generalizes several previously published algorithms for multimodal shortest path problems.

The experiments include work with two different implementations of the algorithm. One is the original implementation of a special case of the problem, that formed a part of the TRANSIMS project at the Los Alamos National Laboratory. The other is a new implementation of the general regular-language-constrained shortest path algorithm that uses an implicit representation of the product graph. The second implementation also provides several speed-up techniques which have previously only been used for standard point-to-point shortest path problems.

Through our experiments, we study the scalability of the algorithm with respect to the network size as well as with respect to the constraining language complexity. Further, we study the effectiveness of speed-up techniques such as bidirectional search, shortest path containers, bit-vectors and the multilevel technique when applied to the multimodal shortest path problems formalized by the regular language constraints.

Title: An Experimental Evaluation of Point-To-Point Shortest Path Calculation on Roadnetworks with Precalculated Edge-Flags

We present an efficient algorithm for fast and exact calculation of point to point shortest paths in graphs with geometrical information in nodes (coordinates), e.g. road networks. We compared this method experimentally to a classical Dijksta implementation using USA road networks with travel times and report on speedup, preprocessing time, and memory needed to store preprocessing results.

Title: Parallel Shortest Path Algorithms for Solving Large-Scale Instances

We present an experimental study of parallel algorithms for solving the single source shortest path problem with non-negative edge weights (NSSP) on large-scale graphs. We implement Meyer and Sander's $\Delta$-stepping algorithm and report performance results on the Cray MTA-2, a multithreaded parallel architecture. The MTA-2 is a high-end shared memory system offering two unique features that aid the efficient implementation of irregular parallel graph algorithms: the ability to exploit fine-grained parallelism, and low-overhead synchronization primitives. Our implementation exhibits remarkable parallel speedup when compared with a competitive sequential algorithm, for low-diameter sparse graphs. For instance, $\Delta$-stepping on a directed scale-free graph of 100 million vertices and 1 billion edges takes less than ten seconds on 40 processors of the MTA-2, with a relative speedup of close to 30. To our knowledge, these are the first performance results of a parallel NSSP problem on realistic graph instances in the order of billions of vertices and edges.

Title: High-Performance Multi-Level Graphs

Shortest-path computation is a frequent task in practice. Owing to ever-growing real-world graphs, there is a constant need for faster algorithms. In the course of time, a large number of techniques to heuristically speed up Dijkstra's shortest-path algorithm have been devised. This work reviews the multi-level technique to answer shortest-path queries exactly, which makes use of a hierarchical decomposition of the input graph and precomputation of supplementary information. We develop this preprocessing to the maximum and introduce several ideas to enhance this approach considerably, by reorganizing the precomputed data in partial graphs and optimizing them individually. To answer a given query, certain partial graphs are combined to a search graph, which can be explored by a simple and fast procedure. Experiments confirm query times of less than 170 microseconds for a road graph with over 15 million vertices.

Title: TRANSIT: Ultrafast Shortest-Path Queries with Linear-Time Preprocessing

We introduce the concept of transit nodes, as a means for preprocessing a road network, with given coordinates for each node and a travel time for each edge, such that point-to-point shortest-path queries can be answered extremely fast.

The transit nodes are a set of nodes as small as possible with the property that every shortest path that covers a certain not too small euclidean distance passes through at least on of these nodes. With such a set and precomputed distances from each node in the graph to its few, closest transit nodes, all non-short-range shortest path queries become a simple matter of a small number of table lookups.

For the US road network, which has about 24 million nodes and 58 million edges, we achieve a worst-case query processing time of 10 microseconds (not milliseconds) for 99% of all queries. This improves over the best previously reported numbers by two orders of magnitude.

Title: Breadth first Search on Massive Graphs

We consider the problem of Breadth First Search (BFS) traversal on massive sparse undirected graphs. Despite the existence of simple linear time algorithms in the RAM model, it was considered non-viable for massive graphs because of the I/O cost it incurs. Munagala, Ranade and later Mehlhorn, Meyer gave efficient algorithms (refered as MR_BFS and MM_BFS) for computing BFS level decompositions in an external memory model. Ajwani et al. implemented MR_BFS and the randomized variant of MM_BFS using the external memory library STXXL and gave a comparative study of the two algorithms on various graph classes. In this talk, we review that result and show its extension demonstrating the effectiveness and viability of the BFS implementations on various other synthetic and real world benchmarks. Also, we present the implementation of the deterministic variant of MM_BFS and show that in most cases, it outperforms the randomized variant. Furthermore, we propose a heuristic that improves the performance of the deterministic variant.

Title: Implementations and Empirical Comparison of K Shortest Loopless Path algorithms

Given an integer K, the aim of the K shortest loopless paths problem is the determination of the best K point-to-point paths with no repeated nodes, by non-decreasing order of cost. We survey deviation algorithms for this problem that only generate loopless paths, discuss implementations of these algorithms, and then compare them empirically.

Title: K Shortest Path Algorithms

This paper is focussed on algorithms to solve the k-shortest path problem. Three codes were described and compared on rand and grid networks (using random generators available for this challenge). Codes were tested also for some real-world instances proposed for this workshop One million paths were ranked in less than 3 seconds on random instances with 10 000 nodes and 10 seconds for real-world instances).

Title: Fast Point-to-Point Shortest Path Computations with Arc-Flags

We present an acceleration method for point-to-point (P2P) shortest path computations on large graphs. Our method is based on Dijkstra's algorithm. We assume that for the same input graph the shortest path problem has to be solved repeatedly for different node pairs. Thus, preprocessing of the graph data is possible and can be used to support the computation of shortest path queries. Our method is a generalized goal directed approach, which is called the "arc-flag approach". It divides the graph into regions and gathers information on whether an arc is on any shortest path into a given region. On a subnetwork of the German road network\footnote{network data from the PTV Europe road network from the DIMACS Challenge homepage} (with 1M nodes and 2.5M arcs) the arc-flag method achieves speedup factors of more than 1,470 (on average) using only 450 bits of additional information per arc. The preprocessing step of the arc-flag method for networks of this size can take up to 120 minutes.

Title: Robust, Almost Constant Time Shortest-Path Queries on Road Networks

When you drive to somewhere `far away', you will leave your current location via one of only a few `important' traffic junctions. Starting from this informal observation, we develop a generic algorithmic approach---transit node routing---that allows us to reduce quickest-path queries in road networks to a small number of table lookups. We implement this basic approach using highway hierarchies. For the road maps of Western Europe and the United States, our best query times improve over the best previously published figures by two orders of magnitude. This is also more than one million times faster than the best known algorithm for general networks.

Title: Better Landmarks within Reach

In this paper we continue the study or algorithms based on combining A* search with landmark-based lower bounds and reach-based pruning approaches, started in our previous paper. In particular, we develop the reach-aware landmark approach. The idea behind this approach is to generate landmark data only for high-reach ("important") vertices. This allows saving space at a small cost to query efficiency. We can use some of the saved space to increase the number of landmarks, and win both in space and time efficiency. Other contribution of the paper include improved locality and a faster algorithm for computing exact reach values. In addition to road networks, we show that our techniques apply to other graphs, in particular grid graphs.