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
  
  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 }
  }

  [copy]
  
  
    DOI:
  10.1145/3694906.3743311    [copy]
  
    Software:
  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
  
  ACDA
   SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2025    [BibTeX]
  @inproceedings{ Ding2025New,
  title = { New Algorithms for Incremental Minimum Spanning Trees and Temporal Graph Applications (To Appear) },
  author = { Ding, Xiangyun and  Gu, Yan and  Sun, Yihan},
  booktitle = {SIAM Conference on Applied and Computational Discrete Algorithms (ACDA)},
  year = { 2025 }
  }

  [copy]
  
  
    Software:
  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!
  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 }
  }

  [copy]
  
  
    DOI:
  10.1145/3721145.3725744    [copy]
  
    Software:
  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  
• [21] Parallel k-Core Decomposition: Theory and Practice
  Youzhe Liu, Xiaojun Dong, Yan Gu, and Yihan Sun
  
  SIGMOD
   ACM Special Interest Group on Management of Data (SIGMOD), 2025    [BibTeX]
  @inproceedings{ Liu2025Parallel,
  title = { Parallel k-Core Decomposition: Theory and Practice },
  author = { Liu, Youzhe and  Dong, Xiaojun and  Gu, Yan and  Sun, Yihan},
  booktitle = {ACM Special Interest Group on Management of Data (SIGMOD)},
  year = { 2025 }
  }

  [copy]
  
  
    DOI:
  10.1145/3725332    [copy]
  
    Software:
  Parallel k-core implementation, integrated in PASGAL  [Github]
  
  ACDA
   Poster and oral presentation at the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2025
  
  HOPC
   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
  
  SIGMOD
   ACM Special Interest Group on Management of Data (SIGMOD), 2025    [BibTeX]
  @inproceedings{ Men2025Pkd-tree:,
  title = { Pkd-tree: Parallel kd-tree with Batch Updates },
  author = { Men, Ziyang and  Shen, Zheqi and  Gu, Yan and  Sun, Yihan},
  booktitle = {ACM Special Interest Group on Management of Data (SIGMOD)},
  year = { 2025 }
  }

  [copy]
  
  
    DOI:
  10.1145/3709712    [copy]
  
    Software:
  Pkd-tree: Parallel kd-tree  [Github]
  
  ACDA
   Poster and oral presentation at the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2025
  
  HOPC
   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
  
  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 }
  }

  [copy]
  
  
    DOI:
  10.1137/1.9781611978339.4    [copy]
  
    Software:
  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)!
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2024    [BibTeX]
  @inproceedings{ Ding2024Parallel,
  title = { Parallel and (Nearly) Work-Efficient Dynamic Programming },
  author = { Ding, Xiangyun and  Gu, Yan and  Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2024 }
  }

  [copy]
  
  
    Software:
  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
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2024    [BibTeX]
  @inproceedings{ Dong2024Brief,
  title = { Brief Announcement: PASGAL: Parallel And Scalable Graph Algorithm Library },
  author = { Dong, Xiaojun and  Gu, Yan and  Sun, Yihan and  Wang, Letong},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2024 }
  }

  [copy]
  
  
    DOI:
  10.1145/3626183.3660258    [copy]
  
    Software:
  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
  
  PPoPP
   ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2024    [BibTeX]
  @inproceedings{ Manohar2024ParlayANN:,
  title = { ParlayANN: Scalable and Deterministic Parallel Graph-Based Algorithms for Approximate Nearest Neighbor Search },
  author = { Manohar, Magdalen Dobson and  Shen, Zheqi and  , and  Dhulipala, Laxman and  Gu, Yan and  Simhadri, Harsha and  Sun, Yihan},
  booktitle = {ACM Symposium on Principles and Practice of Parallel Programming (PPoPP)},
  year = { 2024 }
  }

  [copy]
  
  
    DOI:
  10.1145/3627535.3638475    [copy]
  
    Software:
  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
  
  PPoPP
   ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2024    [BibTeX]
  @inproceedings{ Dong2024Parallel,
  title = { Parallel Integer Sort: Theory and Practice },
  author = { Dong, Xiaojun and  Dhulipala, Laxman and  Gu, Yan and  Sun, Yihan},
  booktitle = {ACM Symposium on Principles and Practice of Parallel Programming (PPoPP)},
  year = { 2024 }
  }

  [copy]
  
  
    DOI:
  10.1145/3627535.3638483    [copy]
  
    Software:
  DovetailSort: Parallel Integer Sort  [Github]
  
  HOPC
   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
  
  VLDB
   Proceedings of the VLDB Endowment (VLDB), 2024    [BibTeX]
  @inproceedings{ Wang2024Fast,
  title = { Fast and Space-Efficient Parallel Algorithms for Influence Maximization },
  author = { Wang, Letong and  Ding, Xiangyun and  Gu, Yan and  Sun, Yihan},
  booktitle = {Proceedings of the VLDB Endowment (VLDB)},
  year = { 2024 }
  }

  [copy]
  
  
    DOI:
  10.14778/3632093.3632104    [copy]
  
    Software:
  PaC-IM: Parallel and Compressed Influence Maximization  [Github]
  
  HOPC
   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!
  ESA
   European Symposium on Algorithms (ESA), 2023    [BibTeX]
  @inproceedings{ Ding2023Efficient,
  title = { Efficient Parallel Output-Sensitive Edit Distance },
  author = { Ding, Xiangyun and  Dong, Xiaojun and  Gu, Yan and  Liu, Youzhe and  Sun, Yihan},
  booktitle = {European Symposium on Algorithms (ESA)},
  year = { 2023 }
  }

  [copy]
  
  
    DOI:
  10.4230/LIPIcs.ESA.2023.40    [copy]
  
    Software:
  Parallel Output-Sensitive Edit Distance  [Github]
  
  HOPC
   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
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2023    [BibTeX]
  @inproceedings{ Dong2023High-Performance,
  title = { High-Performance and Flexible Parallel Algorithms for Semisort and Related Problems },
  author = { Dong, Xiaojun and  Wu, Yunshu and  Wang, Zhongqi and  Dhulipala, Laxman and  Gu, Yan and  Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2023 }
  }

  [copy]
  
  
    DOI:
  10.1145/3558481.3591071    [copy]
  
    Software:
  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
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2023    [BibTeX]
  @inproceedings{ Gu2023Parallel,
  title = { Parallel Longest Increasing Subsequence and van Emde Boas Trees },
  author = { Gu, Yan and  Men, Ziyang and  Shen, Zheqi and  Sun, Yihan and  Wan, Zijin},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2023 }
  }

  [copy]
  
  
    DOI:
  10.1145/3558481.3591069    [copy]
  
    Software:
  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
  
  SIGMOD
   ACM Special Interest Group on Management of Data (SIGMOD), 2023    [BibTeX]
  @inproceedings{ Wang2023Parallel,
  title = { Parallel Strong Connectivity Based on Faster Reachability },
  author = { Wang, Letong and  Dong, Xiaojun and  Gu, Yan and  Sun, Yihan},
  booktitle = {ACM Special Interest Group on Management of Data (SIGMOD)},
  year = { 2023 }
  }

  [copy]
  
  
    DOI:
  10.1145/3589259    [copy]
  
    Software:
  Parallel Strongly Connected Components (SCC), integrated in PASGAL  [Github]
  
  ACDA
   Poster presented at the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2023
  
  HOPC
   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!
  PPoPP
   ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2023    [BibTeX]
  @inproceedings{ Dong2023Provably,
  title = { Provably Fast and Space-Efficient Parallel Biconnectivity },
  author = { Dong, Xiaojun and  Wang, Letong and  Gu, Yan and  Sun, Yihan},
  booktitle = {ACM Symposium on Principles and Practice of Parallel Programming (PPoPP)},
  year = { 2023 }
  }

  [copy]
  
  
    DOI:
  10.1145/3572848.3577483    [copy]
  
    Software:
  Parallel Biconnected Components (BCC), integrated in PASGAL  [Github]
  
  ACDA
   Poster and oral presentation at the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2023
  
  HOPC
   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
  
  PLDI
   ACM Conference on Programming Language Design and Implementation (PLDI), 2022    [BibTeX]
  @inproceedings{ Dhulipala2022PaC-trees:,
  title = { PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections },
  author = { Dhulipala, Laxman and  Blelloch, Guy E. and  Gu, Yan and  Sun, Yihan},
  booktitle = {ACM Conference on Programming Language Design and Implementation (PLDI)},
  year = { 2022 }
  }

  [copy]
  
  
    DOI:
  10.1145/3519939.3523733    [copy]
  
    Software:
  CPAM: Compressed Parallel Augmented Maps  [Github]
  Paper   ArXiV  Code  Slides  
• [7] Joinable Parallel Balanced Binary Trees
  Guy E. Blelloch, Daniel Ferizovic, and Yihan Sun
  
  TOPC
   ACM Transactions on Parallel Computing (TOPC), 2022    [BibTeX]
  @inproceedings{ Blelloch2022Joinable,
  title = { Joinable Parallel Balanced Binary Trees },
  author = { Blelloch, Guy E. and  Ferizovic, Daniel and  Sun, Yihan},
  booktitle = {ACM Transactions on Parallel Computing (TOPC)},
  year = { 2022 }
  }

  [copy]
  
  
    DOI:
  10.1145/3512769    [copy]
  
    Software:
  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
  
  PPoPP
   ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2022    [BibTeX]
  @inproceedings{ Anderson2022POSTER:,
  title = { POSTER: The Problem-Based Benchmark Suite (PBBS), V2 },
  author = { Anderson, Daniel and  Blelloch, Guy E. and  Dhulipala, Laxman and  Manohar, Magdalen Dobson and  Sun, Yihan},
  booktitle = {ACM Symposium on Principles and Practice of Parallel Programming (PPoPP)},
  year = { 2022 }
  }

  [copy]
  
  
    DOI:
  10.1145/3503221.3508422    [copy]
  
    Software:
  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
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2021    [BibTeX]
  @inproceedings{ Dong2021Efficient,
  title = { Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths },
  author = { Dong, Xiaojun and  Gu, Yan and  Sun, Yihan and  Zhang, Yunming},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2021 }
  }

  [copy]
  
  
    DOI:
  10.1145/3409964.3461782    [copy]
  
    Software:
  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
  
  PPoPP
   ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2021    [BibTeX]
  @inproceedings{ Wei2021Constant-Time,
  title = { Constant-Time Snapshots with Applications to Concurrent Data Structures },
  author = { Wei, Yuanhao and  Ben-David, Naama and  Blelloch, Guy E. and  Fatourou, Panagiota and  Ruppert, Eric and  Sun, Yihan},
  booktitle = {ACM Symposium on Principles and Practice of Parallel Programming (PPoPP)},
  year = { 2021 }
  }

  [copy]
  
  
    DOI:
  10.1145/3437801.3441602    [copy]
  
    Software:
  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
  
  VLDB
   Proceedings of the VLDB Endowment (VLDB), 2020    [BibTeX]
  @inproceedings{ Sun2020On,
  title = { On Supporting Efficient Snapshot Isolation for Hybrid Workloads with Multi-Versioned Indexes },
  author = { Sun, Yihan and  Blelloch, Guy E. and  Lim, Wan Shen and  Pavlo, Andrew},
  booktitle = {Proceedings of the VLDB Endowment (VLDB)},
  year = { 2020 }
  }

  [copy]
  
  
    DOI:
  10.14778/3364324.3364334    [copy]
  
    Software:
  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
  
  PPoPP
   ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2018    [BibTeX]
  @inproceedings{ Sun2018PAM:,
  title = { PAM: Parallel Augmented Maps },
  author = { Sun, Yihan and  Ferizovic, Daniel and  Blelloch, Guy E.},
  booktitle = {ACM Symposium on Principles and Practice of Parallel Programming (PPoPP)},
  year = { 2018 }
  }

  [copy]
  
  
    DOI:
  10.1145/3200691.3178509    [copy]
  
    Software:
  PAM: Parallel Augmented Maps  [Github]
  Paper   ArXiV  Code  
• 2016:
  [1] Just Join for Parallel Ordered Sets
  Guy E. Blelloch, Daniel Ferizovic, and Yihan Sun
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016    [BibTeX]
  @inproceedings{ Blelloch2016Just,
  title = { Just Join for Parallel Ordered Sets },
  author = { Blelloch, Guy E. and  Ferizovic, Daniel and  Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2016 }
  }

  [copy]
  
  
    DOI:
  10.1145/2935764.2935768    [copy]
  
    Software:
  Part of the PAM library: Parallel Augmented Maps  [Github]
  Paper   ArXiV  Code