TY - GEN
T1 - Path Query Processing Using Typical Snapshots in Dynamic Road Networks
AU - Zhang, Mengxuan
AU - Li, Lei
AU - Chao, Pingfu
AU - Hua, Wen
AU - Zhou, Xiaofang
N1 - Funding Information:
Acknowledgment. This research is partially supported by the Australian Research Council (DP200103650 and LP180100018).
Publisher Copyright:
© 2020, Springer Nature Switzerland AG.
PY - 2020
Y1 - 2020
N2 - The shortest path query in road network is a fundamental operation in navigation and location-based services. The existing shortest path algorithms aim at improving efficiency in the static/time-dependent environment. However, the real-life road networks are dynamic, so they can hardly meet the requirement in practice. In this paper, we aim to support the path query in dynamic road networks by identifying the typical snapshots from the snapshot sequences, building the path indexes on them, and finally processing the query with the most suitable typical snapshot. Specifically, we first use the typical OD pairs to capture the dynamic information and represent the snapshots. Then the snapshot similarity is measured by considering the shortest path error and the shortest path similarity of these OD pairs. Because the OD pair number is huge and they have different power in capturing the traffic condition, we further propose a hot region-based OD selection method that could select a small but powerful OD set. Lastly, we use the distance-based-quantile error for the query accuracy evaluation and conduct experiments in a large real-world dynamic road network to verify the effectiveness of our method compared with the state-of-the-art.
AB - The shortest path query in road network is a fundamental operation in navigation and location-based services. The existing shortest path algorithms aim at improving efficiency in the static/time-dependent environment. However, the real-life road networks are dynamic, so they can hardly meet the requirement in practice. In this paper, we aim to support the path query in dynamic road networks by identifying the typical snapshots from the snapshot sequences, building the path indexes on them, and finally processing the query with the most suitable typical snapshot. Specifically, we first use the typical OD pairs to capture the dynamic information and represent the snapshots. Then the snapshot similarity is measured by considering the shortest path error and the shortest path similarity of these OD pairs. Because the OD pair number is huge and they have different power in capturing the traffic condition, we further propose a hot region-based OD selection method that could select a small but powerful OD set. Lastly, we use the distance-based-quantile error for the query accuracy evaluation and conduct experiments in a large real-world dynamic road network to verify the effectiveness of our method compared with the state-of-the-art.
KW - Dynamic road network
KW - Shortest path
KW - Typical snapshot
UR - http://www.scopus.com/inward/record.url?scp=85092099337&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-59419-0_16
DO - 10.1007/978-3-030-59419-0_16
M3 - Conference article published in proceeding or book
AN - SCOPUS:85092099337
SN - 9783030594183
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 255
EP - 271
BT - Database Systems for Advanced Applications - 25th International Conference, DASFAA 2020, Proceedings
A2 - Nah, Yunmook
A2 - Cui, Bin
A2 - Lee, Sang-Won
A2 - Yu, Jeffrey Xu
A2 - Moon, Yang-Sae
A2 - Whang, Steven Euijong
PB - Springer Science and Business Media Deutschland GmbH
T2 - 25th International Conference on Database Systems for Advanced Applications, DASFAA 2020
Y2 - 24 September 2020 through 27 September 2020
ER -