Parallel Point-to-Point Shortest Paths and Batch Queries (SPAA '25)

Jun 20, 2025
ResearchParallel AlgorithmsGraph ProcessingSPAA

I am excited to share our work published at the 37th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2025):

Parallel Point-to-Point Shortest Paths and Batch Queries
Xiaojun Dong, Andy Li, Yan Gu, and Yihan Sun
ACM SPAA 2025, pp. 458–472.
ACM Digital Library

Motivation & Background

Computing point-to-point shortest paths is one of the most fundamental problems in graph algorithms, ubiquitous across mapping engines, social network analysis, and transportation networks. While Dijkstra’s algorithm and bidirectional search are standard sequential solutions, designing scalable parallel formulations for single-pair and batch shortest path queries without massive work overhead is challenging.

Standard parallel BFS or Delta-stepping algorithms can suffer from high synchronization costs and redundant frontier exploration when answering point-to-point queries, especially on skewed graph topologies.

Key Contributions

  1. Search Space Pruning with Thread-Level Parallelism: We devised an algorithm that enables fine-grained thread parallelism while actively pruning the search frontier. This prevents threads from traversing irrelevant branches in the graph.

  2. Batch Query Processing: We extended our design to process large batches of shortest path queries concurrently, sharing graph representations and optimizing cache hierarchy utilization.

  3. High-Performance Implementation in ParlayLib: We implemented our algorithms using ParlayLib, a C++ library designed for fast shared-memory parallel programming.

Empirical Results

We benchmarked the implementation on a 96-core server across real-world datasets including large-scale road networks, social graphs, and synthetic benchmark graphs. Our proposed algorithm achieved an average $1.92\times$ speedup over existing state-of-the-art baselines while maintaining strict theoretical work bounds.

×