Computing Shortest Path for Graph Using FEM Framework

Abstract: This paper focus on computing shortest path as finding the distance between two vertices in graph or tree. Graph data can use in many domains like a social network and in knowledge graph. This graph search includes sub-graph. The problem of finding the shortest path between two nodes can be solved using the salesman traveling path, minimal spanning tree, and the likewise. The problem occurred with the graph based searching when a graph is too big to fit in memory and for that, it uses the external memory. The disk-based method has some limitations when graph exceeds its size. In this paper, we are analyzing the shortest path for efficient relational approaches to graph search queries. For this, we use three relational operator based-on which we introduce the framework for bridge the gap between graph operation and relational operator. We show the new feature of SQL such as merge statement and windows function to improve the performance of FEM framework. To avoid extra indexing overhead and improve scalability and performance, we propose an edge weight aware graph partitioned schema and design bi-directional restrictive BFS (breadth-first-search). The final experimental results illustrate our relational approach with optimization strategies can achieve high performance and scalability.

Keywords: graph, shortest path, Relational database, graph search queries, graph indexing