TFP: Efficient algorithm for fastest path queries

DU Ming; ZHENG Kaiwen; CHEN Ziyang; ZHOU Junfeng

doi:10.16511/j.cnki.qhdxxb.2020.22.007

PDF(1056 KB)

Journal of Tsinghua University(Science and Technology) ›› 2020, Vol. 60 ›› Issue (8) : 656-663. DOI: 10.16511/j.cnki.qhdxxb.2020.22.007

SPECIALSECTION: DATABASE

TFP: Efficient algorithm for fastest path queries

{{article.zuoZhe_EN}}

Author information +

History +

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.

Key words

temporal graph / reachability query / fastest path query / heuristic rules

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations

DU Ming, ZHENG Kaiwen, CHEN Ziyang, ZHOU Junfeng. TFP: Efficient algorithm for fastest path queries[J]. Journal of Tsinghua University(Science and Technology). 2020, 60(8): 656-663 https://doi.org/10.16511/j.cnki.qhdxxb.2020.22.007

References

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