Yinzhao Yan
The Hong Kong University of Science and Technology
2025年6月16日 星期一
上午 10:00-11:00
102 会议室
Performing shortest path queries on a 3D surface has gained significant attention from both industry and academia. Among different representations of a 3D surface, the most popular representations are Triangular Irregular Network, i.e., TIN, and point cloud. However, all existing algorithms for answering shortest path queries on a TIN are inefficient, and there is no existing study focusing on answering shortest path queries directly on a point cloud. In this talk, we study how to effectively calculate the shortest path passing on a TIN and a point cloud. In the case of disaster, e.g., wildfire, earthquake and snowfall, we need to effectively calculate the shortest path passing on a TIN and a point cloudfor evacuation or recusing.
In the first part of the talk, we discuss an efficient on-the-fly shortest path algorithm, that answers the shortest path between two points passing different regions on a weighted TIN, where different regions are assigned different weights. In the second part of the talk, we discuss an efficient updatable shortest path oracle, that answers the shortest path query for a set of Points-Of-Interests (POIs) on an updated TIN, where the TIN is not fixed. In the third part of the talk, we discuss an efficient shortest path oracle, that answers the shortest path query for a set of POIs on a point cloud. Then, we propose efficient algorithms for answering other proximity queries, i.e., k-Nearest Neighbor (kNN) and range query, with the assistance of our oracle. Our experimental results show that they outperform the best-known algorithms or oracles in terms of time and memory.They are useful in the case of disaster for efficient evacuation path finding.
Yinzhao Yan is a final-year PhD candidate in the Department of Computer Science and Engineering, The Hong Kong University of Science and Technology (HKUST), supervised by Prof. Raymond Chi-Wing Wong. He received BSc degree in Computer Science in Hong Kong Baptist University (HKBU) in 2020 with the first class honours and is top 2% of the class, supervised by Prof. Jiming Liu. From June 2019 to Aug 2019, he was a research intern in School of Information Studies, McGill University, in Canada, under the supervision of Prof. Benjamin Fung and Prof. William Kwok Wai Cheung. From Sep 2018 to Jan 2019, he was an exchange student in Leiden University, in the Netherlands. From June 2018 to Aug 2018, he was an intern in The University of New South Wales, in Australia. His research interest lies in spatial databases. His current focus is on finding the shortest path on 3D models efficiently. He has published papers in top-tier conferences and journals, including SIGMOD’26, SIGMOD’24, VLDB’21, TKDE’24 and MDM’24, all as the first author. He served as program committees in top-tier conferences including SIGMOD and ICDE. He served as reviewers in VLDB, TKDE, ICDM, SSTD, MDM, and SIGSPATIAL. He received the best paper award from MDM’24. He received more than 20 awards or scholarships.
