![]() |
|
I'm giving the talk for paper "Parallel In-Place Algorithms: Theory and Practice" at APOCS 2021. You can find the link to the full version of this talk here:
I'm teaching CS CS 142: Algorithms Engineering (how to write faster code) in Winter 2021.
I'm looking for self-motivated students. If you are interested in working with me, or want me to write you a letter, please read this first.
I am an Assistant Professor at the University of California, Riverside (UCR) from Jan. 2020.
I was a postdoc associate at MIT CSAIL in 2019, working with Julian Shun. Before that, I finished my PhD at Carnegie Mellon University, advised by Guy Blelloch. Prior to that, I received my Bachelor degree in Computer Science at Tsinghua University in 2012. My personal webpages are also available on [dblp] and [Google Scholar]. You can find my [CV] here.
My current research interest is design efficient (usually parallel) algorithms for large-scale data with good performance in practice.
This is the link to my lovely wife's homepage.
Ph.D. Thesis
Selected Publications
Papers on this page are categorized in different topics. Paper list in reverse chronological order can be found here.
Algorithm papers
Parallel Algorithms
These papers developed efficient parallel algorithms for fundamental problems or parallel primitives (e.g. sorting, shortest-paths, convex hull, Delauney triangulation, SCC, random permutation, list/tree contraction). All of these new algorithms are highly practical, and with better or matching bounds comparing to previous theoretical approaches.
Parallel In-Place Algorithms: Theory and Practice.
Yan Gu, Omar Obeya, and Julian Shun.
ACM-SIAM Algorithmic Principles of Computer Systems (APoCS), 2021.
Optimal Parallel Algorithms in the Binary-Forking Model.
Guy E. Blelloch, Jeremy T. Fineman, Yan Gu, and Yihan Sun.
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020.
Randomized Incremental Convex Hull is Highly Parallel.
Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun.
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020.
Improved Parallel Cache-Oblivious Algorithms for Dynamic Programming.
Guy Blelloch and Yan Gu.
ACM-SIAM Algorithmic Principles of Computer Systems (APoCS), 2020.
Theoretically-Efficient and Practical Parallel DBSCAN.
Yiqiu Wang, Yan Gu, and Julian Shun.
ACM International Conference on Management of Data (SIGMOD), 2020.
Parallelism in Randomized Incremental Algorithms.
Guy Blelloch, Yan Gu, Julian Shun and Yihan Sun.
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016.
Parallel Shortest-Paths Using Radius Stepping.
Guy Blelloch, Yan Gu, Yihan Sun and Kanat Tangwongsan.
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016.
A Top-Down Parallel Semisort.
Yan Gu, Julian Shun, Yihan Sun and Guy Blelloch.
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2015.
Sequential Random Permutation, List Contraction and Tree Contraction are Highly Parallel.
Julian Shun, Yan Gu, Guy Blelloch, Jeremy T. Fineman and Phillip B. Gibbons.
ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 431-448, 2015.
Algorithms for New Architecture
These papers tried to understand and develop efficient algorithms for the upcoming non-volatile main-memory (NVM). This includes modified computational models, new algorithms, new techniques to support efficient computation, etc.
The Read-Only Semi-External Model.
Guy E. Blelloch, Laxman Dhulipala, Phillip B. Gibbons, Yan Gu, Charlie McGuffey, and Julian Shun.
ACM-SIAM Algorithmic Principles of Computer Systems (APoCS), 2021.
Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs.
Laxman Dhulipala, Charlie McGuffey, Hongbo Kang, Yan Gu, Guy E. Blelloch, Phillip B. Gibbons, and Julian Shun.
Processings of the VLDB Endowment 13(9), 2020.
Algorithmic Building Blocks for Asymmetric Memories.
Yan Gu, Yihan Sun and Guy Blelloch.
European Symposium on Algorithms (ESA), 2018.
Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry.
Guy Blelloch, Yan Gu, Julian Shun, and Yihan Sun.
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2018.
[Conference version] [Full version]
The Parallel Persistent Memory Model.
Guy Blelloch, Phillip B. Gibbons, Yan Gu, Charles McGuffey and Julian Shun.
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2018.
[Conference version] [Full version]
Implicit Decomposition for Write-Efficient Connectivity Algorithms.
Naama Ben-David, Yan Gu, Guy Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Charles McGuffey and Julian Shun.
IEEE International Parallel & Distributed Processing Symposium (IPDPS), 2018.
[Conference version] [Full version]
Parallel Algorithms with Asymmetric Read and Write Costs.
Naama Ben-David, Yan Gu, Guy Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Charles McGuffey and Julian Shun.
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016.
Efficient Algorithms with Asymmetric Read and Write Costs.
Guy Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, and Julian Shun.
European Symposium on Algorithms (ESA), 2016.
[Conference version] [arXiv version]
Sorting with Asymmetric Read and Write Costs.
Guy Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, and Julian Shun.
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2015.
[Conference version] [arXiv version](<-read this)
Miscellaneous Topics
This is a random sample of topics that I occasionally looked into. They are standard sequential algorithms with the goal to minimize the time complexity.
Efficient Construction of Probabilistic Tree Embeddings.
Guy Blelloch, Yan Gu, and Yihan Sun.
International Colloquium on Automata, Languages, and Programming (ICALP), 2017.
Algorithms on Minimizing the Maximum Sensor Movement for Barrier Coverage of a Linear Domain.
Danny Z. Chen, Yan Gu, Jian Li and Haitao Wang.
SWAT 2012. Discrete & Computational Geometry, 2013, 50(2), pp. 374-408.
Graphics papers
I spent most of my time from 2010 to 2014 on computer graphics research (most of the algorithm papers are done starting from 2015).
BVH Construction
These papers discussed some interesting algorithmic improvements either to accelerate the construction or to improve the quality of the bounding volume hierarchy, which is one of the most commonly-used data structure in computer graphics. All these papers improved the state-of-the-art (or at publish time) techniques much.
Ray Specialized BVH Contraction.
Yan Gu, Yong He and Guy Blelloch.
Pacific Graphics 2015. Computer Graphics Forum 34(7), 309-318.
[Conference version] [Full version](<-read this) [Experiments]
Efficient BVH Construction via Approximate Agglomerative Clustering.
Yan Gu, Yong He, Kayvon Fatahalian and Guy Blelloch.
High Performance Graphics 2013, pp. 81-88.
[Project Page] [BibTex] [Paper] [Code]
Miscellaneous Topics
This is another random sample of the topics I worked on during my undergrad and guaduate time, including works on geometry modeling and processing, image processing, and architectual and compiling considerations on GPU rendering.
Extending the Graphics Pipeline with Adaptive, Multi-Rate Shading.
Yong He, Yan Gu, and Kayvon Fatahalian.
SIGGRAPH 2014. ACM Trans. Graph. 33, 4, Article 142 (2014).
[Project Page] [Paper] [Video]
Mixed-Domain Edge-Aware Image Manipulation.
Xian-Ying Li, Yan Gu, Shi-Min Hu, and Ralph R. Martin.
IEEE Transactions on Image Processing (TIP), 2013, 22(5), 1915-1925.
[Project Page] [BibTex] [Paper] [Code]
A Geometric Study of V-style Pop-ups: Theories and Algorithms.
Xian-Ying Li, Tao Ju, Yan Gu, and Shi-Min Hu.
SIGGRAPH 2011. ACM Transactions on Graphics , 30(4): article 98.
[Project Page] [BibTex] [34.3M Paper] [1.8M Paper] [8.9M Video] [13.9M Slides]
Collaborators
You can find my collaborators with the following links.
Naama Ben-David, Guy E. Blelloch, Danny Z. Chen, Laxman Dhulipala, Kayvon Fatahalian, Jeremy T. Fineman, Phillip B. Gibbons, Yong He, Shi-Min Hu, Tao Ju, Jian Li, Xian-Ying Li, Ralph R. Martin, Charles McGuffey, Julian Shun, Yihan Sun, Kanat Tangwongsan, Haitao Wang, Yiqiu Wang.
Teaching
CS 218: Design and Analysis of Algorithms (Spring 2021)
CS 142: Algorithms Engineering (Winter 2021)
CS 141: Intermediate Data Structures and Algorithms (Fall 2020)
CS 260: Algorithm Engineering (aka. How to Write Fast Code) (Spring 2020)
Services
Publicity chair of ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2019-present
Program Committee:
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) 2019, 2020
IEEE International Parallel & Distributed Processing Symposium (IPDPS) 2019, 2020
ACM-SIAM Algorithmic Principles of Computer Systems (APoCS) 2020
Workshop on Advances in Parallel and Distributed Computational Models (APDCM) in IPDPS 2019
Big Graph Processing (BGP) in ICDCS 2017
Reviewer of SPAA, SODA, STOC, ICALP, ESA, IPDPS, Euro-Par, ALENEX, SIGMETRIC, APOCS, HiPC, CANDAR, SIGGRAPH, Eurographics, Pacific Graphics, FUN with Algorithms.
Reviewer of ACM Transaction on Parallel Computing (TOPC), Parallel Processing Letters (PPL), Transactions on Knowledge and Data Engineering (TKDE), International Journal of Parallel Programming, PeerJ Computer Science, Journal of Experimental Algorithmics, Information Processing Letters, TVCG (IEEE Transactions on Visualization and Computer Graphics), CAG (Computers & Graphics), JCGT (Journal of Computer Graphics Techniques), the Visual Computer, JOCO (Journal of Combinatorial Optimization), Transactions on Computers, Astronomy and Computing.
Teaching assistant for 15-418/618: Parallel Computer Architecture and Programming (Summer 17).
Teaching assistant for 15-853: Algorithms in the "Real World" (Fall 15).
Teaching assistant for 15-295: Competition Programming and Problem Solving(Fall 13, Spring 14, Fall 14, Spring 15), co-coach for CMU ACM/ICPC team in 2013-2015.
Page view since Sep 23, 2018.