基于平面图覆盖的大规模图可达查询处理

摘要：

随着语义网络、社交网络、生物信息网络等新兴应用的涌现及普及,图数据的规模不断增大,针对大规模图数据的研究成为当今的研究热点和难点.可达查询是图数据处理中频繁使用的基础性查询,一些复杂的查询能够分解成包含多个可达查询的操作集合,其高效处理具有重要意义.针对大规模图的可达查询,提出了一种基于平面图覆盖的大规模图可达查询处理方法.首先给出了一种基于平面图覆盖的可达标签索引方法(planar graph cover based reachability labeling index method,PGCL).该方法将最优树作为预处理应用于平面图覆盖,通过最优树创建、最优树分解以及树分解平面化处理,得到有向无环图(directed acyclic graph, DAG)的平面图覆盖,最大限度地保留了原图的可达性信息,从而基于覆盖顶点创建二维标签,用于压缩可达传递闭包.设计了基于PGCL的可达查询算法,有效实现了大规模图的可达查询.通过大量实验证明了提出的查询方法在保证查询的高效性情况下,更好地压缩了传递闭包,提高了可达查询的处理效率.

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

所属期刊栏目：9

分类号：TP311.13(计算技术、计算机技术)

资助基金：The National Natural Science Foundation of China under Grant Nos. 61472169, 61174115, 61502215;the Sci-ence Research Normal Fund of Liaoning Province Education Department under Grant No. L2015193;the Doctoral Science Research Start Foundation of Liaoning Province under Grant No. 201501127;the Young Research Foundation of Liaoning University under Grant No. LDQN201438

在线出版日期：2015-11-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：1326-1334