Computing source-to-target shortest paths for complex networks in RDBMS

作者：Ahmed Aly^*; Thomo Alex

来源：Journal of Computer and System Sciences, 2017, 89: 114-129.

DOI：10.1016/j.jcss.2016.09.011

• Big graphs
• Relational databases
• SQL
• Shortest paths algorithms

How do we deal with the exponential growth of complex networks? Are existing algorithms introduced decades ago able to work on big network graphs? In this work, we focus on computing shortest paths (SP) from a source to a target in large network graphs. Main memory algorithms require the graph to fit in memory and they falter when this requirement is not met. We explore SQL-based solutions using a Relational Database Management System (RDBMS). Our approach leverages the intelligent scheduling that a RDBMS performs when executing set-at-a-time expansions of graph vertices, which is in contrast to vertex-at-a-time expansions in classical SP algorithms. Our algorithms perform orders of magnitude faster than baselines and even faster than main memory algorithms for large graphs. Also, we show that our algorithms on RDBMS outperform counterparts running on modern native graph databases, such as Neo4j.

• 出版日期2017-11