Publications - Parallel Incremental Algorithms

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

[Back to full publication list]

• 2024:
  [9] 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]
  
  
  parallelize iterative DP algorithms
  Paper   ArXiV  Code  Slides
• [8] ParlayANN: Scalable and Deterministic Parallel Graph-Based Algorithms for Approximate Nearest Neighbor Search
  Magdalen Dobson, Zheqi Shen, Guy Blelloch, Laxman Dhulipala, Yan Gu, Harsha Simhadri, and Yihan Sun
  
  PPoPP
   ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2024  [BibTeX]
  @inproceedings{ Dobson2024ParlayANN:,
  title = { ParlayANN: Scalable and Deterministic Parallel Graph-Based Algorithms for Approximate Nearest Neighbor Search },
  author = {Dobson, Magdalen and Shen, Zheqi and Blelloch, Guy 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]
  
  parallelize iterative ANNS algorithms
  Paper   ArXiV  Code  
• 2023:
  [7] 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]
  
  HOPC
   Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2024
  
  parallelize the iterative edit distance algorithm
  Paper   ArXiV  Code  Slides
• [6] 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]
  
  Parallelizing sequential algorithms for LIS
  Paper   ArXiV  Code  Slides
• 2022:
  [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]
  
  Parallelizing sequential algorithms for LIS, activity selection, Huffman tree, MIS, and Dijkstra's algorithm.
  Paper   ArXiV  Slides
• 2020:
  [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  
• [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