典型文献
时态图最短路径查询方法
文献摘要：
最短路径查询问题已被研究多年,然而,目前已有大部分工作主要集中在普通图上,针对时态图最短路径查询的研究工作相对较少.时态图中,2个顶点之间有多条边,每条边附带有时态区间,记录着边上代表事件的发生时间和结束时间.时态图最短路径查询在城市交通路径规划、社交网络分析、通信网络挖掘等领域有着广泛的应用.由于最短时态路径的子路径不能保证是最优子结构,传统的普通图最短路径计算方法不再适用于时态图.因此提出了基于压缩转化图树(CTG-tree)索引的查询方法,该方法包含预处理和在线查询2个阶段.预处理阶段将时态图转化为普通图,提出了一种无损压缩方法将转化图压缩以减小图规模,采用层次划分技术将压缩有向图分解为若干个子图,并基于子图建立CTG-tree索引.CTG-tree中的节点保存相应子图内部分顶点之间的最短路径、孩子节点对应子图的边界点之间的最短路径、孩子节点对应子图的边界点与当前节点相应子图的边界点之间的最短路径信息.在线查询阶段基于构建的CTG-tree索引,提出了一种高效的最短路径查询方法.基于4个真实的时态图数据集实验结果表明,与现有方法相比,提出的方法具有更优的查询性能.
文献关键词：
最短路径;时态图;压缩有向图;树索引;查询方法
中图分类号：
作者姓名：
张天明;徐一恒;蔡鑫伟;范菁
作者机构：
浙江工业大学计算机科学与技术学院 杭州 310023;浙江大学计算机科学与技术学院 杭州 310013
文献出处：
引用格式：
[1]张天明;徐一恒;蔡鑫伟;范菁-.时态图最短路径查询方法)[J].计算机研究与发展,2022(02):362-375
A类：
时态图,压缩有向图
B类：
最短路径查询,查询方法,询问,顶点,多条,附带,着边,边上,上代,发生时间,城市交通,交通路,路径规划,社交网络分析,通信网络,网络挖掘,子路径,路径计算,CTG,tree,在线查询,无损压缩方法,若干个,子图,边界点,图数据,查询性能,树索引
AB值：
0.196653
相似文献
机标中图分类号，由域田数据科技根据网络公开资料自动分析生成，仅供学习研究参考。
