The shortest path algorithm performance comparison in graph and relational database on a transportation network

  • Mario Miler Faculty of geodesy, University of Zagreb
  • Damir Medak Faculty of geodesy, University of Zagreb
  • Dražen Odobašić Faculty of geodesy, University of Zagreb
Keywords: pgRouting, OpenStreetMap, Dijkstra, benchmark, Neo4j, PostgreSQL

Abstract

In the field of geoinformation and transportation science, the shortest path is calculated on graph data mostly found in road and transportation networks. This data is often stored in various database systems. Many applications dealing with transportation network require calculation of the shortest path. The objective of this research is to compare the performance of Dijkstra shortest path calculation in PostgreSQL (with pgRouting) and Neo4j graph database for the purpose of determining if there is any difference regarding the speed of the calculation. Benchmarking was done on commodity hardware using OpenStreetMap road network. The first assumption is that Neo4j graph database would be well suited for the shortest path calculation on transportation networks but this does not come without some cost. Memory proved to be an issue in Neo4j setup when dealing with larger transportation networks.

Author Biographies

Mario Miler, Faculty of geodesy, University of Zagreb
Department of geoinformatics
Damir Medak, Faculty of geodesy, University of Zagreb
Department of geoinformatics
Dražen Odobašić, Faculty of geodesy, University of Zagreb
Department of geoinformatics

References

1. Dreyfus SE. An Appraisal of Some Shortest-Path Algorithms. Operations Research. 1969 May 1;17(3):395–412.

2. Golden BL. Shortest Path Algorithms: A Comparison. Massachusetts Institute of Technology, Operations Research Center; 1975.

3. Cherkassky B V., Goldberg A V., Radzik T. Shortest paths algorithms: theory and experimental evaluation. 1994 Jan 23;516–25.

4. Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms, Third Edition. BOOK. The MIT Press; 2009. p. 1312.

5. Zlatanova S, Baharin SSK. Optimal Navigation of First Responders Using DBMS. 3rd International Conference on Information Systems for Crisis Response and Management 4th International Symposium on GeoInformation for Disaster Management. 2008;541–54 606.

6. Tuot C, Obradovic D, Fichter F, Dengel A. CRUV - A Collaborative Route-Planning System for Utility Vehicles. 2010;

7. Innerebner M, Böhlen M, Gamper J. ISOGA: a system for geographical reachability analysis. Liang SHL, Wang X, Claramunt C, editors. Berlin, Heidelberg: Springer Berlin Heidelberg; 2013. p. 180–9.

8. Codd EF. A relational model of data for large shared data banks. 1970. MD computing computers in medical practice. ACM; 1970;15(3):162–6.

9. Dominguez-Sal D, Urbón-Bayes P, Giménez-Vanó A, Gómez-Villamor S, Martinez-Bazán N, Larriba-Pey J. Survey of graph database performance on the hpc scalable graph analysis benchmark. Web-Age Information Management. Springer; 2010;37–48.

10. Stonebraker M, Cetintemel U. “One Size Fits All”: An Idea Whose Time Has Come and Gone. 21st International Conference on Data Engineering ICDE05. Ieee; 2005;0(Icde):2–11.

11. Strauch C. NoSQL Databases. Lecture Notes Stuttgart Media. Hochschule der Medien, Stutgart; 2010;1–8.

12. Orend K. Analysis and Classification of NoSQL Databases and Evaluation of their Ability to Replace an Object-relational Persistence Layer. Architecture. Citeseer; 2010. p. 100.

13. Tiwari S. Professional NoSQL. 1 edition. Wrox; 2011.

14. Sadalage PJ, Fowler M. NoSQL Distilled: A Brief Guide to the Emerging World of Polyglot Persistence. 1 edition. Addison-Wesley Professional; 2012.

15. Ciglan M, Averbuch A, Hluchy L. Benchmarking Traversal Operations over Graph Databases. 2012 IEEE 28th International Conference on Data Engineering Workshops. IEEE; 2012. p. 186–9.

16. Angles R, Gutierrez C. Survey of graph database models. ACM Computing Surveys. ACM; 2008;40(1):1–39.

17. Euler L. Solutio problematis ad geometriam situs pertinentis. Commentarii Academiae Scientiarum Imperialis Petropolitanae. Nature Publishing Group; 1736;8:128–40.

18. Dominguez-Sal D, Martinez-Bazan N, Muntes-Mulero V, Baleta P, Larriba-Pay JL. A discussion on the design of graph database benchmarks. 2010 Sep 13;25–40.

19. Rodriguez MA, Neubauer P. Constructions from Dots and Lines. Science. American Society for Information Science and Technology; 2010;X(X):35–41.

20. NeoTechnology. The Neo database - A Technology Introduction. 2006; Available from: http://dist.neo4j.org/neo-technology-introduction.pdf

21. Seng J-L, Yao SB, Hevner AR. Requirements-driven database systems benchmark method. Decision Support Systems. 2005 Jan 1;38(4):629–48.

22. TCP. Transaction Processing Performance Council [Internet]. 2011 [cited 2011 Sep 21]. Available from: http://www.tpc.org/default.asp

23. Ray S, Simion B, Demke Brown A. Jackpine: A benchmark to evaluate spatial database performance. Data Engineering (ICDE), 2011 IEEE 27th International Conference on. IEEE; 2011. p. 1139–50.

24. Bader DA, Feo J, Gilbert J, Kepner J, Koester D. Hpc scalable graph analysis benchmark. Citeseer. Citeseer; 2009;(HiPC 2005):1–10.

25. Coast S. OpenStreetMap project [Internet]. 2013. Available from: http://www.openstreetmap.org/

26. Ramm F, Topf J. Towards a New Data Model for OpenStreetMap [Internet]. 2007 p. 1–42. Available from: http://www.remote.org/frederik/tmp/towards-a-new-data-model-for-osm.pdf

27. Moeller C. osm2po [Internet]. 2011. Available from: http://osm2po.de/

28. NeoTechnology. The Neo4j Manual v1.7.2 [Internet]. NeoTechnology; 2012. Available from: http://docs.neo4j.org/chunked/1.7.2/

29. Naphtali Rishe AV. A Benchmarking Technique for DBMS`s with Advanced Data Models.
Published
2014-02-28
How to Cite
Miler, M., Medak, D., & Odobašić, D. (2014). The shortest path algorithm performance comparison in graph and relational database on a transportation network. PROMET - Traffic & Transportation, 26(1), 75-82. https://doi.org/https://doi.org/10.7307/ptt.v26i1.1268
Section
Articles

Most read articles by the same author(s)