Persistent (Functional) Data Structures
[Back to full publication list]
Persistent (functional) data structures, which are immutable data structures that preserves the previous version of itself upon updates.
- 2025:[6] 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 - 2022:[5] 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 -
[4]
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 -
[3]
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 - 2020:[2] 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 -
[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