TY - GEN
T1 - Typical Snapshots Selection for Shortest Path Query in Dynamic Road Networks
AU - Zhang, Mengxuan
AU - Li, Lei
AU - Hua, Wen
AU - Zhou, Xiaofang
N1 - Publisher Copyright:
© 2020, Springer Nature Switzerland AG.
PY - 2020
Y1 - 2020
N2 - Finding the shortest paths in road network is an important query in our life nowadays, and various index structures are constructed to speed up the query answering. However, these indexes can hardly work in real-life scenario because the traffic condition changes dynamically, which makes the pathfinding slower than in the static environment. In order to speed up path query answering in the dynamic road network, we propose a framework to support these indexes. Firstly, we view the dynamic graph as a series of static snapshots. After that, we propose two kinds of methods to select the typical snapshots. The first kind is time-based and it only considers the temporal information. The second category is the graph representation-based, which considers more insights: edge-based that captures the road continuity, and vertex-based that reflects the region traffic fluctuation. Finally, we propose the snapshot matching to find the most similar typical snapshot for the current traffic condition and use its index to answer the query directly. Extensive experiments on real-life road network and traffic conditions validate the effectiveness of our approach.
AB - Finding the shortest paths in road network is an important query in our life nowadays, and various index structures are constructed to speed up the query answering. However, these indexes can hardly work in real-life scenario because the traffic condition changes dynamically, which makes the pathfinding slower than in the static environment. In order to speed up path query answering in the dynamic road network, we propose a framework to support these indexes. Firstly, we view the dynamic graph as a series of static snapshots. After that, we propose two kinds of methods to select the typical snapshots. The first kind is time-based and it only considers the temporal information. The second category is the graph representation-based, which considers more insights: edge-based that captures the road continuity, and vertex-based that reflects the region traffic fluctuation. Finally, we propose the snapshot matching to find the most similar typical snapshot for the current traffic condition and use its index to answer the query directly. Extensive experiments on real-life road network and traffic conditions validate the effectiveness of our approach.
KW - Dynamic road network
KW - Shortest path
KW - Snapshot selection
UR - http://www.scopus.com/inward/record.url?scp=85082298876&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-39469-1_9
DO - 10.1007/978-3-030-39469-1_9
M3 - Conference article published in proceeding or book
AN - SCOPUS:85082298876
SN - 9783030394684
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 105
EP - 120
BT - Databases Theory and Applications - 31st Australasian Database Conference, ADC 2020, Proceedings
A2 - Borovica-Gajic, Renata
A2 - Qi, Jianzhong
A2 - Wang, Weiqing
PB - Springer
T2 - 31st Australasian Database Conference, ADC 2019
Y2 - 3 February 2020 through 7 February 2020
ER -