CSE Seminar: Efficient Shortest Path Processing in Dynamic Road Networks

Presenter: Mengxuan Zhang, Postdoc Research Associate, Iowa State University

Description: Shortest path query processing is the fundamental operation for the app-based/ in-car  navigation services and the building block of various applications. Even though this query has been extensively studied in the last decades, it is far from enough, for the real-life road network applications, which have two characteristics: (1) a huge number of queries are  submitted to the servers simultaneously; (2) the traffic in road network keeps evolving all  the time. However, the existing algorithms can either adapt to dynamics naturally or  process the query efficiently. Therefore, we study how to process shortest path query  efficiently in dynamics and propose three types of methods: (1) The first solution is to process the queries by batch with index-free algorithms. The index-free algorithms can  deal with dynamics naturally while with relatively slow query processing speed; (2) The second solution is snapshot clustering with index-based algorithms, and we treat the road  network as a sequence of snapshots. The index-based algorithms can achieve high query  efficiency and support the dynamics; (3) The third solution is index maintenance. We refresh the index incrementally and efficiently in dynamics. The significance of this work is  attested by six top-tier conference and journal papers. In addition, multiple future research  directions are being explored based on the existing achievements.

Bio: Dr. Mengxuan Zhang is a postdoc research associate at Iowa State University. She obtained her Ph.D. in computer science from the University of Queensland in 2021, her M.S. degree in control theory and control engineering from Dalian University of  Technology in 2017, and her B.S. degree in automation from Wuhan University of Science  and Technology in 2014. Her research interests include spatial-temporal database  management, dynamic route planning and graph.

Hosted by: Professor Yi Zhang

Zoom link: https://ucsc.zoom.us/j/94130199818?pwd%3Ddm5oQUVhTFpjRjZoZjJRcWF2aWRkQT09&sa=D&source=calendar&ust=1676331161548665&usg=AOvVaw0qF2BSWXl2wOVrzqiwsNmV

Tuesday, February 21 at 11:00am to 12:00pm

Virtual Event

Recent Activity