有向无环图上k步可达查询优化算法

作者：杜明; 杨安平; 周军锋^*; 陈子阳; 杨云

来源：计算机应用, 2020, 40(02): 426-433.

• 有向无环图
• k步可达性查询
• hop点最短路径索引
• 双向互逆拓扑索引
• 双向遍历

k步可达查询用于在给定的有向无环图(DAG)中回答两点之间是否存在长度不超过k的路径。针对现有方法的索引规模大、查询处理效率低的问题,提出一种基于部分点的双向最短路径索引来提升索引的可达信息覆盖率,并提出一组优化规则来减小索引规模;然后提出基于简化图的正反互逆拓扑索引来加速回答不可达查询;最后提出远距离优先的双向遍历策略来提高查询处理的效率。基于21个真实数据集(如引用网络、社交网络等)的实验结果表明,相比已有的高效方法PLL及BFSI-B,所提出的算法具有更小的索引规模和更快的查询响应速度。

• 单位
  东华大学; 上海立信会计金融学院