[Back to full publication list]

• 2023:
  [25] Parallel Strong Connectivity Based on Faster Reachability (To Appear)
  Letong Wang, Xiaojun Dong, Yan Gu, and Yihan Sun
  
  SIGMOD
   ACM Special Interest Group on Management of Data (SIGMOD), 2023    [BibTeX]
  @inproceedings{ scc,
  title = { Parallel Strong Connectivity Based on Faster Reachability (To Appear) },
  author = {Wang, Letong and Dong, Xiaojun and Gu, Yan and Sun, Yihan},
  booktitle = {ACM Special Interest Group on Management of Data (SIGMOD)},
  year = { 2023 }
  }

  [copy]
  
  
  Hash bag data structure
• 2022:
  [24] Bi-directional Log-Structured Merge Tree
  Xin Zhang, Qizhong Mao, Ahmed Eldawy, Vagelis Hristidis, and Yihan Sun
  
  SSDBM
   International Conference on Scientific and Statistical Database Management (SSDBM), 2022    [BibTeX]
  @inproceedings{ bidirectional,
  title = { Bi-directional Log-Structured Merge Tree },
  author = {Zhang, Xin and Mao, Qizhong and Eldawy, Ahmed and Hristidis, Vagelis and Sun, Yihan},
  booktitle = {International Conference on Scientific and Statistical Database Management (SSDBM)},
  year = { 2022 }
  }

  [copy]
  
  
  LSM tree
  Paper   Video  
• [23] Parallel Cover Trees and Applications
  Yan Gu, Zachary Napier, Yihan Sun, and Letong Wang
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2022    [BibTeX]
  @inproceedings{ covertree,
  title = { Parallel Cover Trees and Applications },
  author = {Gu, Yan and Napier, Zachary and Sun, Yihan and Wang, Letong},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2022 }
  }

  [copy]
  
  
  Parallel cover tree.
  Paper   Slides  
• [22] Many Sequential Iterative Algorithms Can Be Parallel and (Nearly) Work-efficient
  Zheqi Shen, Zijin Wan, Yan Gu, and Yihan Sun
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2022    [BibTeX]
  @inproceedings{ iterative,
  title = { Many Sequential Iterative Algorithms Can Be Parallel and (Nearly) Work-efficient },
  author = {Shen, Zheqi and Wan, Zijin and Gu, Yan and Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2022 }
  }

  [copy]
  
  
  Using BST and TAS tree data structures to support work-efficiency.
  Paper   ArXiV  Slides  
• [21] 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{ pactree,
  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]
  
  
  Compressed functional search trees called PaC-trees for supporting collection data types
  Paper   ArXiV  Code  Slides  
• [20] Joinable Parallel Balanced Binary Trees
  Guy E. Blelloch, Daniel Ferizovic, and Yihan Sun
  
  TOPC
   ACM Transactions on Parallel Computing (TOPC), 2022    [BibTeX]
  @inproceedings{ joinable,
  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]
  
  
  Join-based trees for multiple balancing schemes
  Paper   Code  
• [19] POSTER: The Problem-Based Benchmark Suite (PBBS), V2
  Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, Magdalen Dobson, and Yihan Sun
  
  PPoPP
   ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2022    [BibTeX]
  @inproceedings{ pbbsv2,
  title = { POSTER: The Problem-Based Benchmark Suite (PBBS), V2 },
  author = {Anderson, Daniel and Blelloch, Guy E. and Dhulipala, Laxman and Dobson, Magdalen and Sun, Yihan},
  booktitle = {ACM Symposium on Principles and Practice of Parallel Programming (PPoPP)},
  year = { 2022 }
  }

  [copy]
  
  
  join-based trees, suffix arrays
  Paper   Code  
• 2021:
  [18] The Processing-in-Memory Model
  Hongbo Kang, Phillip B. Gibbons, Guy E. Blelloch, Laxman Dhulipala, Yan Gu, and Charles McGuffey
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2021    [BibTeX]
  @inproceedings{ pim,
  title = { The Processing-in-Memory Model },
  author = {Kang, Hongbo and Gibbons, Phillip B. and Blelloch, Guy E. and Dhulipala, Laxman and Gu, Yan and McGuffey, Charles},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2021 }
  }

  [copy]
  
  
  skiplist
  Paper   Video  
• [17] Space and Time Bounded Multiversion Garbage Collection
  Naama Ben-David, Guy E. Blelloch, Panagiota Fatourou, Eric Ruppert, Yihan Sun, and Yuanhao Wei
  
  DISC
   International Symposium on Distributed Computing (DISC), 2021    [BibTeX]
  @inproceedings{ mvgc,
  title = { Space and Time Bounded Multiversion Garbage Collection },
  author = {Ben-David, Naama and Blelloch, Guy E. and Fatourou, Panagiota and Ruppert, Eric and Sun, Yihan and Wei, Yuanhao},
  booktitle = {International Symposium on Distributed Computing (DISC)},
  year = { 2021 }
  }

  [copy]
  
  
  Garbage collection for concurrent multi-versioned data structures
  Paper   Video  ArXiV  
• [16] Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths
  Xiaojun Dong, Yan Gu, Yihan Sun, and Yunming Zhang
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2021    [BibTeX]
  @inproceedings{ stepping,
  title = { Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths },
  author = {Dong, Xiaojun and Gu, Yan and Sun, Yihan and Zhang, Yunming},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2021 }
  }

  [copy]
  
  
  parallel priority queues based on arrays and tournament trees
  Paper   Video  ArXiV  Code  
• [15] An Experimental Study of a New Parallel Batch-Dynamic Closest Pair Data Structure
  Wang Yiqiu, Shangdi Yu, Yan Gu, and Julian Shun
  
  SoCG
   ACM Symposium on Computational Geometry (SoCG), 2021    [BibTeX]
  @inproceedings{ closestpair,
  title = { An Experimental Study of a New Parallel Batch-Dynamic Closest Pair Data Structure },
  author = {Yiqiu, Wang and Yu, Shangdi and Gu, Yan and Shun, Julian},
  booktitle = {ACM Symposium on Computational Geometry (SoCG)},
  year = { 2021 }
  }

  [copy]
  
  
  parallel binary heap
  Paper   ArXiV  Code  
• [14] Constant-Time Snapshots with Applications to Concurrent Data Structures
  Yuanhao Wei, Naama Ben-David, Guy E. Blelloch, Panagiota Fatourou, Eric Ruppert, and Yihan Sun
  
  PPoPP
   ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2021    [BibTeX]
  @inproceedings{ vcas,
  title = { Constant-Time Snapshots with Applications to Concurrent Data Structures },
  author = {Wei, Yuanhao and Ben-David, Naama and Blelloch, Guy E. and Fatourou, Panagiota and Ruppert, Eric and Sun, Yihan},
  booktitle = {ACM Symposium on Principles and Practice of Parallel Programming (PPoPP)},
  year = { 2021 }
  }

  [copy]
  
  
  Take snapshots on concurrent data structures
  Paper   Video  ArXiV  Code  
• 2020:
  [13] Optimal (Randomized) Parallel Algorithms in the Binary-Forking Model
  Guy E. Blelloch, Jeremy Fineman, Yan Gu, and Yihan Sun
  
  🏆 Best Paper Candidate!
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020    [BibTeX]
  @inproceedings{ binaryforking,
  title = { Optimal (Randomized) Parallel Algorithms in the Binary-Forking Model },
  author = {Blelloch, Guy E. and Fineman, Jeremy and Gu, Yan and Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2020 }
  }

  [copy]
  
  
  Parallel set operations with optimal work and span using BST
  Paper   Video  
• [12] 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
  
  VLDB
   Proceedings of the VLDB Endowment (VLDB), 2020    [BibTeX]
  @inproceedings{ ,
  title = { Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs },
  author = {Dhulipala, Laxman and McGuffey, Charles and Kang, Hongbo and Gu, Yan and Blelloch, Guy E. and Gibbons, Phillip B. and Shun, Julian},
  booktitle = {Proceedings of the VLDB Endowment (VLDB)},
  year = { 2020 }
  }

  [copy]
  
  
  filtering structure
  Paper   ArXiV  Code  
• 2019:
  [11] 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{ pam-snapshot,
  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]
  
  
  Supporting snapshot isolation and MVCC in databases using P-trees in PAM
  Paper   Video  Code  
• [10] 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{ single-writer,
  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]
  
  
  Garbage collection of multi-versioned P-tree-like structures (path-copying data structures)
  Paper   ArXiV  
• [9] 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{ ppopp-tutorial,
  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]
  
  
  Tutorial about P-trees and the PAM library
  Paper   
• [8] Parallel Range, Segment and Rectangle Queries with Augmented Maps
  Yihan Sun, and Guy E. Blelloch
  
  ALENEX
   Algorithm Engineering and Experiments (ALENEX), 2019    [BibTeX]
  @inproceedings{ pam-geometry,
  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]
  
  
  Using P-trees and PAM to solve range, segment and rectangle queries in parallel
  Paper   ArXiV  
• 2018:
  [7] Algorithmic Building Blocks for Asymmetric Memories
  Yan Gu, Yihan Sun, and Guy E. Blelloch
  
  ESA
   European Symposium on Algorithms (ESA), 2018    [BibTeX]
  @inproceedings{ we-exp,
  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]
  
  
  write-efficient join-based tree algorithms and hash table
  Paper   ArXiV  
• [6] Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry
  Guy E. Blelloch, Yan Gu, Yihan Sun, and Julian Shun
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2018    [BibTeX]
  @inproceedings{ we-geo,
  title = { Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry },
  author = {Blelloch, Guy E. and Gu, Yan and Sun, Yihan and Shun, Julian},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2018 }
  }

  [copy]
  
  
  Parallel write-efficient algorithms on interval tree, priority search tree, range tree
  Paper   ArXiV  
• [5] 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{ pam,
  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]
  
  
  Introducing P-tree and the PAM library
  Paper   ArXiV  Code  
• 2017:
  [4] Efficient Construction of Probabilistic Tree Embeddings
  Guy E. Blelloch, Yan Gu, and Yihan Sun
  
  ICALP
   International Colloquium on Automata, Languages, and Programming (ICALP), 2017    [BibTeX]
  @inproceedings{ frt,
  title = { Efficient Construction of Probabilistic Tree Embeddings },
  author = {Blelloch, Guy E. and Gu, Yan and Sun, Yihan},
  booktitle = {International Colloquium on Automata, Languages, and Programming (ICALP)},
  year = { 2017 }
  }

  [copy]
  
  
  FRT trees
  Paper   ArXiV  
• 2016:
  [3] 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{ join,
  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]
  
  
  algorithms on P-trees
  Paper   ArXiV  Code  
• 2015:
  [2] Ray Specialized BVH Contraction
  Yan Gu, Yong He, and Guy E. Blelloch
  
  PG
   Pacific Graphics. Computer Graphics Forum (PG), 2015    [BibTeX]
  @inproceedings{ ,
  title = { Ray Specialized BVH Contraction },
  author = {Gu, Yan and He, Yong and Blelloch, Guy E.},
  booktitle = {Pacific Graphics. Computer Graphics Forum (PG)},
  year = { 2015 }
  }

  [copy]
  
  
  bounding volume hierarchy (BVH)
  Paper   
• 2013:
  [1] Efficient BVH Construction via Approximate Agglomerative Clustering
  Yan Gu, Yong He, Kayvon Fatahalian, and Guy E. Blelloch
  
  HPG
   High Performance Graphics (HPG), 2013    [BibTeX]
  @inproceedings{ ,
  title = { Efficient BVH Construction via Approximate Agglomerative Clustering },
  author = {Gu, Yan and He, Yong and Fatahalian, Kayvon and Blelloch, Guy E.},
  booktitle = {High Performance Graphics (HPG)},
  year = { 2013 }
  }

  [copy]
  
  
  bounding volume hierarchy (BVH)
  Paper   Code  Page