Relational Approach for Shortest Path Discovery over Large Graphs

With the rapid growth of large graphs, the authors cannot assume that graphs can still be fully loaded into memory, thus the disk-based graph operation is inevitable. In this paper, they take the shortest path discovery as an example to investigate the technique issues when leveraging existing infrastructure of Relational DataBase (RDB) in the graph data management. Based on the observation that a variety of graph search queries can be implemented by iterative operations including selecting frontier nodes from visited nodes, making expansion from the selected frontier nodes, and merging the expanded nodes into the visited ones, they introduce a relational FEM framework with three corresponding operators to implement graph search tasks in the RDB context.

Provided by: VLD Digital Topic: Data Management Date Added: Aug 2012 Format: PDF

Find By Topic