About Me

News - I will be joining the University of California, Riverside (UCR) as an Assistant Professor from Jan. 2020. I'm looking for self-motivated Ph.D. students. If you are interested, please contact me via email with your CV.

I am a final-year Ph.D. student in Computer Science Department at Carnegie Mellon University. I am very forturnate to be advised by Prof. Guy Blelloch. I received my Bachelor's degree in Computer Science from Tsinghua University.

My research interests include broad topics in the theory and practice of parallel computing, including algorithms, data structures, frameworks, implementations, programming tools and their applications. My work involves both designing algorithms with improved asymptotical theoretical bounds and developing efficient solutions to large-scale real-world problems.

This is the homepage of my lovely husband.

View my publication list:

    Google Scholar | DBLP | By Year

Software:

    PAM: a parallel library for balanced binary trees.     Download | Website

SELECTED RESEARCH TOPICS & PUBLICATIONS

A full list of my publications can be found here.

Parallel Tree Structures
  • I have been working on parallel and concurrent tree structures, both in theory and in practice. The tree structure is designed to be highly-parallelized, work-efficient, safe for concurrency, persistent (and functional), and also supports a full interface for commonly-used functions.
  • In particular, I developed the join-based algorithms on trees, which base all other tree algorithms on a single function join. Other than join, all tree algorithms are generic across four balancing schemes: AVL trees, red-black trees, weight-balanced trees and treaps.
  • The tree structure is implemented in a library called PAM. Along with an abstract data type called the augmented map, the tree structure is also applied to and tested in vairious applications, including computational geometry algorithms, database systems, transactional systems, multi-version concurrency control (MVCC), index searching, etc.
The PAM Library
Related Wikipedia Pages:
The join-based algorithms are also used in Hackage (the Haskell central package archive) Data.Set and Data.Map, and C-trees (a a compressed purely-functional search tree structure) in Aspen (a graph-streaming framework).
On Supporting Efficient Snapshot Isolation for Hybrid Workloads with Multi-Versioned Indexes
  • Yihan Sun, Guy E. Blelloch, Wan Shen Lim and Andrew Pavlo
  • Manuscript.
Implementing Parallel and Concurrent Tree Structures
  • Yihan Sun and Guy Blelloch
  • Tutorial, ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2019
Document
Multiversion Concurrency with Bounded Delay and Precise Garbage Collection
  • Naama Ben-David, Guy E. Blelloch, Yihan Sun and Yuanhao Wei
  • ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2019.
  • Also, arXiv:1803.08617 [cs.DC]
Paper (Conference) Full Paper (arXiv)
Parallel Range, Segment and Rectangle Queries with Augmented Maps
  • Yihan Sun and Guy E. Blelloch
  • Algorithm Engineering and Experiments (ALENEX), 2019
  • Also, ArXiv:1803.08621 [cs.CG]
Paper (Conference) Full Paper (arXiv)
PAM: Parallel Augmented Maps
  • Yihan Sun, Daniel Ferizovic and Guy Blelloch
  • ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2018
  • Also, arXiv:1612.05665 [cs.DS]
Paper (conference) Full Paper (arXiv) Code (PPoPP AE)
Just Join for Parallel Ordered Sets
  • Guy E. Blelloch, Daniel Ferizovic and Yihan Sun
  • ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016.
  • Also, arXiv:1602.02120 [cs.DS]
Paper (conference) Full Paper (arXiv)
Write-efficient Algorithms
  • I have been working on write-efficient algorithms, which means to optimize the overall (asymptotical) cost considering more expensive writes to the memory than reads. The research is motivated by the new Non-Volatile Memory (NVM) technology.
Algorithmic Building Blocks for Asymmetric Memories
  • Yan Gu, Yihan Sun and Guy E. Blelloch
  • European Symposium on Algorithms (ESA), 2018.
  • Also, arXiv:1806.10370 [cs.DS]
Paper (conference) Full Paper (arXiv)
Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry
  • Guy E. Blelloch, Yan Gu, Julian Shun and Yihan Sun
  • ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2018.
  • Also, arXiv:1805.05592 [cs.DS]
Paper (conference) Full Paper (arXiv)
Parallel Algorithms on Computational Geometry
  • I have been working on some algorithms on computational geometry, most of them in parallel. Some of them are also write-efficient. The topics include range, segment, interval, rectangle queries in low dimensions, Delaunay triangulations, closest pair, smallest enclosing disk, etc. Many of them are based on efficient parallel tree structures, and the others use a randomized incremental construction framework proposed by us.
Parallel Range, Segment and Rectangle Queries with Augmented Maps
  • Yihan Sun and Guy E. Blelloch
  • Algorithm Engineering and Experiments (ALENEX), 2019
  • ArXiv:1803.08621 [cs.CG]
Full Paper (arXiv)
Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry
  • Guy E. Blelloch, Yan Gu, Julian Shun and Yihan Sun
  • ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2018.
  • Also, arXiv:1805.05592 [cs.DS]
Paper (conference) Full Paper (arXiv)
Parallelism in Randomized Incremental Algorithms
  • Guy E. Blelloch, Yan Gu, Julian Shun and Yihan Sun
  • ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016.
Paper (conference)
Parallel Graph Algorithms
  • I have been working on many parallel graph algorithms, including single-source shortest path (SSSP) and strongly-connected component (SCC).
Parallel Shortest-paths Using Radius Stepping
  • Guy E. Blelloch, Yan Gu, Yihan Sun and Kanat Tangwongsan
  • ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016.
Paper (conference)
Parallelism in Randomized Incremental Algorithms
  • Guy E. Blelloch, Yan Gu, Julian Shun and Yihan Sun
  • ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016.
Paper (conference)
Other Topics
  • I have also been working on other interested research topics, including tree embedding, parallel sorting and semisorting, data mining on social networks, and computational biology.

Teaching

  • Guest Lecturer. MIT 6.886 (Algorithm Engineering). Spring 2019.
  • Guest Lecturer. CMU 15-859 (Algorithms in the "real world"). Spring 2018.
  • Teaching Assistant. CMU 15-859 (Algorithms in the "real world"). Spring 2018.
  • Teaching Assistant. CMU 15-451/651 (Algorithms). Spring 2017.

 

Services

Paper Review

  • Parallel Computing, Systems & Applications.
  • ESA (European Symposium on Algorithms) 2019.
  • ICALP (International Colloquium on Automata, Languages and Programming) 2019.
  • SPAA (ACM Symposium on Parallelism in Algorithms and Architectures) 2019.
  • IPDPS (IEEE International Parallel and Distributed Processing Symposium) 2019.
  • SPAA (ACM Symposium on Parallelism in Algorithms and Architectures) 2018.
  • HiPC (High Performance Computing) 2016.
  • Euro-Par (International European Conference on Parallel and Distributed Computing) 2016.
  • FUN (Fun With Algorithms) 2016.
  • JCST (Journal of Computer Science & Technology).

PC Members

  • ALENEX (Algorithm Engineering and Experiments) 2020.