计算机应用

作者：杜明, 杨安平, 周军锋, 陈子阳, 杨云

单位：1.东华大学 计算机科学与技术学院，上海 201620；2.上海立信会计金融学院 信息管理学院，上海 201620

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

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

来源：2020年第2期

《计算机应用》期刊编辑部

查看计算机应用杂志2020年第2期