TFP:高效的最快路径查询处理方法

作     者：杜明 郑凯文 陈子阳 周军锋 DU Ming;ZHENG Kaiwen;CHEN Ziyang;ZHOU Junfeng

作者机构：东华大学计算机科学与技术学院上海201620 上海立信会计金融学院信息管理学院上海201620 

出 版 物：《清华大学学报（自然科学版）》 (Journal of Tsinghua University(Science and Technology))

年 卷 期：2020年第60卷第8期

页      面：656-663页

核心收录：

学科分类：0810[工学-信息与通信工程] 08[工学] 0805[工学-材料科学与工程（可授工学、理学学位）] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 081202[工学-计算机软件与理论] 

基　　金：国家重点研发计划(2017YFB0309800) 国家自然科学基金项目(61472339,61873337)。 

主　　题：时态图 可达性查询 最快路径查询 启发式规则 

摘      要：给定时态图,最快路径查询可以得到两点之间用时最短的路径对应的时间跨度。高效回答最快路径查询可有效提升系统的易用性,增强用户黏度。然而,现有方法在处理时态图上的最快路径查询时,因其处理策略造成大量冗余操作,查询处理效率不高。该文提出3个启发式规则用于减少冗余计算,并给出了合理性证明。基于3个启发式规则,提出了一种高效的最快路径通用查询算法。该方法在多个数据集上比原有方法减少了5~8倍的可达性查询调用,显著减少了冗余计算,具有更高的查询处理效率。