Publications in SPAA

ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)

[Back to full publication list]

• 2025:
  [13] Optimal Batch-Dynamic kd-trees for Processing-in-Memory with Applications (To Appear)
  Yiwei Zhao, Hongbo Kang, Yan Gu*, Guy E. Blelloch, Laxman Dhulipala, Charles McGuffey, and Phillip B. Gibbons
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2025    [BibTeX]
  @inproceedings{ Zhao2025Optimal,
  title = { Optimal Batch-Dynamic kd-trees for Processing-in-Memory with Applications (To Appear) },
  author = { Zhao, Yiwei and  Kang, Hongbo and  Gu, Yan and  Blelloch, Guy E. and  Dhulipala, Laxman and  McGuffey, Charles and  Gibbons, Phillip B.},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2025 }
  }

  [copy]
  
  Paper   
• [12] 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 Library:
  Orionet: Parallel Single and Batch PPSP  [Github]
  Paper   ArXiV  Code  
• 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 Library:
  Parallel Work-Efficient Dynamic Programming  [Github]
  Paper   ArXiV  Code  Slides  
• [10] 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]
  
  
    Software Library:
  PASGAL: Parallel And Scalable Graph Algorithm Library  [Github]
  Paper   ArXiV  Code  Slides  Poster  
• [9] Optimal Parallel Algorithms for Dendrogram Computation and Single-Linkage Clustering
  Laxman Dhulipala, Xiaojun Dong*, , and Yan Gu*
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2024    [BibTeX]
  @inproceedings{ Dhulipala2024Optimal,
  title = { Optimal Parallel Algorithms for Dendrogram Computation and Single-Linkage Clustering },
  author = { Dhulipala, Laxman and  Dong, Xiaojun and  , and  Gu, Yan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2024 }
  }

  [copy]
  
  
    Software Library:
  Parallel Single-linkage Dendrogram Construction Algorithm  [Github]
  Paper   ArXiV  Code  
• 2023:
  [8] 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 Library:
  Parallel Semisort  [Github]
  Paper   ArXiV  Code  Slides  
• [7] 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 Library:
  Parallel Longest Increasing Subsequence  [Github]
  Paper   ArXiV  Code  Slides  
• 2022:
  [6] 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]
  Paper   Slides  
• [5] 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 Library:
  Parallel Dynamic Programming (DP) and greedy algorithms  [Github]
  Paper   ArXiV  Slides  
• 2021:
  [4] The Processing-in-Memory Model
  Hongbo Kang, Phillip B. Gibbons, Guy E. Blelloch, Laxman Dhulipala, Yan Gu*, and Charles McGuffey
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2021    [BibTeX]
  @inproceedings{ Kang2021The,
  title = { The Processing-in-Memory Model },
  author = { Kang, Hongbo and  Gibbons, Phillip B. and  Blelloch, Guy E. and  Dhulipala, Laxman and  Gu, Yan and  McGuffey, Charles},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2021 }
  }

  [copy]
  
  Paper   Video  
• [3] 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 Library:
  Rho-Stepping: Parallel single-source shortes paths, integrated in PASGAL  [Github]
  Paper   Video  ArXiV  Code  Slides  
• 2020:
  [2] 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]
  Paper   Video  Slides  
• [1] 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]
  Paper   Video  Slides