Distance Oracle

[Back to full publication list]

Techniques for distance oracles, such as 2-hop distances, landmark labeling, bidirectional search, A* search, contraction, hierarchies, etc.

2025:
[4] Parallel Point-to-Point Shortest Paths and Batch Queries (To Appear)
Xiaojun Dong*, Andy Li*, Yan Gu*, and Yihan Sun*
SPAA
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2025    [BibTeX]

@inproceedings{ Dong2025Parallel,
title = { Parallel Point-to-Point Shortest Paths and Batch Queries (To Appear) },
author = { Dong, Xiaojun and Li, Andy and Gu, Yan and Sun, Yihan},
booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
year = { 2025 }
}

  DOI:
10.1145/3694906.3743311
  Software Library:
Orionet: Parallel Single and Batch PPSP  [Github]
Paper   ArXiV  Code
[3] Parallel Contraction Hierarchies Can Be Efficient and Scalable
Zijin Wan*, Xiaojun Dong*, Letong Wang*, Enzuo Zhu*, Yan Gu*, and Yihan Sun*
🏆 Best Paper Finalist!
ICS
International Conference on Supercomputing (ICS), 2025    [BibTeX]

@inproceedings{ Wan2025Parallel,
title = { Parallel Contraction Hierarchies Can Be Efficient and Scalable },
author = { Wan, Zijin and Dong, Xiaojun and Wang, Letong and Zhu, Enzuo and Gu, Yan and Sun, Yihan},
booktitle = {International Conference on Supercomputing (ICS)},
year = { 2025 }
}

  DOI:
10.1145/3721145.3725744
  Software Library:
SPoCH: Scalable Parallelization of Contraction Hierarchies  [Github]
HOPC
Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2025
Paper   ArXiV  Code  Slides
[2] Parallel Cluster-BFS and Applications to Shortest Paths
Letong Wang*, Guy E. Blelloch, Yan Gu*, and Yihan Sun*
ALENEX
Algorithm Engineering and Experiments (ALENEX), 2025    [BibTeX]

@inproceedings{ Wang2025Parallel,
title = { Parallel Cluster-BFS and Applications to Shortest Paths },
author = { Wang, Letong and Blelloch, Guy E. and Gu, Yan and Sun, Yihan},
booktitle = {Algorithm Engineering and Experiments (ALENEX)},
year = { 2025 }
}

  DOI:
10.1137/1.9781611978339.4
  Software Library:
CBFS: Cluster Breadth-First Search  [Zenodo]
Paper   ArXiV  Code  Slides
2021:
[1] The Read-Only Semi-External Model
Guy E. Blelloch, Laxman Dhulipala, Phillip B. Gibbons, Yan Gu*, Charles McGuffey, and Julian Shun
APOCS
ACM-SIAM Algorithmic Principles of Computer Systems (APOCS), 2021 [BibTeX]

@inproceedings{ Blelloch2021The,
title = { The Read-Only Semi-External Model },
author = { Blelloch, Guy E. and Dhulipala, Laxman and Gibbons, Phillip B. and Gu, Yan and McGuffey, Charles and Shun, Julian},
booktitle = {ACM-SIAM Algorithmic Principles of Computer Systems (APOCS)},
year = { 2021 }
}

Paper