An Efficiently Updatable Path Oracle for Terrain Surfaces

This is the dataset for "An Efficiently Updatable Path Oracle for Terrain Surfaces" submitted to IEEE Transactions on Knowledge and Data Engineering. For more details, please refer to our code GitHub link https://github.com/yanyinzhao/UpdatedStructureTerrainCode.

The abstract of the paper: The booming of computer graphics technology facilitates the growing use of terrain data. Notably, shortest path querying on a terrain surface is central in a range of applications and has received substantial attention from the database community. Despite this, computing the shortest paths on-the-fly on a terrain surface remains very expensive, and all existing oracle-based algorithms are only efficient when the terrain surface is fixed. They rely on large data structures that must be re-constructed from scratch when updates to the terrain surface occur, which is very time-consuming. To advance the state-of-the-art, we propose an efficiently updatable (1+epsilon)-approximate shortest path oracle for a set of Points-Of-Interests (POIs) on an updated terrain surface, and it can be easily adapted to the case if POIs are not given as input. This oracle is capable of improved performance in terms of the oracle update time, output size, and shortest path query time. Our empirical study shows that when POIs are given (resp. not given), our oracle is up to 88 times, 12 times and 3 times (resp. 15 times, 50 times and 100 times) better than the best-known oracle on terrain surfaces in terms of the oracle update time, output size and shortest path query.