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

• 作者: 周军锋 杜明 杨云 杨安平 陈子阳
• 来源期刊: 计算机应用
• 学科: 工学
• 关键词: 有向无环图 k步可达性查询 hop点最短路径索引 双向互逆拓扑索引 双向遍历
• 年，卷（期）: 2020,（2）
• 所属期刊栏目: 第36届CCF中国数据库学术会议(NDBC2019)
• 页码范围: 426-433
• 页数: 8页
• 分类号: TP311
• 字数: 9983字
• 语种: 中文
• DOI: 10.11772/j.issn.1001-9081.2019081605

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杜明	东华大学计算机科学与技术学院	23	43	4.0	5.0
2	陈子阳	上海立信会计金融学院信息管理学院	4	2	1.0	1.0
3	周军锋	东华大学计算机科学与技术学院	6	2	1.0	1.0
4	杨云	东华大学计算机科学与技术学院	2	1	1.0	1.0
5	杨安平	东华大学计算机科学与技术学院	2	1	1.0	1.0