Efficient Multi-Constraint Shortest Path Query Processing in Road Network

When: Wed 31th August 2022, at 1:00 pm (GMT+10)

Speaker: Mr Ziyi Liu

Host: Dr Wen Hua

Zoom: https://uqz.zoom.us/j/89362232168

Abstract:

The Multi-Constraint Shortest Path (MCSP) problem aims to find the shortest path between two nodes in a network subject to a given constraint set. It is typically processed as a skyline path problem. However, the number of intermediate skyline paths becomes larger as the network size increases and the constraint number grows, which brings about the dramatic growth of computational cost and further makes the existing index-based methods hardly capable of obtaining the complete exact results. In this talk, we will present our index-based methods to answer three types of MCSP queries: 1) the simplest version of MCSP query with one constraint; 2) MCSP query with a fixed constraint set; 3) MCSP query with any combinations of constraints.

Bio:

Ziyi Liu is currently a PhD candidate in the UQ’s School of Information Technology and Electrical Engineering under the supervision of Dr Wen Hua and Dr Lei Li. He obtained his BSc in Applied Mathematics from Chongqing Normal University (Chongqing, China) and MSc in Computer Science from the Queensland University of Technology. His research interests are spatial database management, graph, and multi-criteria route planning.