TFP: Efficient algorithm for fastest path queries

doi:10.16511/j.cnki.qhdxxb.2020.22.007

Download: PDF(1056 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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.

Keywords temporal graph reachability query fastest path query heuristic rules

Issue Date: 17 June 2020

	Service

	E-mail this article
	E-mail Alert
	RSS
	Articles by authors

	DU Ming
	ZHENG Kaiwen
	CHEN Ziyang
	ZHOU Junfeng

Cite this article:

DU Ming,ZHENG Kaiwen,CHEN Ziyang, et al. TFP: Efficient algorithm for fastest path queries[J]. Journal of Tsinghua University(Science and Technology), 2020, 60(8): 656-663.

URL:

http://jst.tsinghuajournals.com/EN/10.16511/j.cnki.qhdxxb.2020.22.007 OR http://jst.tsinghuajournals.com/EN/Y2020/V60/I8/656

[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.