The shortest path algorithm performance comparison in graph and relational database on a transportation network
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.
References
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.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
