AI Paper Atlas

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

AAAI 2023 · Learning theory and algorithms › Combinatorial and search optimization · approach: Globally optimal geometric optimization · 4 citations (OpenAlex)

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 changedWhereMeasuredEffect
Project visibility-graph hub labels onto grid cells and use via-label joiningEuclidean shortest path queries · DAO, DA, BG, and SC mapsquery time: typically 1-2 orders of magnitude fasterImproved
Use hub labeling instead of a CPD within EPSEPS · DAO, DA, BG, and SC mapsquery time: 27.40 -> 82.62; 12.62 -> 22.65; 11.53 -> 21.92; 70.99 -> 359.48Hurt
Add non-taut-region pruning (PR1) (ablation)EHL · DAO maps, non-co-visible queriesquery time: 2.18 -> 1.97Improved
Add non-taut-label pruning (PR2) (ablation)EHL · DAO maps, non-co-visible queriesquery time: 2.17 -> 1.97Improved
Add distance-bound pruning (PR3) (ablation)EHL · DAO maps, non-co-visible queriesquery time: 2.22 -> 1.97Improved
Add dead-end-label pruning (PR4) (ablation)EHL · DAO maps, non-co-visible queriesquery time: 2.05 -> 1.97No clear effect
Add lower-bound ordering and early termination (ablation)EHL · DAO maps, non-co-visible queriesquery time: 2.38 -> 1.97Improved
Increase the uniform-grid cell sizeEHL · DAO, DA, BG, and SC mapsbuild time and memory: decrease by over 100 times and over 50 timesImproved
Increase the uniform-grid cell sizeEHL · Less challenging queriesquery timeHurt
Add lower-bound optimization (OP) (ablation)EHL · DAO maps, preprocessingmemory: 113.766 -> 136.139Hurt
Add non-taut-region pruning (PR1) (ablation)EHL · DAO maps, preprocessingbuild time: 13.282 -> 4.418Improved

Closest papers by meaning

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy