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

CREATORXiaojun Dong, Andy Li, Yan Gu, Yihan Sun
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE88 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-16488

Browse the full library · About the Tower of Babel