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 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
- Proceedings of the VLDB Endowment (PVLDB), 13(2).
Paper Code (for TPC-H)
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.
