Min-Forest: Fast Reachability Indexing Approach for Large-Scale Graphs on Spark Platform

摘要

Reachability query is an important graph operation in graph database which answers whether a vertex can reach another vertex through a path over the graph, and it is also fundamental to real applications involved with graph-shaped data. However, the increasingly large amount of data in real graph database makes it more challenging for query efficiency and scalability. In this paper, we propose Min-Forest approach to handle with reachability problem in large graphs. We present Min-Forest structure to transfer and label the original DAG, and introduce a 4-tuple labeling scheme to construct index for each vertices, which integrate interval labels for trees and non-tree labels. We design efficient reachability query algorithms for Min-Forest approach on the Cloud Platform of Spark. The experiment results show that query time of Min-Forest approach is also on average about 10~(-4) ms for large dense graphs, and query time and index construction time of our approach are linear for both sparse graphs and dense graphs. It can answer reachability queries much faster than the state-of-art approaches on real graphs database, especially on large and dense ones.