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

• 作者: 丁琳琳 李世峰 段雨晴
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: 大规模有向图 平面图覆盖 标签索引方法 可达查询
• 年，卷（期）: 2015,（11）
• 所属期刊栏目: 数据库技术
• 页码范围: 1326-1334
• 页数: 9页
• 分类号: TP311.13
• 字数: 6329字
• 语种: 中文
• DOI: 10.3778/j.issn.1673-9418.1412056

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	丁琳琳	辽宁大学信息学院	16	19	3.0	3.0
2	李世峰	辽宁大学信息学院	2	2	1.0	1.0
3	段雨晴	香港科技大学电子及计算机工程学系	1	1	1.0	1.0