DU Ming1, ZHENG Kaiwen1, CHEN Ziyang2, ZHOU Junfeng1
1. College of Computer Science and Technology, Dong Hua University, Shanghai 201620, China; 2. School of Information Management, Shanghai Lixin University of Accounting and Finance, Shanghai 201620, China
Abstract：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.
2020, Vol. 60 
