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

来源：计算机科学与探索杂志2015年第11期北京时间：

作者：段雨晴，李世峰，丁琳琳

单位：1. 香港科技大学 电子及计算机工程学系，中国香港2. 辽宁大学 信息学院，沈阳 110036

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

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