On Boosting Spatial Data Management with Efficient Indexing Structures

Speaker: Dr. Victor WEI
         Department of Computing
         The Hong Kong Polytechnic University

Title:   "On Boosting Spatial Data Management with Efficient Indexing 

Date:    Friday, 7 January 2022

Time:    10:00am - 11:00am (Hong Kong Local Time)

Zoom link:

Meeting ID:     928 308 079
Passcode:       20220107


Due to the advance of geo-positioning technologies, spatial data including 
spatial trajectories, 3D terrain data and spatial networks, etc. becomes 
more and more popular and draws a lot of attention from both academia and 
industry. As such, the query processing in spatial data management becomes 
more and more important and finds wide applications in urban computing, 
smart cities, autonomous driving, etc.

One of the fundamental queries in spatial data management is the shortest 
distance and shortest path query. In this talk, I will present two 
research works on this fundamental query which boosts the query processing 
with efficient indexing structures. The first work tackles an emerging 
type of spatial data, namely 3D terrain surface. It proposes an indexing 
structure, namely a Distance Oracle, to efficiently index the pairwise 
distances among a set of points-of-interest on the terrain surface. The 
oracle answers the distance query by using a small set of pre-computed 
distances and utilizes a tree structure to boost the search on the 
pre-computed distances. Besides, it guarantees the error is bounded by a 
user-specified error parameter. The second one studies the dynamic road 
networks where the traffic information changes over time. It proposes an 
efficient indexing structure for the shortest distance and path queries on 
dynamic road networks. The indexing structure is based on auxiliary edges 
introduced to the network, namely shortcuts, which bridge distant vertices 
on the network to accelerate the query processing. In this work, we 
propose using a randomized algorithm to generate the shortcuts. As such, 
we obtain that it has small space consumption and query time and it could 
be updated efficiently in the perspective of both theory and practice.


Victor Junqiu Wei obtained his PhD degree from the Department of Computer 
Science and Engineering, the Hong Kong University of Science and 
Technology in 2018. From March 2018 to May 2018, he was a visiting student 
of Prof. Hanan Samet and Prof. David Mount at University of Maryland in 
the US. He obtained his bachelor degree from Nanjing University in 2013. 
He is currently working as a research assistant professor in the Hong Kong 
Polytechnic University (jointly Appointed by Department of Computing and 
Research Institute for Artificial Intelligence). Prior to this, he was an 
AI Researcher in Huawei Noah's Ark Lab. His research interests span 
spatial data management, graph data analytics, random sampling and deep 
neural networks. He received many honors and awards including the 
nomination of the Best Paper Award of SIGMOD 2020, Potentially High-Value 
Patent Award of Huawei, Future Star Award of Huawei, etc.