基于平面图覆盖的大规模图可达查询处理
随着语义网络、社交网络、生物信息网络等新兴应用的涌现及普及,使得图数据的规模不断增大,针对大规模图数据的研究成为当今的研究热点和难点.可达查询是图数据处理中频繁使用的基础性查询,一些复杂的查询能够分解成包含多个可达查询的操作集合,其高效处理具有重要意义.针对大规模图的可达查询,本文提出了一种基于平面图覆盖的大规模图可达查询处理方法.首先,提出了一种基于平面图覆盖的可达标签索引方法(PGCL).该方法将最优树作为预处理应用于平面图覆盖,通过创建最优树、最优树分解以及树分解的平面化处理,得到有向图的平面图覆盖,最大限度地保留了原图的可达性信息,从而基于覆盖顶点创建二维标签,用于压缩可达传递闭包.其次,设计了基于PGCL的可达查询算法,有效实现了大规模图的可达查询.最后,大量真实数据集的实验证明了本文提出的查询方法在保证查询的高效性情况下,更好地压缩了传递闭包,提高了可达查询的处理效率.
图数据 可达查询处理 标签索引方法 平面图覆盖
丁琳琳 李雪城 王大军 宋宝燕
辽宁大学 信息学院,辽宁 沈阳 110036
国内会议
广州
中文
569-576
2014-11-06（万方平台首次上网日期，不代表论文的发表时间）