CAJ | 학술논문

随着语义网络、社交网络、生物信息网络等新兴应用的涌现及普及,图数据的规模不断增大,针对大规模图数据的研究成为当今的研究热点和难点.可达查询是图数据处理中频繁使用的基础性查询,一些复杂的查询能够分解成包含多个可达查询的操作集合,其高效处理具有重要意义.针对大规模图的可达查询,提出了一种基于平面图覆盖的大规模图可达查询处理方法.首先给出了一种基于平面图覆盖的可达标签索引方法(planar graph cover based reachability labeling index method,PGCL).该方法将最优树作为预处理应用于平面图覆盖,通过最优树创建、最优树分解以及树分解平面化处理,得到有向无环图(directed acyclic graph, DAG)的平面图覆盖,最大限度地保留了原图的可达性信息,从而基于覆盖顶点创建二维标签,用于压缩可达传递闭包.设计了基于PGCL的可达查询算法,有效实现了大规模图的可达查询.通过大量实验证明了提出的查询方法在保证查询的高效性情况下,更好地压缩了传递闭包,提高了可达查询的处理效率.
수착어의망락、사교망락、생물신식망락등신흥응용적용현급보급,도수거적규모불단증대,침대대규모도수거적연구성위당금적연구열점화난점.가체사순시도수거처리중빈번사용적기출성사순,일사복잡적사순능구분해성포함다개가체사순적조작집합,기고효처리구유중요의의.침대대규모도적가체사순,제출료일충기우평면도복개적대규모도가체사순처리방법.수선급출료일충기우평면도복개적가체표첨색인방법(planar graph cover based reachability labeling index method,PGCL).해방법장최우수작위예처리응용우평면도복개,통과최우수창건、최우수분해이급수분해평면화처리,득도유향무배도(directed acyclic graph, DAG)적평면도복개,최대한도지보류료원도적가체성신식,종이기우복개정점창건이유표첨,용우압축가체전체폐포.설계료기우PGCL적가체사순산법,유효실현료대규모도적가체사순.통과대량실험증명료제출적사순방법재보증사순적고효성정황하,경호지압축료전체폐포,제고료가체사순적처리효솔.
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 prob-lem. 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.