关键词: 大规模有向图, 平面图覆盖, 标签索引方法, 可达查询

Abstract: With the springing up and wide use of emerging applications, such as semantic networks, social networks and bioinformatics networks, the research on increasingly large-scale graph data has become a hot and difficult problem. Reachability query is a fundamental query frequently used in graph data analysis and processing which has important effectiveness. Some complex queries can be decomposed into operation sets containing multiple reachability queries. For processing the reachability query of large graph, this paper proposes planar graph cover based reachability query processing in large graph. Firstly, this paper presents a planar graph cover based reachability labeling index method (PGCL). PGCL uses the optimal tree as the preprocessing to process the planar graph cover. By creating the optimal tree, optimal tree decomposition and some plane processing, this paper obtains the planar graph cover of a DAG (directed acyclic graph), which maximally retains the accessibility information of the original image, and creates labels for vertexes and compresses the reachability transitive closure. Then, this paper designs a reachability query algorithm based on PGCL to effectively process the reachability query of large graph. The experimental results on real data sets show that the proposed query method has better performance of compressing the transitive closure, and enhances the performance of reachability query.

Key words:  large-scale digraph, planar graph cover, labeling index method, reachability query