An Efficiently Updatable Path Oracle for Terrain Surfaces

Citation Author(s):
Yinzhao
Yan
The Hong Kong University of Science and Technology
Raymond Chi-Wing
Wong
The Hong Kong University of Science and Technology
Christian S.
Jensen
Aalborg University
Submitted by:
Yinzhao YAN
Last updated:
Sat, 07/27/2024 - 10:10
DOI:
10.21227/7ras-ng51
Data Format:
.txt, .off
Research Article Link:
An Efficiently Updatable Path Oracle for Terrain Surfaces
Links:
Code GitHub link
License:
Creative Commons Attribution
148 Views
Categories:
Other
Keywords:
Spatial databases, query processing, shortest path query, terrain
0
0 ratings - Please login to submit your rating.
ACCESS DATASET CITE SHARE/EMBED

Abstract 

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. Our experiments show 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.

Instructions: 

The dataset are stored in "input/" folder.

The datasets are as follows, where XX could be {TJ, SC, GI, AU, LH, VS}:

- "TJpre_1058.off" (multiresolution resolution TJ pre earthquake terrain dataset with dataset size of 1058)
- "TJpost_1058.off" (multiresolution resolution TJ post earthquake terrain dataset with dataset size of 1058)
- "XXpre_500000.off" (default resolution XX pre earthquake terrain dataset with dataset size of 500000)
- "XXpost_500000.off" (default resolution XX post earthquake terrain dataset with dataset size of 500000)
- "XXpre_1002528.off" (multiresolution XX pre earthquake terrain dataset with dataset size of 1002528)
- "XXpost_1002528.off" (multiresolution XX post earthquake terrain dataset with dataset size of 1002528)
- "XXpre_1503378.off" (multiresolution XX pre earthquake terrain dataset with dataset size of 1503378)
- "XXpost_1503378.off" (multiresolution XX post earthquake terrain dataset with dataset size of 1503378)
- "XXpre_2000000.off" (multiresolution XX pre earthquake terrain dataset with dataset size of 2000000)
- "XXpost_2000000.off" (multiresolution XX post earthquake terrain dataset with dataset size of 2000000)
- "XXpre_2504322.off" (multiresolution XX pre earthquake terrain dataset with dataset size of 2504322)
- "XXpost_2504322.off" (multiresolution XX post earthquake terrain dataset with dataset size of 2504322)
- "TJpre_50_poi_on_1058.txt" (POI list with POI number of 50 on "TJpre_1058.off")
- "TJpost_50_poi_on_1058.txt" (POI list with POI number of 50 on "TJpost_1058.off")
- "XXpre_500_poi_on_500000.txt" (POI list with POI number of 500 on "XXpre_500000.off")
- "XXpost_500_poi_on_500000.txt" (POI list with POI number of 500 on "XXpost_500000.off")
- "XXpre_500_poi_on_1002528.txt" (POI list with POI number of 500 on "XXpre_1002528.off")
- "XXpost_500_poi_on_1002528.txt" (POI list with POI number of 500 on "XXpost_1002528.off")
- "XXpre_500_poi_on_1503378.txt" (POI list with POI number of 500 on "XXpre_1503378.off")
- "XXpost_500_poi_on_1503378.txt" (POI list with POI number of 500 on "XXpost_1503378.off")
- "XXpre_500_poi_on_2000000.txt" (POI list with POI number of 500 on "XXpre_2000000.off")
- "XXpost_500_poi_on_2000000.txt" (POI list with POI number of 500 on "XXpost_2000000.off")
- "XXpre_500_poi_on_2504322.txt" (POI list with POI number of 500 on "XXpre_2504322.off")
- "XXpost_500_poi_on_2504322.txt" (POI list with POI number of 500 on "XXpost_2504322.off")
- "XXpre_1000_poi_on_500000.txt" (POI list with POI number of 1000 on "XXpre_500000.off")
- "XXpost_1000_poi_on_500000.txt" (POI list with POI number of 1000 on "XXpost_500000.off")
- "XXpre_1500_poi_on_500000.txt" (POI list with POI number of 1500 on "XXpre_500000.off")
- "XXpost_1500_poi_on_500000.txt" (POI list with POI number of 1500 on "XXpost_500000.off")
- "XXpre_2000_poi_on_500000.txt" (POI list with POI number of 2000 on "XXpre_500000.off")
- "XXpost_2000_poi_on_500000.txt" (POI list with POI number of 2000 on "XXpost_500000.off")
- "XXpre_2500_poi_on_500000.txt" (POI list with POI number of 2500 on "XXpre_500000.off")
- "XXpost_2500_poi_on_500000.txt" (POI list with POI number of 2500 on "XXpost_500000.off")
- "XXpre_50_poi_on_500000.txt" (POI list with POI number of 50 on "XXpre_500000.off")
- "XXpost_50_poi_on_500000.txt" (POI list with POI number of 50 on "XXpost_500000.off")
- "XXpre_50_poi_on_1002528.txt" (POI list with POI number of 50 on "XXpre_1002528.off")
- "XXpost_50_poi_on_1002528.txt" (POI list with POI number of 50 on "XXpost_1002528.off")
- "XXpre_50_poi_on_1503378.txt" (POI list with POI number of 50 on "XXpre_1503378.off")
- "XXpost_50_poi_on_1503378.txt" (POI list with POI number of 50 on "XXpost_1503378.off")
- "XXpre_50_poi_on_2000000.txt" (POI list with POI number of 50 on "XXpre_2000000.off")
- "XXpost_50_poi_on_2000000.txt" (POI list with POI number of 50 on "XXpost_2000000.off")
- "XXpre_50_poi_on_2504322.txt" (POI list with POI number of 50 on "XXpre_2504322.off")
- "XXpost_50_poi_on_2504322.txt" (POI list with POI number of 50 on "XXpost_2504322.off")
- "XXpre_100_poi_on_500000.txt" (POI list with POI number of 100 on "XXpre_500000.off")
- "XXpost_100_poi_on_500000.txt" (POI list with POI number of 100 on "XXpost_500000.off")
- "XXpre_150_poi_on_500000.txt" (POI list with POI number of 150 on "XXpre_500000.off")
- "XXpost_150_poi_on_500000.txt" (POI list with POI number of 150 on "XXpost_500000.off")
- "XXpre_200_poi_on_500000.txt" (POI list with POI number of 200 on "XXpre_500000.off")
- "XXpost_200_poi_on_500000.txt" (POI list with POI number of 200 on "XXpost_500000.off")
- "XXpre_250_poi_on_500000.txt" (POI list with POI number of 250 on "XXpre_500000.off")
- "XXpost_250_poi_on_500000.txt" (POI list with POI number of 250 on "XXpost_500000.off")

Data Format:

For the terrain dataset, we used the .off format in the experiment. The content of the .off file is as follows:

```
OFF

vertices_num faces_num edges_num

1st_vertex_x_coord 1st_vertex_y_coord 1st_vertex_z_coord

2nd_vertex_x_coord 2nd_vertex_y_coord 2nd_vertex_z_coord

......

last_vertex_x_coord last_vertex_y_coord last_vertex_z_coord

1st_face_1st_vertex_ID 1st_face_2nd_vertex_ID 1st_face_3td_vertex_ID

2nd_face_1st_vertex_ID 2nd_face_2nd_vertex_ID 2nd_face_3td_vertex_ID

......

last_face_1st_vertex_ID last_face_2nd_vertex_ID last_face_3td_vertex_ID
```

For the POI list, we used the .txt format in the experiment. The content of the .txt file is as follows:

```
POI_num
1st_POI_index 2nd_POI_index ......
```

Funding Agency: 
DIREC – Digital Research Center Denmark, Innovation Fund Denmark & Guangzhou Fund
Grant Number: 
9142-00001B & GZSTI16EG24

Dataset Files

LOGIN TO ACCESS DATASET FILES

 

QUESTIONS?