[Back to full publication list]

• 2025:
  [28] Pkd-tree: Parallel kd-tree with Batch Updates (To Appear)
  Ziyang Men, Zheqi Shen, Yan Gu, and Yihan Sun
  
  SIGMOD
   ACM Special Interest Group on Management of Data (SIGMOD), 2025    [BibTeX]
  @inproceedings{ pkdtree,
  title = { Pkd-tree: Parallel kd-tree with Batch Updates (To Appear) },
  author = {Men, Ziyang and Shen, Zheqi and Gu, Yan and Sun, Yihan},
  booktitle = {ACM Special Interest Group on Management of Data (SIGMOD)},
  year = { 2025 }
  }

  [copy]
  
  
  parallel kdtree
  Paper   
• 2024:
  [27] Fast and Space-Efficient Parallel Algorithms for Influence Maximization
  Letong Wang, Xiangyun Ding, Yan Gu, and Yihan Sun
  
  VLDB
   Proceedings of the VLDB Endowment (VLDB), 2024    [BibTeX]
  @inproceedings{ im,
  title = { Fast and Space-Efficient Parallel Algorithms for Influence Maximization },
  author = {Wang, Letong and Ding, Xiangyun and Gu, Yan and Sun, Yihan},
  booktitle = {Proceedings of the VLDB Endowment (VLDB)},
  year = { 2024 }
  }

  [copy]
  
  
  HOPC
   Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2024
  
  Parallel data structures for CELF
  Paper   ArXiV  Code  
• 2023:
  [26] Parallel Longest Increasing Subsequence and van Emde Boas Trees
  Yan Gu, Ziyang Men, Zheqi Shen, Yihan Sun, and Zijin Wan
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2023    [BibTeX]
  @inproceedings{ lis-veb,
  title = { Parallel Longest Increasing Subsequence and van Emde Boas Trees },
  author = {Gu, Yan and Men, Ziyang and Shen, Zheqi and Sun, Yihan and Wan, Zijin},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2023 }
  }

  [copy]
  
  
  Parallel van Emde Boas Tree
  Paper   ArXiV  Code  Slides  
• [25] Parallel Strong Connectivity Based on Faster Reachability
  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 },
  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]
  
  
  ACDA
   Poster presented at the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2023
  
  HOPC
   Poster presented at the Highlights of Parallel Computing (HOPC@SPAA), 2023
  
  Hash bag data structure
  Paper   ArXiV  Code  Slides  
• 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