Parallel Point-to-Point Shortest Paths and Batch Queries Conference: 37th ACM Symposium on Parallelism in Algorithms and Architectures; July 28-August 1, 2025; Portland, OR, USA 37th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA ’25), July 28-August 1, 2025, Portland, OR, USA DO
Xiaojun Dong, Andy Li, Yan Gu, Yihan Sun · 2025
Read Parallel Point-to-Point Shortest Paths and Batch Queries Conference: 37th ACM Symposium on Parallelism in Algorithms and Architectures; July 28-August 1, 2025; Portland, OR, USA 37th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA ’25), July 28-August 1, 2025, Portland, OR, USA DO by Xiaojun Dong, Andy Li, Yan Gu, Yihan Sun (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-16488.txt.
Description
Xiaojun Dong and three co-authors speed up point-to-point shortest path queries on huge graphs, singly and in batches. Their system, Orionet, appeared in twenty twenty-five. Such queries power maps and network tools, and running many at once is common in practice.
The framework builds on single-source search tools and adds pruning rules. It supports early stopping, two-way search, goal-guided search, and a combined form. For batches, shared work is captured by a small query graph linking sources and targets. On fourteen test graphs, two-way search ran about three to seven times faster than two rival systems. The goal-guided pair was also several times faster. Batch tests show strong gains over plain per-query runs.
Catalog record
| CREATOR | Xiaojun Dong, Andy Li, Yan Gu, Yihan Sun |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 88 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-16488