一种并行环境下的有向图可达性链表生成及查询方法

摘要

一种并行环境下的有向图可达性链表生成及查询方法，属于大图数据处理领域。将一个有向图分发到各个处理机中，每个处理机存储图中的节点及节点所对应的子节点；将分割到各个处理机内的图数据压缩；计算主干图上主干节点可达性编码；构建链式索引；在链式索引上建立跳表；各处理机间进行数据通信：各处理机向其他处理机发送跳表信息；各处理机更新自身的跳表信息；建立全图可达性索引。本发明通并行环境下的图可达性压缩技术，极大降低图数据大小、降低系统计算负载，使得系统处理更大规模的图数据。本发明提高从磁盘上读取数据的速度，间接加快查询速度，保证查询结果准确性，极大降低并行计算系统在查询时的网路通信代价和查询时间。

主权项

一种并行环境下的有向图可达性链表生成方法，其特征在于：包括以下步骤：步骤1：首先将一个有向图数据G分发到各个处理机中，每个处理机中存储有图中的节点及节点所对应的子节点；步骤2：对分割到各个处理机内的图数据进行压缩，过程为：步骤2‑1：将所有与其他处理机有联系的节点设为主干节点，所有主干节点经过k跳后所能到达的节点形成一个集合R；步骤2‑2：确定集合R的边界节点经k跳后所能到达的节点形成另一个集合，依次计算该另一个集合中每个元素的评价函数，公式为：r(C_x) = 1/|C_x/R|式中，r(C_x)表示评价函数，C_x为主干节点周围k跳内的节点的集合，x为待处理节点，R为当前的主干节点集合的涵盖范围集合；该另一个集合中评价函数最大值所对应的节点确定为主干节点，此主干节点经过k跳后所能到达的节点均添加至集合R中，重复步骤2‑2，直至集合R与有向图数据G中的节点集合相同；步骤2‑3：各个处理器将经步骤2‑2压缩处理后的非主干节点信息存储至磁盘上；对于所有的非主干节点，在各个处理机当中进行深度为k的广度优先搜索，将k跳内的所有主干节点索引，作为该非主干节点的附加信息，写入磁盘中，其中，所有主干节点索引形成主干节点集合；步骤2‑4：更新主干节点的邻接表信息，并将结果写回磁盘；对于所有的主干节点，在各个处理机当中进行深度为k的广度优先搜索，将k跳内的所有主干节点信息添加到邻接表中，生成主干图；步骤3：计算主干图上主干节点的可达性编码；步骤3‑1：计算主干图生成树：首先进行深度优先遍历获得生成树森林，添加虚拟根节点，将整个生成森林转化为一个生成树，并保存被删除的边，并将这些删除的边连接起来；步骤3‑2：对主干图的生成树再进行深度优先遍历，然后根据深度优先遍历访问次序进行编码；步骤4：利用步骤3‑1所保存的删除的边，构建链式索引；步骤4‑1：根据主干节点之间的位置建立关系链：首先任意选择一个节点，建立该节点与其一个可到达的节点间的初始关系链；步骤4‑2：依次处理与初始关系链上节点相邻的节点，分别建立这些相邻节点的关系链；判断相邻节点形成的关系链中是否有与初始关系链中节点相同的节点，若存在，则将获得关系链最长的链作为输出结果，并将相邻节点剩余的部分构建成新关系链；重复执行步骤4‑2，直至步骤3‑1所有删除的节点都在关系链集合中，完成链式索引的建立；步骤4‑3：标记链索引；主链上保存主链的标号、链所能到达处理机标号、主链所能到达的其他主链标号、主链所能到达从链标号，从链上保存从链标号、从链所能到达的从链标号，从链所能到达的主链标号；步骤5：在链式索引上建立跳表；步骤6：各处理机间进行数据通信：各处理机向其他处理机发送跳表信息，并根据接受到的其他处理机的跳表信息来更新自身的跳表信息，实现全图可达性索引的建立。