Publications - P-trees, PAM library and join-based algorithms

You can also find my publication list on Google Scholar and DBLP.

[Back to full publication list]

  • 2022:
    [9] PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections
    Laxman Dhulipala, Guy Blelloch, Yan Gu, and Yihan Sun
    PLDI
     ACM Conference on Programming Language Design and Implementation (PLDI), 2022  
    DOI:
    10.1145/3519939.3523733   
    Pac-tree, the compressed version of join-based weight-balanced tree
    Paper   ArXiV  Code  Slides
  • [8] Joinable Parallel Balanced Binary Trees
    Guy E. Blelloch, Daniel Ferizovic, and Yihan Sun
    TOPC
     ACM Transactions on Parallel Computing (TOPC), 2022  
    DOI:
    10.1145/3512769   
    general algorithmic and proof framework for join-based trees
    Paper   Code  
  • 2019:
    [7] On Supporting Efficient Snapshot Isolation for Hybrid Workloads with Multi-Versioned Indexes
    Yihan Sun, Guy E. Blelloch, Wan Shen Lim, and Andrew Pavlo
    VLDB
     Proceedings of the VLDB Endowment (VLDB), 2019  
    DOI:
    10.14778/3364324.3364334   
    Supporting snapshot isolation and MVCC in databases using P-trees in PAM
    Paper   Video  Code  
  • [6] Multiversion Concurrency with Bounded Delay and Precise Garbage Collection
    Naama Ben-David, Guy E. Blelloch, Yihan Sun, and Yuanhao Wei
    SPAA
     ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2019  
    DOI:
    10.1145/3323165.3323185   
    Garbage collection of multi-versioned P-tree-like structures (path-copying data structures)
    Paper   ArXiV  
  • [5] Implementing Parallel and Concurrent Tree Structures
    Yihan Sun, and Guy E. Blelloch
    PPoPP
     ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2019  
    DOI:
    10.1145/3293883.3302576   
    Tutorial about P-trees and the PAM library
    Paper   
  • [4] Parallel Range, Segment and Rectangle Queries with Augmented Maps
    Yihan Sun, and Guy E. Blelloch
    ALENEX
     Algorithm Engineering and Experiments (ALENEX), 2019  
    DOI:
    10.1137/1.9781611975499.13   
    Using P-trees and PAM to solve range, segment and rectangle queries in parallel
    Paper   ArXiV  
  • 2018:
    [3] Algorithmic Building Blocks for Asymmetric Memories
    Yan Gu, Yihan Sun, and Guy E. Blelloch
    ESA
     European Symposium on Algorithms (ESA), 2018  
    DOI:
    10.4230/LIPIcs.ESA.2018.44   
    write-efficient join-based tree algorithms
    Paper   ArXiV  
  • [2] PAM: Parallel Augmented Maps
    Yihan Sun, Daniel Ferizovic, and Guy E. Blelloch
    PPoPP
     ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2018  
    DOI:
    10.1145/3200691.3178509   
    Introducing P-tree and the PAM library
    Paper   ArXiV  Code  
  • 2016:
    [1] Just Join for Parallel Ordered Sets
    Guy E. Blelloch, Daniel Ferizovic, and Yihan Sun
    SPAA
     ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016  
    DOI:
    10.1145/2935764.2935768   
    Introducing join-based algorithms for BSTs
    Paper   ArXiV  Code