Publications - Tree Algorithms
You can also find my publication list on Google Scholar and DBLP.
[Back to full publication list]
- 2021:[11] Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths
Xiaojun Dong, Yan Gu, Yihan Sun, and Yunming Zhang
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2021DOI:10.1145/3409964.3461782parallel tournament treesPaper Video ArXiV Code - 2020:[10] Optimal (Randomized) Parallel Algorithms in the Binary-Forking Model
Guy E. Blelloch, Jeremy Fineman, Yan Gu, and Yihan Sun🏆 Outstanding Paper Award!ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020DOI:10.1145/3350755.3400227Parallel set operations with optimal work and span using BSTPaper Video - 2019:[9] 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 (VLDB), 2019DOI:10.14778/3364324.3364334Supporting snapshot isolation and MVCC in databases using P-trees in PAMPaper Video Code - [8]
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), 2019DOI:10.1145/3323165.3323185Garbage collection of multi-versioned P-tree-like structures (path-copying data structures)Paper ArXiV - [7]
Implementing Parallel and Concurrent Tree Structures
Yihan Sun, and Guy E. Blelloch
ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2019DOI:10.1145/3293883.3302576Tutorial about P-trees and the PAM libraryPaper - [6]
Parallel Range, Segment and Rectangle Queries with Augmented Maps
Yihan Sun, and Guy E. Blelloch
Algorithm Engineering and Experiments (ALENEX), 2019DOI:10.1137/1.9781611975499.13Using P-trees and PAM to solve range, segment and rectangle queries in parallelPaper ArXiV - 2018:[5] Algorithmic Building Blocks for Asymmetric Memories
Yan Gu, Yihan Sun, and Guy E. Blelloch
European Symposium on Algorithms (ESA), 2018DOI:10.4230/LIPIcs.ESA.2018.44write-efficient join-based tree algorithmsPaper ArXiV - [4]
Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry
Guy E. Blelloch, Yan Gu, Yihan Sun, and Julian Shun
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2018DOI:10.1145/3210377.3210380Parallel write-efficient algorithms on interval tree, priority search tree, range treePaper ArXiV - [3]
PAM: Parallel Augmented Maps
Yihan Sun, Daniel Ferizovic, and Guy E. Blelloch
ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2018DOI:10.1145/3200691.3178509Introducing P-tree and the PAM libraryPaper ArXiV Code - 2017:[2] Efficient Construction of Probabilistic Tree Embeddings
Guy E. Blelloch, Yan Gu, and Yihan Sun
International Colloquium on Automata, Languages, and Programming (ICALP), 2017DOI:10.4230/LIPIcs.ICALP.2017.26FRT treesPaper ArXiV - 2016:[1] Just Join for Parallel Ordered Sets
Guy E. Blelloch, Daniel Ferizovic, and Yihan Sun
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016DOI:10.1145/2935764.2935768Introducing join-based algorithms for BSTsPaper ArXiV Code