Publications - Data structures

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

[Back to full publication list]

• 2023:
  [17] 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
  
  parallel van Emde Boas tree
  Conference paper  Full version (arXiv)  
• [16] A Skew-Resistant Trie for Processing-in-Memory
  Hongbo Kang, Yiwei Zhao, Guy E. Blelloch, Laxman Dhulipala, Yan Gu, Charles McGuffey, and Phillip B. Gibbons
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2023
  
  trie on PIM
  Conference paper  
• [15] PIM-tree: A Skew-resistant Index for Processing-in-Memory
  Hongbo Kang, Yiwei Zhao, Guy Blelloch, Laxman Dhulipala, Yan Gu, Charles McGuffey, and Phillip Gibbons
  
  🏆 VLDB 2023 Best Paper Runner-Up
  VLDB
   Processings of the VLDB Endowment, 2023
  
  PIM-tree
  Conference paper  
• 2022:
  [14] ParGeo: A Library for Parallel Computational Geometry
  Yiqiu Wang, Rahul Yesantharao, Shangdi Yu, Laxman Dhulipala, Yan Gu, and Julian Shun
  
  ESA
   European Symposium on Algorithms (ESA), 2022
  
  Parallel kd-tree
  Conference paper  Full version (arXiv)  Code
• [13] 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
  
  Parallel cover tree
  Conference paper  
• [12] 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
  
  Using BST and TAS tree data structures to support work-efficiency
  Conference paper  Full version (arXiv)  
• [11] PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections
  Laxman Dhulipala, Guy Blelloch, Yan Gu, and Yihan Sun
  
  PLDI
   ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2022
  
  Space-efficient parallel trees
  Conference paper  Full version (arXiv)  
• 2021:
  [10] 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
  
  parallel priority queue
  Conference paper  Full version (arXiv)  Video  Code
• [9] 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
  
  skiplist
  Conference paper  Video  
• [8] An Experimental Study of a New Parallel Batch-Dynamic Closest Pair Data Structure
  Yiqiu Wang, Shangdi Yu, Yan Gu, and Julian Shun
  
  SoCG
   ACM Symposium on Computational Geometry (SoCG), 2021
  
  parallel binary heap
  Conference paper  Full version (arXiv)  Code
• 2020:
  [7] Randomized Incremental Convex Hull is Highly Parallel
  Guy E. Blelloch, Yan Gu, Julian Shun and Yihan Sun
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020.
  
  concurrent hash table
  Conference paper  Video  
• [6] Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs
  Laxman Dhulipala, Charlie McGuffey, Hongbo Kang, Yan Gu, Guy E. Blelloch, Phillip B. Gibbons, Julian Shun
  
  🏆 Memorable Paper Award Finalist at the Non-Volatile Memories Workshop (NVMW'20)
  VLDB
   Processings of the VLDB Endowment 13(9), 2020
  
  filtering structure
  Conference paper  Full version (arXiv)  Code
• 2018:
  [5] Algorithmic Building Blocks for Asymmetric Memories
  Yan Gu, Yihan Sun and Guy E. Blelloch
  
  ESA
   European Symposium on Algorithms (ESA), 2018
  
  hash table, search tree
  Conference paper  Full version (arXiv)  
• [4] Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry
  Guy E. Blelloch, Yan Gu, Julian Shun and Yihan Sun
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2018
  
  interval tree, priority search tree, range tree
  Conference paper  Full version (arXiv)  
• 2017:
  [3] Efficient Construction of Probabilistic Tree Embeddings
  Guy E. Blelloch, Yan Gu, and Yihan Sun
  
  ICALP
   International Colloquium on Automata, Languages, and Programming (ICALP), 2017.
  
  bucket-tree structure (constant-cost approximate priority queue)
  Conference paper  Full version (arXiv)  
• 2015:
  [2] Ray Specialized BVH Contraction
  Yan Gu, Yong He, and Guy Blelloch
  
  PG
   Pacific Graphics 2015. Computer Graphics Forum 34(7), 309-318
  
  bounding volume hierarchy (BVH)
  Conference paper  Full version  
• 2013:
  [1] Efficient BVH Construction via Approximate Agglomerative Clustering
  Yan Gu, Yong He, Kayvon Fatahalian, and Guy Blelloch
  
  HPG
   High Performance Graphics 2013, pp. 81-88
  
  bounding volume hierarchy (BVH)
  Project page  Conference paper  Code