Position:  PhD Student

Current Institution:  Carnegie Mellon University

Abstract:  Parallel Algorithms and Data Structures in Theory and Practice

Nowadays, the explosion of data has raised new challenges necessitating considering parallelism and/or concurrency in algorithm design and engineering. On the other hand, multi-core processors are now used in from smartphones to big database servers, making it possible to bring parallel algorithms to practice. Unfortunately, classic algorithm design and engineering mainly focus on the sequential setting, and implementations of parallel/concurrent algorithms are usually complicated, less portable and scalable. My research has been mostly focusing on designing parallel and concurrent algorithms that are simple, generic, and practically efficient and meanwhile have good theoretical worst-case guarantees. Some research topics that I have been working on include: (1) Parallel tree structures. I have a series of work on parallel and concurrent tree algorithms implementations and applications that have tight theoretical bounds and good practical performance. The most essential components include a theoretically-efficient algorithmic framework for parallel balance binary tree, as well as a parallel general-purpose C++ library implementing all these algorithms using fully-persistent (functional) tree structures. We apply this tree structure to many applications, e.g., range query, segment query, inverted indices, transactional memory with multi-version concurrency control (MVCC) and efficient garbage collection (GC) and an HTAP (hybrid transactional/analytical processing) database system with snapshot isolation. (2) Write-efficient algorithms. Motivated by the significantly higher cost of writing than reading in emerging NVM technologies, I have been seeking sequential and parallel write-efficient algorithms with an emphasis on tree algorithms and geometric algorithms. (3) Parallel algorithms in computational geometry. I have worked on both theoretical and experimental work in computational geometry. They either use our framework of the parallel tree structures or a group of randomized incremental algorithms. (4) Assorted parallel algorithms on other topics including parallel sort and semi-sort algorithms, parallel shortest path algorithms, and probabilistic tree embeddings.

Bio:
Yihan Sun is currently a fifth-year PhD student in the Computer Science Department at Carnegie Mellon University, advised by Professor Guy Blelloch. She received a bachelor’s degree in computer science from Tsinghua University in 2010. She received the Best Bachelor Thesis Award from Tsinghua University (first place in the Computer Science Department) in 2014. Her research interests lie in parallel and concurrent algorithms and data structures and their applications that are simple, generic, and practically efficient and that, meanwhile, have good theoretical guarantees for worst-case performance.