Data Structures
[Back to full publication list]
- 2025:[22] Optimal Batch-Dynamic kd-trees for Processing-in-Memory with Applications (To Appear)
Yiwei Zhao, Hongbo Kang, Yan Gu*, Guy E. Blelloch, Laxman Dhulipala, Charles McGuffey, and Phillip B. Gibbons
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2025
Paper -
[21]
New Algorithms for Incremental Minimum Spanning Trees and Temporal Graph Applications (To Appear)
Xiangyun Ding*, Yan Gu*, and Yihan Sun*
SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2025Software Library:AM-tree: Anti-Monoply tree for incremental MST and temporal connectivity [Github]
Paper Code -
[20]
Parallel k-Core Decomposition: Theory and Practice
Youzhe Liu*, Xiaojun Dong*, Yan Gu*, and Yihan Sun*
ACM Special Interest Group on Management of Data (SIGMOD), 2025DOI:10.1145/3725332Software Library:Parallel k-core implementation, integrated in PASGAL [Github]
Poster and oral presentation at the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2025
Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2025
Paper ArXiV Code Slides -
[19]
Pkd-tree: Parallel kd-tree with Batch Updates
Ziyang Men*, Zheqi Shen*, Yan Gu*, and Yihan Sun*
ACM Special Interest Group on Management of Data (SIGMOD), 2025DOI:10.1145/3709712Software Library:Pkd-tree: Parallel kd-tree [Github]
Poster and oral presentation at the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2025
Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2025
Paper ArXiV Code Slides Poster - 2024:[18] BYO: A Unified Framework for Benchmarking Large-Scale Graph Containers
Brian Wheatman, Xiaojun Dong*, Zheqi Shen*, Laxman Dhulipala, Jakub Łącki, Prashant Pandey, and Helen Xu
International Conference on Very Large Data Bases (VLDB), 2024DOI:10.14778/3665844.3665859Software Library:BYO: A Unified Framework for Benchmarking Large-Scale Graph Containers [Github]
Paper ArXiV Code -
[17]
Fast and Space-Efficient Parallel Algorithms for Influence Maximization
Letong Wang*, Xiangyun Ding*, Yan Gu*, and Yihan Sun*
International Conference on Very Large Data Bases (VLDB), 2024DOI:10.14778/3632093.3632104Software Library:PaC-IM: Parallel and Compressed Influence Maximization [Github]
Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2024
Paper ArXiV Code Poster - 2023:[16] 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 Library:Parallel Longest Increasing Subsequence [Github]
Paper ArXiV Code Slides -
[15]
Parallel Strong Connectivity Based on Faster Reachability
Letong Wang*, Xiaojun Dong*, Yan Gu*, and Yihan Sun*
ACM Special Interest Group on Management of Data (SIGMOD), 2023DOI:10.1145/3589259Software Library:Parallel Strongly Connected Components (SCC), integrated in PASGAL [Github]
Poster presented at the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2023
Poster presented at the Highlights of Parallel Computing (HOPC@SPAA), 2023
Paper ArXiV Code Slides Poster - 2022:[14] Bi-directional Log-Structured Merge Tree
Xin Zhang, Qizhong Mao, Ahmed Eldawy, Vagelis Hristidis, and Yihan Sun*
International Conference on Scientific and Statistical Database Management (SSDBM), 2022DOI:10.1145/3538712.3538730Software Library:Bi-directional LSM Tree [Github]
Paper Video -
[13]
Parallel Cover Trees and Applications
Yan Gu*, Zachary Napier, Yihan Sun*, and Letong Wang*
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2022DOI:10.1145/3490148.3538581
Paper Slides -
[12]
Many Sequential Iterative Algorithms Can Be Parallel and (Nearly) Work-efficient
Zheqi Shen*, Zijin Wan*, Yan Gu*, and Yihan Sun*
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2022DOI:10.1145/3490148.3538574Software Library:Parallel Dynamic Programming (DP) and greedy algorithms [Github]
Paper ArXiV Slides -
[11]
PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections
Laxman Dhulipala, Guy E. Blelloch, Yan Gu*, and Yihan Sun*
ACM Conference on Programming Language Design and Implementation (PLDI), 2022DOI:10.1145/3519939.3523733Software Library:CPAM: Compressed Parallel Augmented Maps [Github]
Paper ArXiV Code Slides -
[10]
Joinable Parallel Balanced Binary Trees
Guy E. Blelloch, Daniel Ferizovic, and Yihan Sun*
ACM Transactions on Parallel Computing (TOPC), 2022DOI:10.1145/3512769Software Library:PAM: Parallel Augmented Maps [Github]
Paper Code -
[9]
POSTER: The Problem-Based Benchmark Suite (PBBS), V2
Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, Magdalen Dobson Manohar, and Yihan Sun*
ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2022DOI:10.1145/3503221.3508422Software Library:PBBS: The Problem-Based Benchmark Suite [Github]
Paper Code - 2021:[8] The Processing-in-Memory Model
Hongbo Kang, Phillip B. Gibbons, Guy E. Blelloch, Laxman Dhulipala, Yan Gu*, and Charles McGuffey
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2021
Paper Video -
[7]
Space and Time Bounded Multiversion Garbage Collection
Naama Ben-David, Guy E. Blelloch, , , Yihan Sun*, and Yuanhao Wei
International Symposium on Distributed Computing (DISC), 2021DOI:10.4230/LIPIcs.DISC.2021.12
Paper Video ArXiV Slides -
[6]
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 Library:Rho-Stepping: Parallel single-source shortes paths, integrated in PASGAL [Github]
Paper Video ArXiV Code Slides -
[5]
An Experimental Study of a New Parallel Batch-Dynamic Closest Pair Data Structure
Yiqiu Wang, Shangdi Yu, Yan Gu*, and Julian Shun
ACM Symposium on Computational Geometry (SoCG), 2021Software Library:Parallel Batch-Dynamic Closest Pair [Github]
Paper ArXiV Code -
[4]
Constant-Time Snapshots with Applications to Concurrent Data Structures
Yuanhao Wei, Naama Ben-David, Guy E. Blelloch, Panagiota Fatourou, Eric Ruppert, and Yihan Sun*
ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2021DOI:10.1145/3437801.3441602Software Library:VCASLib [Github]
Paper Video ArXiV Code - 2020:[3] 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.3400227
Paper Video Slides -
[2]
Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs
Laxman Dhulipala, Charles McGuffey, Hongbo Kang, Yan Gu*, Guy E. Blelloch, Phillip B. Gibbons, and Julian Shun
International Conference on Very Large Data Bases (VLDB), 2020Software Library:SAGE: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs [Github]
Paper ArXiV Code -
[1]
On Supporting Efficient Snapshot Isolation for Hybrid Workloads with Multi-Versioned Indexes
Yihan Sun*, Guy E. Blelloch, Wan Shen Lim, and Andrew Pavlo
International Conference on Very Large Data Bases (VLDB), 2020DOI:10.14778/3364324.3364334Software Library:Part of the PAM library: Parallel Augmented Maps [Github]
Paper Video Code Slides