Planar Graph Cover Based Reachability Query Processing in Large Graph
Duan Yuqin · Jisuanji kexue yu tansuo · 2015
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.