时态图最短路径查询方法

作     者：张天明 徐一恒 蔡鑫伟 范菁 Zhang Tianming;Xu Yiheng;Cai Xinwei;Fan Jing

作者机构：浙江工业大学计算机科学与技术学院杭州310023 浙江大学计算机科学与技术学院杭州310013 

出 版 物：《计算机研究与发展》 (Journal of Computer Research and Development)

年 卷 期：2022年第59卷第2期

页      面：362-375页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 0903[农学-农业资源与环境] 0901[农学-作物学] 0701[理学-数学] 

基　　金：国家重点研发计划项目(2018YFB1402802)。 

主　　题：最短路径 时态图 压缩有向图 树索引 查询方法 

摘      要：最短路径查询问题已被研究多年,然而,目前已有大部分工作主要集中在普通图上,针对时态图最短路径查询的研究工作相对较少.时态图中,2个顶点之间有多条边,每条边附带有时态区间,记录着边上代表事件的发生时间和结束时间.时态图最短路径查询在城市交通路径规划、社交网络分析、通信网络挖掘等领域有着广泛的应用.由于最短时态路径的子路径不能保证是最优子结构,传统的普通图最短路径计算方法不再适用于时态图.因此提出了基于压缩转化图树(CTG-tree)索引的查询方法,该方法包含预处理和在线查询2个阶段.预处理阶段将时态图转化为普通图,提出了一种无损压缩方法将转化图压缩以减小图规模,采用层次划分技术将压缩有向图分解为若干个子图,并基于子图建立CTG-tree索引.CTG-tree中的节点保存相应子图内部分顶点之间的最短路径、孩子节点对应子图的边界点之间的最短路径、孩子节点对应子图的边界点与当前节点相应子图的边界点之间的最短路径信息.在线查询阶段基于构建的CTG-tree索引,提出了一种高效的最短路径查询方法.基于4个真实的时态图数据集实验结果表明,与现有方法相比,提出的方法具有更优的查询性能.