Research map / Learning theory and algorithms / Combinatorial and search optimization
Ultrafast Euclidean Shortest Path Computation Using Hub Labeling
Jinchun Du, Bojie Shen, Muhammad Aamir Cheema
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Project visibility-graph hub labels onto grid cells and use via-label joining | Euclidean shortest path queries · DAO, DA, BG, and SC maps | query time: typically 1-2 orders of magnitude faster | Improved |
| Use hub labeling instead of a CPD within EPS | EPS · DAO, DA, BG, and SC maps | query time: 27.40 -> 82.62; 12.62 -> 22.65; 11.53 -> 21.92; 70.99 -> 359.48 | Hurt |
| Add non-taut-region pruning (PR1) (ablation) | EHL · DAO maps, non-co-visible queries | query time: 2.18 -> 1.97 | Improved |
| Add non-taut-label pruning (PR2) (ablation) | EHL · DAO maps, non-co-visible queries | query time: 2.17 -> 1.97 | Improved |
| Add distance-bound pruning (PR3) (ablation) | EHL · DAO maps, non-co-visible queries | query time: 2.22 -> 1.97 | Improved |
| Add dead-end-label pruning (PR4) (ablation) | EHL · DAO maps, non-co-visible queries | query time: 2.05 -> 1.97 | No clear effect |
| Add lower-bound ordering and early termination (ablation) | EHL · DAO maps, non-co-visible queries | query time: 2.38 -> 1.97 | Improved |
| Increase the uniform-grid cell size | EHL · DAO, DA, BG, and SC maps | build time and memory: decrease by over 100 times and over 50 times | Improved |
| Increase the uniform-grid cell size | EHL · Less challenging queries | query time | Hurt |
| Add lower-bound optimization (OP) (ablation) | EHL · DAO maps, preprocessing | memory: 113.766 -> 136.139 | Hurt |
| Add non-taut-region pruning (PR1) (ablation) | EHL · DAO maps, preprocessing | build time: 13.282 -> 4.418 | Improved |
Closest papers by meaning
- Approximate Distance Oracle for Fault-Tolerant Geometric Spanners (AAAI 2024 · similarity 0.85)
- A machine learning approach that beats Rubik's cubes (NeurIPS 2025 · similarity 0.83)
- Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits (NeurIPS 2024 · similarity 0.82)
- Paths, Proofs, and Perfection: Developing a Human-Interpretable Proof System for Constrained Shortest Paths (AAAI 2024 · similarity 0.81)
- Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology (AAAI 2024 · similarity 0.81)
- Rectangle Search: An Anytime Beam Search (AAAI 2024 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
