Publications - Open-source Code Available
You can also find my publication list on Google Scholar and DBLP.
[Back to full publication list]
- 2025:[24] Parallel Point-to-Point Shortest Paths and Batch Queries (To Appear)
Xiaojun Dong, Andy Li, Yan Gu, and Yihan Sun
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2025DOI:10.1145/3694906.3743311Software:Orionet: Parallel Single and Batch PPSP [Github]
Paper ArXiV Code - [23]
New Algorithms for Incremental Minimum Spanning Trees and Temporal Graph Applications (To Appear)
Xiangyun Ding, Yan Gu, and Yihan Sun
SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2025Software:AM-tree: Anti-Monoply tree for incremental MST and temporal connectivity [Github]
Paper Code - [22]
Parallel Contraction Hierarchies Can Be Efficient and Scalable
Zijin Wan, Xiaojun Dong, Letong Wang, Enzuo Zhu, Yan Gu, and Yihan Sun🏆 Best Paper Finalist!International Conference on Supercomputing (ICS), 2025DOI:10.1145/3721145.3725744Software:SPoCH: Scalable Parallelization of Contraction Hierarchies [Github]
Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2025
Paper ArXiV Code Slides - [21]
Parallel k-Core Decomposition: Theory and Practice
Youzhe Liu, Xiaojun Dong, Yan Gu, and Yihan Sun
ACM Special Interest Group on Management of Data (SIGMOD), 2025DOI:10.1145/3725332Software:Parallel k-core implementation, integrated in PASGAL [Github]
Poster and oral presentation at the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2025
Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2025
Paper ArXiV Code Slides - [20]
Pkd-tree: Parallel kd-tree with Batch Updates
Ziyang Men, Zheqi Shen, Yan Gu, and Yihan Sun
ACM Special Interest Group on Management of Data (SIGMOD), 2025DOI:10.1145/3709712Software:Pkd-tree: Parallel kd-tree [Github]
Poster and oral presentation at the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2025
Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2025
Paper ArXiV Code Slides Poster - [19]
Parallel Cluster-BFS and Applications to Shortest Paths
Letong Wang, Guy E. Blelloch, Yan Gu, and Yihan Sun
Algorithm Engineering and Experiments (ALENEX), 2025DOI:10.1137/1.9781611978339.4Software:CBFS: Cluster Breadth-First Search [Github]
Paper ArXiV Code Slides - 2024:[18] Parallel and (Nearly) Work-Efficient Dynamic Programming
Xiangyun Ding, Yan Gu, and Yihan Sun🏆 Outstanding Paper Award (Best paper finalist)!ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2024Software:Parallel Work-Efficient Dynamic Programming [Github]
Paper ArXiV Code Slides - [17]
Brief Announcement: PASGAL: Parallel And Scalable Graph Algorithm Library
Xiaojun Dong, Yan Gu, Yihan Sun, and Letong Wang
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2024DOI:10.1145/3626183.3660258Software:PASGAL: Parallel And Scalable Graph Algorithm Library [Github]
Paper ArXiV Code Slides Poster - [16]
ParlayANN: Scalable and Deterministic Parallel Graph-Based Algorithms for Approximate Nearest Neighbor Search
Magdalen Dobson Manohar, Zheqi Shen, , Laxman Dhulipala, Yan Gu, Harsha Simhadri, and Yihan Sun
ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2024DOI:10.1145/3627535.3638475Software:ParlayANN: Parallel Graph-Based Algorithms for Approximate Nearest Neighbor Search [Github]
Paper ArXiV Code - [15]
Parallel Integer Sort: Theory and Practice
Xiaojun Dong, Laxman Dhulipala, Yan Gu, and Yihan Sun
ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2024DOI:10.1145/3627535.3638483Software:DovetailSort: Parallel Integer Sort [Github]
Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2024
Paper ArXiV Code Slides Poster - [14]
Fast and Space-Efficient Parallel Algorithms for Influence Maximization
Letong Wang, Xiangyun Ding, Yan Gu, and Yihan Sun
Proceedings of the VLDB Endowment (VLDB), 2024DOI:10.14778/3632093.3632104Software:PaC-IM: Parallel and Compressed Influence Maximization [Github]
Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2024
Paper ArXiV Code Poster - 2023:[13] Efficient Parallel Output-Sensitive Edit Distance
Xiangyun Ding, Xiaojun Dong, Yan Gu, Youzhe Liu, and Yihan Sun🏆 Best Paper Award!European Symposium on Algorithms (ESA), 2023DOI:10.4230/LIPIcs.ESA.2023.40Software:Parallel Output-Sensitive Edit Distance [Github]
Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2024
Paper ArXiV Code Slides - [12]
High-Performance and Flexible Parallel Algorithms for Semisort and Related Problems
Xiaojun Dong, Yunshu Wu, Zhongqi Wang, Laxman Dhulipala, Yan Gu, and Yihan Sun
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2023DOI:10.1145/3558481.3591071Software:Parallel Semisort [Github]
Paper ArXiV Code Slides - [11]
Parallel Longest Increasing Subsequence and van Emde Boas Trees
Yan Gu, Ziyang Men, Zheqi Shen, Yihan Sun, and Zijin Wan
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2023DOI:10.1145/3558481.3591069Software:Parallel Longest Increasing Subsequence [Github]
Paper ArXiV Code Slides - [10]
Parallel Strong Connectivity Based on Faster Reachability
Letong Wang, Xiaojun Dong, Yan Gu, and Yihan Sun
ACM Special Interest Group on Management of Data (SIGMOD), 2023DOI:10.1145/3589259Software:Parallel Strongly Connected Components (SCC), integrated in PASGAL [Github]
Poster presented at the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2023
Poster presented at the Highlights of Parallel Computing (HOPC@SPAA), 2023
Paper ArXiV Code Slides Poster - [9]
Provably Fast and Space-Efficient Parallel Biconnectivity
Xiaojun Dong, Letong Wang, Yan Gu, and Yihan Sun🏆 Best Paper Award!ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2023DOI:10.1145/3572848.3577483Software:Parallel Biconnected Components (BCC), integrated in PASGAL [Github]
Poster and oral presentation at the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2023
Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2023
Paper ArXiV Code Poster - 2022:[8] PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections
Laxman Dhulipala, Guy E. Blelloch, Yan Gu, and Yihan Sun
ACM Conference on Programming Language Design and Implementation (PLDI), 2022DOI:10.1145/3519939.3523733Software:CPAM: Compressed Parallel Augmented Maps [Github]
Paper ArXiV Code Slides - [7]
Joinable Parallel Balanced Binary Trees
Guy E. Blelloch, Daniel Ferizovic, and Yihan Sun
ACM Transactions on Parallel Computing (TOPC), 2022DOI:10.1145/3512769Software:PAM: Parallel Augmented Maps [Github]
Paper Code - [6]
POSTER: The Problem-Based Benchmark Suite (PBBS), V2
Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, Magdalen Dobson Manohar, and Yihan Sun
ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2022DOI:10.1145/3503221.3508422Software:PBBS: The Problem-Based Benchmark Suite [Github]
Paper Code - 2021:[5] Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths
Xiaojun Dong, Yan Gu, Yihan Sun, and Yunming Zhang
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2021DOI:10.1145/3409964.3461782Software:Rho-Stepping: Parallel single-source shortes paths, integrated in PASGAL [Github]
Paper Video ArXiV Code Slides - [4]
Constant-Time Snapshots with Applications to Concurrent Data Structures
Yuanhao Wei, Naama Ben-David, Guy E. Blelloch, Panagiota Fatourou, Eric Ruppert, and Yihan Sun
ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2021DOI:10.1145/3437801.3441602Software:VCASLib: Versioned CAS Library [Github]
Paper Video ArXiV Code - 2020:[3] On Supporting Efficient Snapshot Isolation for Hybrid Workloads with Multi-Versioned Indexes
Yihan Sun, Guy E. Blelloch, Wan Shen Lim, and Andrew Pavlo
Proceedings of the VLDB Endowment (VLDB), 2020DOI:10.14778/3364324.3364334Software:Part of the PAM library: Parallel Augmented Maps [Github]
Paper Video Code Slides - 2018:[2] PAM: Parallel Augmented Maps
Yihan Sun, Daniel Ferizovic, and Guy E. Blelloch
ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2018DOI:10.1145/3200691.3178509Software:PAM: Parallel Augmented Maps [Github]
Paper ArXiV Code - 2016:[1] Just Join for Parallel Ordered Sets
Guy E. Blelloch, Daniel Ferizovic, and Yihan Sun
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016DOI:10.1145/2935764.2935768Software:Part of the PAM library: Parallel Augmented Maps [Github]
Paper ArXiV Code