About Me

I am on the academic job market this year.

Research Statement | Teaching Statement | CV

I am currently a 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 has focued on both designing algorithms with improved asymptotical theoretical bounds and developing efficient solutions to large-scale real-world problems.

My thesis is on parallel and concurrent tree structures. My thesis proposal document can be found here.

View my publication list:

Google Scholar | DBLP | By Topic | By Year

News

* I will give a tutorial on Parallel and Concurrent Tree Structures in PPoPP 2019.

* I will be presenting our paper on Parallel Range, Segment and Rectangle Queries with Augmented Maps at ALENEX 2019.

* I gave a talk at CMU DB seminar. [Abstract]

* I participated in the Rising Stars at MIT, an academic career workshop for women in EECS.

* I gave a talk at MIT on October 31. [Abstract]

RESEARCH & SELECTED PUBLICATIONS

For certain papers, the authors are listed alphabetically, following the convention in mathematics and theoretical computer science, and others are listed by contribution.

Papers listed here are categorized by topics. 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 memories, multi-version concurrency control (MVCC), index searching, and so on.
The PAM Library
Related Wikipedia Pages:
My thesis proposal document: proposal
The join-based algorithms are also used in Hackage (the Haskell central package archive) Data.Set and Data.Map.
On Supporting Efficient Snapshot Isolation for Hybrid Workloads with Multi-Versioned Indexes
  • Yihan Sun, Guy E. Blelloch, Andrew Pavlo and Wanshen Lim
  • Manuscript.
Efficient Single Writer Concurrency
Full Paper (arXiv)
Parallel Range, Segment and Rectangle Queries with Augmented Maps
  • Yihan Sun and Guy E. Blelloch
  • Algorithm Engineering and Experiments (ALENEX), 2019
  • To appear.
  • Also, ArXiv:1803.08621 [cs.CG]
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 (lexicographical order)
  • 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 (lexicographical order)
  • 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 many 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, and so on. 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
  • To appear.
  • 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 (lexicographical order)
  • 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
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). I also have worked on sequential graph algorithms, including graph embedding, network alignment on biological graphs, and social network analysis, which will be classified to later categories.
Parallel Shortest-paths Using Radius Stepping
Paper (conference)
Parallelism in Randomized Incremental Algorithms
Paper (conference)
Miscellaneous Algorithms
  • I have been working on other topics of algorithms.
Efficient Construction of Probabilistic Tree Embeddings
  • Guy E. Blelloch, Yan Gu and Yihan Sun (lexicographical order)
  • International Colloquium on Automata, Languages, and Programming (ICALP), 2017.
  • Also, arXiv:1605.04651 [cs.DS]
Full Paper (arXiv)
A Top-down Parallel Semisort
  • Yan Gu, Julian Shun and Yihan Sun and Guy E. Blelloch
  • ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2015.
Paper (conference) Slides
Computational Biology
  • I have been working on computational biology, especially protein-protein network aligning algorithms.
Simultaneous Optimization of Both Node and Edge Conservation in Network Alignment via WAVE
  • Yihan Sun, Joseph Crawford, Jie Tang and Tijana Milenkovic
  • Workshop on Algorithms in Bioinformatics (WABI), 2015.
  • Also, arXiv:1410.3301 [q-bio.MN]
Paper (WABI) Full Paper (arXiv)
Fair Evaluation of Global Network Aligners
  • Joseph Crawford,Yihan Sun, and Tijana Milenkovic
  • Algorithms for Molecular Biology, 10:19.
  • Also, arXiv:1407.4824 [q-bio.MN]
Paper (AMB) AMB Website Full Paper (arXiv)
Data Mining
  • I have been working on data mining on social networks, especially influence maximization on dynamic networks.
Influence Maximization in Dynamic Social Networks
  • Honglei Zhuang, Yihan Sun, Jie Tang, Jialin Zhang and Xiaoming Sun
  • IEEE International Conference on Data Mining (ICDM), 2013.
Paper (Conference) Slides
My Word Cloud
Paper Abstracts
Research Statement

Services

Teaching

  • 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.

Paper Review

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

Awards and Hornors

  • Outstanding Graduated Student in Beijing, 2014.
  • Graduated with honors in Computer Science (Tsinghua Univ.), 2014.
  • Best Bachelor Thesis Award in Tsinghua Univ. (1st place in CS Department), 2014.
  • IBM scholarship for outstanding students, 2013(only 3 winners in Tsinghua).
  • The Scholarship of THTF for students in the School of Information, 2010 and 2011.
  • The Scholarship of Singapore Technologies Engineering Ltd, 2011(Top 5%).
  • The Scholarship of Changhong Electric Co. Ltd., 2011(Top 5%).
  • The Scholarship of Tung OOCL, 2012(Top 5%).
  • Outstanding Student Leader in CS&T Dept., Tsinghua Univ., 2011.
  • Outstanding Volunteer in the Zijing Mail Project, Volunteer Center, Tsinghua Univ., 2011.
  • 4-star Volunteer in Tsinghua Univ., 2013.
  • Star of Volunteer in Beijing, 2013.
  • 3rd Prize in Challenge Cup in Tsinghua University (with Project Come on With Me: App Based on Recommendation Algorithm of Mobile Social Network. Chao Zhang, Yingjie Zhang, Rui Liu, Tianyang Zhang, Yihan Sun, Weizhi Ma.