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  [BibTeX]
  @inproceedings{ Dhulipala2022PaC-trees:,
  title = { PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections },
  author = {Dhulipala, Laxman and Blelloch, Guy and Gu, Yan and Sun, Yihan},
  booktitle = {ACM Conference on Programming Language Design and Implementation (PLDI)},
  year = { 2022 }
  }

  [copy]
  
  
  DOI:
  10.1145/3519939.3523733    [copy]
  
  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  [BibTeX]
  @inproceedings{ Blelloch2022Joinable,
  title = { Joinable Parallel Balanced Binary Trees },
  author = {Blelloch, Guy E. and Ferizovic, Daniel and Sun, Yihan},
  booktitle = {ACM Transactions on Parallel Computing (TOPC)},
  year = { 2022 }
  }

  [copy]
  
  
  DOI:
  10.1145/3512769    [copy]
  
  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  [BibTeX]
  @inproceedings{ Sun2019On,
  title = { On Supporting Efficient Snapshot Isolation for Hybrid Workloads with Multi-Versioned Indexes },
  author = {Sun, Yihan and Blelloch, Guy E. and Lim, Wan Shen and Pavlo, Andrew},
  booktitle = {Proceedings of the VLDB Endowment (VLDB)},
  year = { 2019 }
  }

  [copy]
  
  
  DOI:
  10.14778/3364324.3364334    [copy]
  
  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  [BibTeX]
  @inproceedings{ Ben-David2019Multiversion,
  title = { Multiversion Concurrency with Bounded Delay and Precise Garbage Collection },
  author = {Ben-David, Naama and Blelloch, Guy E. and Sun, Yihan and Wei, Yuanhao},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2019 }
  }

  [copy]
  
  
  DOI:
  10.1145/3323165.3323185    [copy]
  
  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  [BibTeX]
  @inproceedings{ Sun2019Implementing,
  title = { Implementing Parallel and Concurrent Tree Structures },
  author = {Sun, Yihan and Blelloch, Guy E.},
  booktitle = {ACM Symposium on Principles and Practice of Parallel Programming (PPoPP)},
  year = { 2019 }
  }

  [copy]
  
  
  DOI:
  10.1145/3293883.3302576    [copy]
  
  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  [BibTeX]
  @inproceedings{ Sun2019Parallel,
  title = { Parallel Range, Segment and Rectangle Queries with Augmented Maps },
  author = {Sun, Yihan and Blelloch, Guy E.},
  booktitle = {Algorithm Engineering and Experiments (ALENEX)},
  year = { 2019 }
  }

  [copy]
  
  
  DOI:
  10.1137/1.9781611975499.13    [copy]
  
  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  [BibTeX]
  @inproceedings{ Gu2018Algorithmic,
  title = { Algorithmic Building Blocks for Asymmetric Memories },
  author = {Gu, Yan and Sun, Yihan and Blelloch, Guy E.},
  booktitle = {European Symposium on Algorithms (ESA)},
  year = { 2018 }
  }

  [copy]
  
  
  DOI:
  10.4230/LIPIcs.ESA.2018.44    [copy]
  
  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  [BibTeX]
  @inproceedings{ Sun2018PAM:,
  title = { PAM: Parallel Augmented Maps },
  author = {Sun, Yihan and Ferizovic, Daniel and Blelloch, Guy E.},
  booktitle = {ACM Symposium on Principles and Practice of Parallel Programming (PPoPP)},
  year = { 2018 }
  }

  [copy]
  
  
  DOI:
  10.1145/3200691.3178509    [copy]
  
  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  [BibTeX]
  @inproceedings{ Blelloch2016Just,
  title = { Just Join for Parallel Ordered Sets },
  author = {Blelloch, Guy E. and Ferizovic, Daniel and Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2016 }
  }

  [copy]
  
  
  DOI:
  10.1145/2935764.2935768    [copy]
  
  Introducing join-based algorithms for BSTs
  Paper   ArXiV  Code