Publications - Parallel Incremental Algorithms

You can also find my publication list on Google Scholar and DBLP.

[Back to full publication list]

• 2025:
  [12] 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
  
  incremental construction for parallel contraction hierarchies
  Paper   ArXiV  Code  Slides  
• 2024:
  [11] 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]
  
  parallelize iterative DP algorithms
  Paper   ArXiV  Code  Slides  
• [10] 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
  
  Parallel CELF
  Paper   ArXiV  Code  Poster  
• 2023:
  [9] 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
  
  parallelizing iterative DP algorithms
  Paper   ArXiV  Code  Slides  
• [8] 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]
  
  Parallelizing sequential algorithms for LIS
  Paper   ArXiV  Code  Slides  
• 2022:
  [7] Parallel Cover Trees and Applications
  Yan Gu, Zachary Napier, Yihan Sun, and Letong Wang
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2022    [BibTeX]
  @inproceedings{ Gu2022Parallel,
  title = { Parallel Cover Trees and Applications },
  author = { Gu, Yan and  Napier, Zachary and  Sun, Yihan and  Wang, Letong},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2022 }
  }

  [copy]
  
  
    DOI:
  10.1145/3490148.3538581    [copy]
  
  parallelizing cover tree construction
  Paper   Slides  
• [6] Many Sequential Iterative Algorithms Can Be Parallel and (Nearly) Work-efficient
  Zheqi Shen, Zijin Wan, Yan Gu, and Yihan Sun
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2022    [BibTeX]
  @inproceedings{ Shen2022Many,
  title = { Many Sequential Iterative Algorithms Can Be Parallel and (Nearly) Work-efficient },
  author = { Shen, Zheqi and  Wan, Zijin and  Gu, Yan and  Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2022 }
  }

  [copy]
  
  
    DOI:
  10.1145/3490148.3538574    [copy]
  
    Software:
  Parallel Dynamic Programming (DP) and greedy algorithms  [Github]
  
  Parallelizing sequential algorithms for LIS, activity selection, Huffman tree, MIS, and Dijkstra's algorithm.
  Paper   ArXiV  Slides  
• 2020:
  [5] Optimal (Randomized) Parallel Algorithms in the Binary-Forking Model
  Guy E. Blelloch, Jeremy T. Fineman, Yan Gu, and Yihan Sun
  
  🏆 Best Paper Candidate!
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020    [BibTeX]
  @inproceedings{ Blelloch2020Optimal,
  title = { Optimal (Randomized) Parallel Algorithms in the Binary-Forking Model },
  author = { Blelloch, Guy E. and  Fineman, Jeremy T. and  Gu, Yan and  Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2020 }
  }

  [copy]
  
  
    DOI:
  10.1145/3350755.3400227    [copy]
  
  iterative list ranking algorithm
  Paper   Video  Slides  
• [4] Randomized Incremental Convex Hull is Highly Parallel
  Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020    [BibTeX]
  @inproceedings{ Blelloch2020Randomized,
  title = { Randomized Incremental Convex Hull is Highly Parallel },
  author = { Blelloch, Guy E. and  Gu, Yan and  Shun, Julian and  Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2020 }
  }

  [copy]
  
  
    DOI:
  10.1145/3350755.3400255    [copy]
  
  Parallel incremental algorithm for convex hull
  Paper   Video  Slides  
• [3] Parallelism in Randomized Incremental Algorithms
  Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun
  
  JACM
   Journal of the ACM (JACM), 2020    [BibTeX]
  @inproceedings{ Blelloch2020Parallelism,
  title = { Parallelism in Randomized Incremental Algorithms },
  author = { Blelloch, Guy E. and  Gu, Yan and  Shun, Julian and  Sun, Yihan},
  booktitle = {Journal of the ACM (JACM)},
  year = { 2020 }
  }

  [copy]
  
  
    DOI:
  10.1145/3402819    [copy]
  
  Parallel incremental algorithms for sorting, Delaunay triangulation, closest pair, smallest enclosing disk, SCC, LE list
  Paper   
• 2018:
  [2] Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry
  Guy E. Blelloch, Yan Gu, Yihan Sun, and Julian Shun
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2018    [BibTeX]
  @inproceedings{ Blelloch2018Parallel,
  title = { Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry },
  author = { Blelloch, Guy E. and  Gu, Yan and  Sun, Yihan and  Shun, Julian},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2018 }
  }

  [copy]
  
  
    DOI:
  10.1145/3210377.3210380    [copy]
  
  Parallel randomized incremental algorithm on Delaunay triangulation
  Paper   ArXiV  
• 2016:
  [1] Parallelism in Randomized Incremental Algorithms
  Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016    [BibTeX]
  @inproceedings{ Blelloch2016Parallelism,
  title = { Parallelism in Randomized Incremental Algorithms },
  author = { Blelloch, Guy E. and  Gu, Yan and  Shun, Julian and  Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2016 }
  }

  [copy]
  
  
    DOI:
  10.1145/2935764.2935766    [copy]
  
  Parallel randomized incremental algorithms for sorting, Delaunay triangulation, closest pair, smallest enclosing disk, SCC, LE list
  Paper   ArXiV