Ultrafast Euclidean Shortest Path Computation Using Hub Labeling
Authors: Jinchun Du, Bojie Shen, Muhammad Aamir Cheema
AAAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our experimental study conducted on the widely used benchmark maps shows that our approach is typically 1-2 orders of magnitude faster than two state-of-the-art algorithms. |
| Researcher Affiliation | Academia | Faculty of Information Technology, Monash University, Melbourne, Australia {jinchun.du, bojie.shen, aamir.cheema}@monash.edu |
| Pseudocode | Yes | Algorithm 1 shows the details of how to compute vdistmin(p, hi). Algorithm 2 shows the details of our query processing algorithm. |
| Open Source Code | Yes | For reproducibility, implementation of EHL is available online4. 4https://github.com/goldi1027/EHL |
| Open Datasets | Yes | Similar to the existing studies, we conduct experiments on the widely used game map benchmarks2, described in (Sturtevant 2012a), on a total of 373 game maps (see Table 3). 2https://github.com/nathansttt/hog2 |
| Dataset Splits | No | The paper does not explicitly provide training/test/validation dataset splits with specific percentages, sample counts, or references to predefined splits. |
| Hardware Specification | Yes | We run experiments on a 3.2 GHz Intel Core i7 machine with 32 GB of RAM. |
| Software Dependencies | No | All the algorithms are implemented in C++ and complied with -O3 flag. This only mentions the programming language and a compiler flag, not specific software components with version numbers. |
| Experiment Setup | Yes | We evaluate the effect of size of the uniform grid used in our Euclidean Hub Labeling (EHL) approach by using grids where each cell is N times bigger than the base cell in each dimension. We vary N from 1 to 64 (e.g., cell sizes vary from 1x to 64x of the base cell size in each dimension)... Ablation Study : In Table 5 and Table 6, we show the effectiveness of the four pruning rules and the optimisation (e.g., by removing these one at a time) on build time, memory and query performance. |