Publications - Tree Algorithms
You can also find my publication list on Google Scholar and DBLP.
[Back to full publication list]
- 2024:[13] Fast and Space-Efficient Parallel Algorithms for Influence Maximization
Letong Wang, Xiangyun Ding, Yan Gu, and Yihan Sun
Proceedings of the VLDB Endowment (VLDB), 2024DOI:10.14778/3632093.3632104Software:PaC-IM: Parallel and Compressed Influence Maximization [Github]
Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2024P-tree and parallel tournament tree for parallelizing CELFPaper ArXiV Code Poster - 2023:[12] Parallel Longest Increasing Subsequence and van Emde Boas Trees
Yan Gu, Ziyang Men, Zheqi Shen, Yihan Sun, and Zijin Wan
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2023DOI:10.1145/3558481.3591069Software:Parallel Longest Increasing Subsequence [Github]Parallel van Emde Boas TreePaper ArXiV Code Slides - 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.3461782Software:Rho-Stepping: Parallel single-source shortes paths, integrated in PASGAL [Github]parallel tournament treesPaper Video ArXiV Code Slides - 2020:[10] Optimal (Randomized) Parallel Algorithms in the Binary-Forking Model
Guy E. Blelloch, Jeremy T. Fineman, Yan Gu, and Yihan Sun🏆 Best Paper Candidate!ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020DOI:10.1145/3350755.3400227Parallel set operations with optimal work and span using BSTPaper Video Slides - [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), 2020DOI:10.14778/3364324.3364334Software:Part of the PAM library: Parallel Augmented Maps [Github]Supporting snapshot isolation and MVCC in databases using P-trees in PAMPaper Video Code Slides - 2019:[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.13Software:Part of the PAM library: Parallel Augmented Maps [Github]Using 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.3178509Software:PAM: Parallel Augmented Maps [Github]Introducing 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.2935768Software:Part of the PAM library: Parallel Augmented Maps [Github]Introducing join-based algorithms for BSTsPaper ArXiV Code