Shortest Distance Queries on Terrain Surface

PhD Thesis Proposal Defence


Title: "Shortest Distance Queries on Terrain Surface"

by

Mr. Junqiu WEI


Abstract:

Due to the advance of the geo-spatial positioning and the computer graphics 
technology, digital terrain data become more and more popular nowadays. Query 
processing on terrain data has attracted considerable attention from both the 
academic community and the industry community.

One fundamental and important query is the shortest distance query and many 
other applications such as proximity queries (including nearest neighbor 
queries and range queries), 3D object feature vector construction and 3D object 
data mining are built based on the result of the shortest distance query. In 
this thesis, we study the shortest distance query which is to find the shortest 
distance between a point-of-interest and another point-of-interest on the 
surface of the terrain due to a variety of applications. As observed by 
existing studies, computing the exact shortest distance is very expensive. Some 
existing studies proposed e-approximate distance oracles where e is a 
non-negative real number and is an error parameter. However, the best-known 
algorithm has a large oracle construction time, a large oracle size and a large 
distance query time.

Motivated by this, we propose a novel e-approximate distance oracle called the 
Space Efficient distance oracle (SE) which has a small oracle construction 
time, a small oracle size and a small distance query time due to its 
compactness storing concise information about pairwise distances between any 
two points-of-interest. Our experimental results show that the oracle 
construction time, the oracle size and the distance query time of SE are up to 
two orders of magnitude, up to 3 orders of magnitude and up to 5 orders of 
magnitude faster than the best-known algorithm.


Date:			Tuesday, 6 February 2018

Time:                  	10:00am - 12:00noon

Venue:                  Room 3494
                         (lifts 25/26)

Committee Members:	Dr. Raymond Wong (Supervisor)
 			Prof. Dik-Lun Lee (Chairperson)
 			Prof. Frederick Lochovsky
 			Prof. Dimitris Papadias


**** ALL are Welcome ****