给定时态图，最快路径查询可以得到两点之间用时最短的路径对应的时间跨度。高效回答最快路径查询可有效提升系统的易用性，增强用户黏度。然而，现有方法在处理时态图上的最快路径查询时，因其处理策略造成大量冗余操作，查询处理效率不高。该文提出3个启发式规则用于减少冗余计算，并给出了合理性证明。基于3个启发式规则，提出了一种高效的最快路径通用查询算法。该方法在多个数据集上比原有方法减少了5~8倍的可达性查询调用，显著减少了冗余计算，具有更高的查询处理效率。
The fastest path query returns the time span of the shortest path between two vertices in a temporal graph. Efficient responses to a fastest path query effectively improve system use and enhance user desire to continue using the system. However, existing fastest path query methods on temporal graphs have many redundant operations in their processing strategies, so they are not very efficient. Three heuristic rules are presented here to reduce the number of redundant computations with verification of their effectiveness. These three heuristic rules are then integrated into an efficient universal query algorithm to find the fastest path. This method reduces the query invocation reachability 5-8 fold on various data sets compared with the original method by significantly reducing redundant computations for higher query processing efficiencies.
[1] KOSSINETS G, KLEINBERG J, WATTS D. The structure of information pathways in a social communication network[C]//Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Las Vegas, USA, 2008:435-443.
[2] TANG J, SCELLATO S, MUSOLESI M, et al. Small-world behavior in time-varying graphs[J]. Physical Review E, 2010, 81(2):055101.
[3] WU H H, HUANG Y Z, CHENG J, et al. Reachability and time-based path queries in temporal graphs[C]//Proceedings of the 32nd International Conference on Data Engineering. Helsinki, Finland, 2016:145-156.
[4] WU H H, CHENG J, HUANG S L, et al. Path problems in temporal graphs[J]. Proceedings of the VLDB Endowment, 2014, 7(9):721-732.
[5] XUAN B B, FERREIRA A, JARRY A. Computing shortest, fastest, and foremost journeys in dynamic networks[J]. International Journal of Foundations of Computer Science, 2003, 14(2):267-285.
[6] WANG S B, LIN W Q, YANG Y, et al. Efficient route planning on public transportation networks:A labelling approach[C]//Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. Melbourne, Australia, 2015:967-982.
[7] YANO Y, AKIBA T, IWATA Y, et al. Fast and scalable reachability queries on graphs by pruned labeling with landmarks and paths[C]//Proceedings of the 22nd ACM International Conference on Information & Knowledge Management. San Francisco, USA, 2013:1601-1606.
[8] CHENG J, HUANG S L, WU H H, et al. TF-Label:A topological-folding labeling scheme for reachability querying in a large graph[C]//Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. New York, USA, 2013:193-204.
[9] JIN R M, WANG G. Simple, fast, and scalable reachability oracle[J]. Proceedings of the VLDB Endowment, 2013, 6(14):1978-1989.
[10] YILDIRIM H, CHAOJI V, ZAKI M J. GRAIL:Scalable reachability index for large graphs[J]. Proceedings of the VLDB Endowment, 2010, 3(1-2):276-284.
[11] WEI H, YU J X, LU C, et al. Reachability querying:An independent permutation labeling approach[J]. The VLDB Journal, 2018, 27(1):1-26.
[12] VELOSO R R, CERF L, MEIRA W JR, et al. Reachability queries in very large graphs:A fast refined online search approach[C]//Proceedings of the 17th International Conference on Extending Database Technology (EDBT). Athens, Greece, 2014:511-522.
[13] SEUFERT S, ANAND A, BEDATHUR S, et al. FERRARI:Flexible and efficient reachability range assignment for graph indexing[C]//Proceedings of the 29th International Conference on Data Engineering. Brisbane, Australia, 2013:1009-1020.
