Engineering multilevel overlay graphs for shortest-path queries

ABSTRACT

An overlay graph of a given graph G = (V, E) on a subset S ⊆ V is a graph with vertex set S and edges corresponding to shortest paths in G. In particular, we consider variations of the multilevel overlay graph used in Schulz et al. [2002] to speed up shortest-path computation. In this work, we follow up and present several vertex selection criteria, along with two general strategies of applying these criteria, to determine a subset S of a graph's vertices. The main contribution is a systematic experimental study where we investigate the impact of selection criteria and strategies on multilevel overlay graphs and the resulting speed-up achieved for shortest-path computation: Depending on selection strategy and graph type, a centrality index criterion, selection based on planar separators, and vertex degree turned out to perform best.

REFERENCES

• 1: Ahuja, R. K., Magnanti, T. L., and Orlin, J. B. 1993. Network Flows: Theory, Algorithms, and Applications. Prentice Hall. Englewood Cliffs, NJ.
• 2: Bast, H., Funke, S., Matijevic, D., Sanders, P., and Schultes, D. 2007. Transit to constant shortest-path queries in road networks. In Proceedings of the 9th Workshop on Algorithm Engineering and Experiments. SIAM. 46--59.
• 3: Bauer, R. 2006. Dynamic speed-up techniques for Dijkstra's algorithm. M.S. thesis, Universität Karlsruhe (TH), Fakultät für Informatik. http://i11www.ira.uka.de/teaching/theses/files/da-rbauer-06.pdf.
• 4: Bollobás, B. 1985. Random Graphs. Academic Press, London.
• 5: Borgi, I., Graf, J., Holzer, M., Schulz, F., and Willhalm, T. 2005. A graph generator. http://i11www.ira.uka.de/resources/graphgenerator.php.
• 6: Brandes, U. and Erlebach, T., Eds. 2005. Network Analysis. LNCS, vol. 3418. Springer, New York.
• 7: Delling, D., Holzer, M., Müller, K., Schulz, F., and Wagner, D. 2007a. High-performance multi-level graphs. In Proceedings of the Workshop on DIMACS Shortest-Path Challenge. To appear. http://i11www.ira.uka.de/members/mholzer/publications/pdf/dhmsw-hpmlg-06.pdf.
• 8: Delling, D., Sanders, P., Schultes, D., and Wagner, D. 2007b. Highway hierarchies star. In Proceedings of the Workshop on DIMACS Shortest-Path Challenge. To appear. http://i11www.ira.uka.de/members/delling/files/dssw-hhs-06.pdf.
• 9: Dijkstra, E. W. 1959. A note on two problems in connexion with graphs. Numerische Math. 1, 269--271.
• 10: Goldberg, A. and Harrelson, C. 2005. Computing the shortest path: A* search meets graph theory. In Proceedings of the 16th Symposium on Discrete Algorithms. SIAM, 156--165.
• 11: Goldberg, A., Kaplan, H., and Werneck, R. 2006. Reach for A*: Efficient point-to-point shortest path algorithms. In Proceedings of the 8th Workshop on Algorithm Engineering and Experiments. SIAM. 129--143.
• 12: Gutman, R. 2004. Reach-based routing: A new approach to shortest path algorithms optimized for road networks. In Proceedings of the 6th Workshop on Algorithm Engineering and Experiments. SIAM. 100--111.
• 13: Holzer, M. 2003. Hierarchical speed-up techniques for shortest-path algorithms. M.S. thesis, Universität Konstanz, Fachbereich Informatik und Informationswissenschaft. http://www.ub.uni-konstanz.de/kops/volltexte/2003/1038/.
• 14: Holzer, M., Schulz, F., and Willhalm, T. 2004. Combining speed-up techniques for shortest-path computations. In Proceedings of the 3rd Workshop on Experimental and Efficient Algorithms. LNCS, vol. 3059. Springer, New York. 269--284.
• 15: Holzer, M., Prasinos, G., Schulz, F., Wagner, D., and Zaroliagis, C. 2005. Engineering planar separator algorithms. In Proceedings of the 13th European Symposium on Algorithms. LNCS, vol. 3669. Springer, New York. 628--639.
• 16: Jing, N., Huang, Y.-W., and Rundensteiner, E. A. 1998. Hierarchical encoded path views for path query processing: An optimal model and its performance evaluation. IEEE Trans. Knowledge Data Eng. 10, 3.
• 17: Jung, S. and Pramanik, S. 2002. An efficient path computation model for hierarchically structured topographical road maps. IEEE Trans. Knowledge Data Eng. 14, 5.
• 18: Karypis, G. 2005. METIS. http://www-users.cs.umn.edu/~karypis/metis.
• 19: Lauther, U. 2004. An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background. In Geoinformation und Mobilität -- von der Forschung zur praktischen Anwendung. Vol. 22. IfGI prints, Institut für Geoinformatik, Münster. 219--230.
• 20: Möhring, R. H., Schilling, H., Schütz, B., Wagner, D., and Willhalm, T. 2005. Partitioning graphs to speed up Dijkstra's algorithm. In Proceedings of the 4th Workshop on Experimental and Efficient Algorithms. 189--202.
• 21: Näher, S. and Mehlhorn, K. 1999. The LEDA Platform of Combinatorial and Geometric Computing. Cambridge University Press, Cambridge. http://www.algorithmic-solutions.com.
• 22: Sanders, P. and Schultes, D. 2005. Highway hierarchies hasten exact shortest path queries. In Proceedings of the 17th European Symposium on Algorithms.
• 23: Sanders, P. and Schultes, D. 2006. Engineering highway hierarchies. In Proceedings of the 14th European Symposium on Algorithms. LNCS, vol. 4168. Springer, New York. 804--816.
• 24: Schultes, D. and Sanders, P. 2007. Dynamic highway-node routing. In Proceedings of the 6th Workshop on Experimental and Efficient Algorithms. LNCS. Springer, New York. 66--79.
• 25: Schulz, F. 2005. Timetable information and shortest paths. Ph.D. thesis, Universität Karlsruhe (TH), Fakultät für Informatik.
• 26: Schulz, F., Wagner, D., and Weihe, K. 2000. Dijkstra's algorithm on-line: An empirical case study from public railroad transport. J. Exp. Algorithmics 5, 12.
• 27: Schulz, F., Wagner, D., and Zaroliagis, C. 2002. Using multi-level graphs for timetable information in railway systems. In Proceedings of the 4th Workshop on Algorithm Engineering and Experiments. LNCS, vol. 2409. Springer, New York. 43--59.
• 28: Wagner, D. and Willhalm, T. 2003. Geometric speed-up techniques for finding shortest paths in large sparse graphs. In Proceedings of the 11th European Symposium on Algorithms. LNCS, vol. 2832. Springer, New York. 776--787.
• 29: Willhalm, T. and Wagner, D. 2007. Shortest path speedup techniques. In Algorithmic Methods for Railway Optimization. LNCS, vol. 4359. Springer, New York.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
Dijkstra's algorithm, hierarchical, multilevel, overlay graph, preprocessing, shortest path, speed-up technique, vertex selection