• 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
Advanced Search
Zhang Tianming, Xu Yiheng, Cai Xinwei, Fan Jing. A Shortest Path Query Method over Temporal Graphs[J]. Journal of Computer Research and Development, 2022, 59(2): 362-375. DOI: 10.7544/issn1000-1239.20210893
Citation: Zhang Tianming, Xu Yiheng, Cai Xinwei, Fan Jing. A Shortest Path Query Method over Temporal Graphs[J]. Journal of Computer Research and Development, 2022, 59(2): 362-375. DOI: 10.7544/issn1000-1239.20210893

A Shortest Path Query Method over Temporal Graphs

Funds: This work was supported by the National Key Research and Development Program of China (2018YFB1402802).
More Information
  • Published Date: January 31, 2022
  • Shortest path query has been extensively studied for decades of years. However, most of existing works focus on shortest path query over general graphs, a paucity of studies aim at temporal graphs, where there are multi-edges between two nodes and each edge is associated with a temporal interval, recording the start time and the end time of an event. Shortest path query over temporal graphs has a plethora of applications in urban traffic route planning, social network analysis, and communication network mining, to name but a few. Traditional shortest path algorithms on general graphs are not suitable for temporal graphs because subpaths of a shortest temporal path are not guaranteed to be the optimal substructures. Hence, in this paper, we propose a Compressed Transformed Graph tree (CTG-tree) based query method, which consists of a preprocessing stage and an online query stage. In the preprocessing stage, we transform the temporal graph into a general graph, propose a lossless compression method to reduce the scale of the transformed graph, use hierarchical partitioning technique to divide the compressed directed graph into subgraphs, and then build a CTG-tree index based on the partitioned subgraphs. The nodes of CTG-tree maintain shortest paths between some vertices in the corresponding subgraphs,save shortest paths between boundaries in the subgraphs of children nodes, and record shortest paths between boundaries of the subgraphs corresponding to the children nodes and those corresponding to the current node. In the online query stage, based on the constructed CTG-tree index, we develop an efficient shortest temporal path query method. Using four real-life temporal graphs, we experimentally demonstrate that our proposed method has the best query performance compared with the state-of-the-art methods.
  • Cited by

    Periodical cited type(6)

    1. 齐锐,彭依明,万静. 基于边缘计算的异构集群混合式资源调度方法. 电气技术与经济. 2025(01): 57-59 .
    2. 任晓旭,仇超,邓辉,戴子明,刘泽军,王晓飞. 边缘智能融合区块链:研究现状、应用及挑战. 信息与控制. 2024(01): 1-16 .
    3. 王斌,马重阳,彭博,牛莹. 基于区块链的分布式算力资源调度机制. 中国宽带. 2024(05): 139-141 .
    4. 崔佳怡,谢人超,唐琴琴. 基于生成式人工智能的算力网络自智优化研究综述. 中兴通讯技术. 2024(06): 54-62 .
    5. 夏景旋 ,申国伟 ,郭春 ,崔允贺 . USPS:面向算力资源高效协同的用户态跨协议代理系统. 计算机科学. 2023(11): 348-355 .
    6. 周旭,李琢. 面向算力网络的云边端协同调度技术. 中兴通讯技术. 2023(04): 32-37 .

    Other cited types(3)

Catalog

    Article views (477) PDF downloads (212) Cited by(9)
    Turn off MathJax
    Article Contents

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return