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.
Dreyfus SE. An Appraisal of Some Shortest-Path Algorithms. Operations Research. 1969 May 1;17(3):395–412.
Golden BL. Shortest Path Algorithms: A Comparison. Massachusetts Institute of Technology, Operations Research Center; 1975.
Cherkassky B V., Goldberg A V., Radzik T. Shortest paths algorithms: theory and experimental evaluation. 1994 Jan 23;516–25.
Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms, Third Edition. BOOK. The MIT Press; 2009. p. 1312.
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.
Tuot C, Obradovic D, Fichter F, Dengel A. CRUV - A Collaborative Route-Planning System for Utility Vehicles. 2010;
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.
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.
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.
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.
Strauch C. NoSQL Databases. Lecture Notes Stuttgart Media. Hochschule der Medien, Stutgart; 2010;1–8.
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.
Tiwari S. Professional NoSQL. 1 edition. Wrox; 2011.
Sadalage PJ, Fowler M. NoSQL Distilled: A Brief Guide to the Emerging World of Polyglot Persistence. 1 edition. Addison-Wesley Professional; 2012.
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.
Angles R, Gutierrez C. Survey of graph database models. ACM Computing Surveys. ACM; 2008;40(1):1–39.
Euler L. Solutio problematis ad geometriam situs pertinentis. Commentarii Academiae Scientiarum Imperialis Petropolitanae. Nature Publishing Group; 1736;8:128–40.
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.
Rodriguez MA, Neubauer P. Constructions from Dots and Lines. Science. American Society for Information Science and Technology; 2010;X(X):35–41.
NeoTechnology. The Neo database - A Technology Introduction. 2006; Available from: http://dist.neo4j.org/neo-technology-introduction.pdf
Seng J-L, Yao SB, Hevner AR. Requirements-driven database systems benchmark method. Decision Support Systems. 2005 Jan 1;38(4):629–48.
TCP. Transaction Processing Performance Council [Internet]. 2011 [cited 2011 Sep 21]. Available from: http://www.tpc.org/default.asp
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.
Bader DA, Feo J, Gilbert J, Kepner J, Koester D. Hpc scalable graph analysis benchmark. Citeseer. Citeseer; 2009;(HiPC 2005):1–10.
Coast S. OpenStreetMap project [Internet]. 2013. Available from: http://www.openstreetmap.org/
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
Moeller C. osm2po [Internet]. 2011. Available from: http://osm2po.de/
NeoTechnology. The Neo4j Manual v1.7.2 [Internet]. NeoTechnology; 2012. Available from: http://docs.neo4j.org/chunked/1.7.2/
Naphtali Rishe AV. A Benchmarking Technique for DBMS`s with Advanced Data Models.
Guest Editor: Eleonora Papadimitriou, PhD
Editors: Dario Babić, PhD; Marko Matulin, PhD; Marko Ševrović, PhD.
The mission of our journal is to provide high quality communication of research results, which is crucial for the effectiveness of scientific research, the promotion of scientific information, new ideas, and original research in the field of traffic and transportation engineering.
1848-4069
0353-5320
Proud publisher
Accelerating Discoveries in Traffic Science |
2024 © Promet - Traffic&Transportation journal
