About Me

I am currently a Ph.D student in Computer Science Department at Carnegie Mellon University, working on parallel algorithms, data structures and their applications. My advisor is Prof. Guy Blelloch.

I received my Bachelor degree in Computer Science from Tsinghua University, working on data mining and social network analysis.

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

This is the homepage of my lovely husband.

My google scholar page

Publication list on DBLP

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.
Efficient Single Writer Concurrency
Full Paper (arXiv)
Parallel Range, Segment and Rectangle Queries with Augmented Maps
  • Yihan Sun and Guy E. Blelloch
  • Manuscript.
  • 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 and Segment Queries with Augmented Maps
  • Yihan Sun and Guy E. Blelloch
  • Manuscript.
  • 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), strongly-connected component (SCC), graph embedding and so on. I also have worked on network alignment on biological graphs, and social network analysis, which will be classified to later categories.
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)
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.
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

Services

Teaching

  • CMU 15-859 (Algorithms in the "real world") Teaching Assistance (Spring 2018).
  • CMU 15-451/651 (Algorithms) Teaching Assitance (Spring 2017).

Paper Review

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