Publications

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

You can also view my publications by category:

By topics:

Graph algorithms   Geometric algorithms   Set/tree algorithms   Data Science   Sorting algorithms  

By approaches or goals:

Incremental algorithms   Write-efficient algorithms   Cache-oblivious algorithms  

By focus:

New architecture   System design   Theory   Experiments   Code available  

Shortcut to Some Papers:

 [Parallel SCC]  [Parallel BCC]  [Phase-Parallel Algorithms]  [PaC-Tree]  [Stepping Algorithms]  [In-place algorithms]  [Binary forking]  [DBSCAN]  [Incremental]  [Cache-oblivous DP]  [Semisort]  

• 2024:
  [49] Fast and Space-Efficient Parallel Algorithms for Influence Maximization (to appear)
  Letong Wang, Xiangyun Ding, Yan Gu, and Yihan Sun
  
  VLDB
   Processings of the VLDB Endowment, 2024
  
  Fast, highly parallel and space-efficient solutions for influence maximization
  #data science, #theory, #data structure, #experiments, #code available
• [48] Parallel Integer Sort: Theory and Practice (to appear)
  Xiaojun Dong, Laxman Dhulipala, Yan Gu, and Yihan Sun
  
  PPoPP
   ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2024
  
  Highly parallel and fast integer sort, with new theoretical analysis
  #theory #sort, #experiments, #code available
• [47] ParANN: Scalable and Deterministic Parallel Graph-Based Algorithms for Approximate Nearest Neighbor Search (to appear)
  Magdalen Dobson, Zheqi Shen, Guy Blelloch, Laxman Dhulipala, Yan Gu, Harsha Simhadri, and Yihan Sun
  
  PPoPP
   ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2024
  
  The first billion-scale software for ANNS, with additional features such as determinism and high parallelism
  #machine learning, #experiments, #code available, #graph
• 2023:
  [46] Efficient Parallel Output-Sensitive Edit Distance
  Xiangyun Ding, Xiaojun Dong, Yan Gu, Youzhe Liu, and Yihan Sun
  
  🏆 Best Paper Award
  ESA
   European Symposium on Algorithms (ESA), 2023
  
  Parallel output-sensitive edit distance
  #string, #experiments, #code available
  Conference paper  Full version (arXiv)  Code
• [45] High-Performance and Flexible Parallel Algorithms for Semisort and Related Problems
  Xiaojun Dong, Yunshu Wu, Zhongqi Wang, Laxman Dhulipala, Yan Gu, and Yihan Sun
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2023
  
  Highly parallel and fast semisort software
  #sort, #experiments, #code available
  Conference paper  Full version (arXiv)  Code
• [44] 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
  
  Simple and work-efficient parallel algorithm of LIS, and parallel vEB tree
  #LIS, #theory, #experiments, #code available
  Conference paper  Full version (arXiv)  
• [43] 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
  
  Parallel trie for PIM
  #architecture, #data structure, #set/tree algorithms
  Conference paper  
• [42] Parallel Strong Connectivity Based on Faster Reachability
  Letong Wang, Xiaojun Dong, Yan Gu, and Yihan Sun
  
  SIGMOD
   ACM International Conference on Management of Data (SIGMOD), 2023
  
  A consistently fast parallel SCC algorithm/implementation
  #graph, #theory, #experiments, #code available
  Conference paper  Full version (arXiv)  Code
• [41] Provably Fast and Space-Efficient Parallel Biconnectivity
  Xiaojun Dong, Letong Wang, Yan Gu, and Yihan Sun
  
  🏆 Best Paper Award
  PPoPP
   ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2023
  
  The first work-, span-, and space-efficient BCC algorithm with fast practical performance
  #graph, #theory, #experiments, #code available
  Conference paper  Full version (arXiv)  Code
• [40] 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
  
  A consistent high-performance search tree structure on PIM architecture
  #architecture, #data structure, #set/tree algorithms, #experiments, #code available
  Conference paper  
• 2022:
  [39] LuisaRender: A High-Performance Rendering Framework with Layered and Unified Interfaces on Stream Architectures
  Shaokun Zheng, Zhiqian Zhou, Xin Chen, Difei Yan, Chuyan Zhang, Yuefeng Geng, Yan Gu, and Kun Xu
  
  SIGGRAPH Asia
   SIGGRAPH Asia 2022, (journal version, published in ACM Transactions on Graphics (TOG))
  
  A high-performance rendering framework
  #geometry, #graphics, #experiments, #code available
  Conference paper  
• [38] 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
  
  A library for commonly used parallel algorithms in computational geometry
  #geometry, #data-science, #experiments, #code available
  Conference paper  Full version (arXiv)  Code
• [37] 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 data structure for nearest neighbor search and other applications
  #cover tree, #data structure, #agglomerative clustering
  Conference paper  
• [36] 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
  
  Parallelizing classic sequential iterative algorithms, including activity selection, LIS, Huffman tree, Dijkstra's algorithm, MIS, etc.
  #paralleling sequential iterative algorithms, #data structure, #LIS, #MIS, #SSSP
  Conference paper  Full version (arXiv)  
• [35] 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
  
  A space and theoretically efficient data structure that support broad functionality
  Conference paper  Full version (arXiv)  
• [34] POSTER: ParGeo: A Library for Parallel Computational Geometry
  Yiqiu Wang, Shagndi Yu, Laxman Dhulipala, Yan Gu, and Julian Shun
  
  PPoPP
   ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 2022
  
  A Library for Parallel Computational Geometry
  #geometry, #experiments, #code avaiable
  Conference paper  
• [33] Analysis of Work-Stealing and Parallel Cache Complexity
  Yan Gu, Zachary Napier, and Yihan Sun
  
  APOCS
   ACM-SIAM Algorithmic Principles of Computer Systems (APoCS), 2022
  
  New simplified analysis for RWS, and improved parallel cache bounds
  #theory
  Conference paper  Full version (arXiv)  
• 2021:
  [32] ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain
  Shangdi Yu, Yiqiu Wang, Yan Gu, Laxman Dhulipala, and Julian Shun
  
  VLDB
   Processings of the VLDB Endowment
  
  Parallel algorithms for hierarchical agglomerative clustering (HAC)
  #geometry, #data-science, #experiments, #code available
  Conference paper  Full version (arXiv)  
• [31] 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
  
  Theoretical and practical parallel SSSP algorithms
  #graph, #SSSP, #theory, #experiments, #code available
  Conference paper  Full version (arXiv)  Video  Code
• [30] 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
  
  Model and algorithms (skiplists) for PIM architecture
  #architecture, #model-of-computation, #data structure, #set/tree algorithms
  Conference paper  Video  
• [29] GeoGraph: A Framework for Graph Processing on Geometric Data
  Yiqiu Wang, Shangdi Yu, Laxman Dhulipala, Yan Gu, and Julian Shun
  
  SIGOPS OSR
   ACM SIGOPS Operating Systems Review, Vol. 55 Issue 1, pp. 38-46, 2021
  
  Enable parallel graph processing for geometric data
  #system #graph #geometry
  Conference paper  Code
• [28] Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering
  Yiqiu Wang, Shangdi Yu, Yan Gu, and Julian Shun
  
  SIGMOD
   ACM International Conference on Management of Data (SIGMOD), 2021
  
  As the title says
  #geometry, #data-science, #theory, #experiments, #code available
  Conference paper  Full version (arXiv)  Video  Code
• [27] 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
  
  #geometry, #theory, #experiments, #code available
  Conference paper  Full version (arXiv)  Code
• [26] Parallel In-Place Algorithms: Theory and Practice
  Yan Gu, Omar Obeya, and Julian Shun
  
  APOCS
   ACM-SIAM Algorithmic Principles of Computer Systems (APoCS), 2021
  
  #architecture, #model-of-computation, #theory, #experiments, #code available
  Conference paper  Video  Code
• [25] The Read-Only Semi-External Model
  Guy E. Blelloch, Laxman Dhulipala, Phillip B. Gibbons, Yan Gu, Charlie McGuffey, and Julian Shun
  
  APOCS
   ACM-SIAM Algorithmic Principles of Computer Systems (APoCS), 2021
  
  #architecture, #model-of-computation, #graph, #theory
  Conference paper  
• 2020:
  [24] Optimal (Randomized) Parallel Algorithms in the Binary-Forking Model
  Guy E. Blelloch, Jeremy Fineman, Yan Gu, and Yihan Sun
  
  🏆 Outstanding Paper Award
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020.
  
  #model-of-computation, #theory, #sort, #set/tree-algorithms
  Conference paper  Full version (arXiv)  Video  Full Video  
• [23] 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.
  
  #theory, #geometry, #parallel-ric
  Conference paper  Video  
• [22] 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
  
  #architecture, #system, #graph, #experiments, #code available
  Conference paper  Full version (arXiv)  Code
• [21] Theoretically-Efficient and Practical Parallel DBSCAN
  Yiqiu Wang, Yan Gu, and Julian Shun
  
  SIGMOD
   ACM International Conference on Management of Data (SIGMOD), 2020
  
  #geometry #data-science #experiments #code-available
  Project page  Conference paper  Full version (arXiv)  Video  Code
• [20] Parallelism in Randomized Incremental Algorithms
  Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun
  
  JACM
   Journal of the ACM (JACM)
  
  #theory, #geometry, #graph, #sort, #parallel-ric, #Delaunay triangulation, #SCC, #LE-list
  Conference paper  Journal paper  
• [19] Improved Parallel Cache-Oblivious Algorithms for Dynamic Programming
  Guy Blelloch and Yan Gu
  
  APOCS
   ACM-SIAM Algorithmic Principles of Computer Systems (APoCS), 2020
  
  #dynamic-programming #linear-algebra #architecture #theory
  Conference paper  Full version (arXiv)  
• 2018:
  [18] Algorithmic Building Blocks for Asymmetric Memories
  Yan Gu, Yihan Sun and Guy E. Blelloch
  
  ESA
   European Symposium on Algorithms (ESA), 2018
  
  #architecture, #write-efficient algorithms, #experiments, #hash-table, #set/tree algorithms, #sort, #SSSP
  Conference paper  Full version (arXiv)  
• [17] 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
  
  #theory, #geometry, #parallel ric, #Delaunay triangulation, #kd trees, #interval tree, #priority search tree, #range tree, #augmented trees, #sort
  Conference paper  Full version (arXiv)  
• [16] The Parallel Persistent Memory Model
  Guy Blelloch, Phillip B. Gibbons, Yan Gu, Charles McGuffey, and Julian Shun
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2018
  
  #architecture #scheduling
  Conference paper  
• [15] Implicit Decomposition for Write-Efficient Connectivity Algorithms
  Naama Ben-David, Guy Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, Charles McGuffey, and Julian Shun
  
  IPDPS
   IEEE International Parallel & Distributed Processing Symposium (IPDPS), 2018
  
  #write-efficient algorithms, #graph, #theory, #architecture, #connectivity
  Conference paper  Full version (arXiv)  
• 2017:
  [14] Efficient Construction of Probabilistic Tree Embeddings
  Guy E. Blelloch, Yan Gu, and Yihan Sun
  
  ICALP
   International Colloquium on Automata, Languages, and Programming (ICALP), 2017.
  
  #thoery, #graph, #tree-embedding, #FRT trees, #LE-list, #SSSP, #distance oracle
  Conference paper  Full version (arXiv)  
• 2016:
  [13] Parallel Shortest-paths Using Radius Stepping
  Guy Blelloch, Yan Gu, Yihan Sun, and Kanat Tangwongsan
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016.
  
  #thoery, #graph, #SSSP, #experiments
  Conference paper  
• [12] Parallelism in Randomized Incremental Algorithms
  Guy Blelloch, Yan Gu, Julian Shun and Yihan Sun
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016.
  
  #theory, #geometry, #graph, #sort, #parallel-ric, #Delaunay triangulation, #SCC, #LE-list
  Conference paper  Full version (arXiv)  
• [11] Parallel Algorithms with Asymmetric Read and Write Costs
  Naama Ben-David, Guy Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, Charles McGuffey, and Julian Shun
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016.
  
  #write-efficient algorithms, #architecture, #theory, #model-of-computation, #graph, #geometry, #BFS, list/tree contraction
  Conference paper  
• [10] Efficient Algorithms with Asymmetric Read and Write Costs
  Guy Blelloch, Jeremy T. Fineman, Phillip B. Gibbons Yan Gu, and Julian Shun
  
  ESA
   European Symposium on Algorithms (ESA), 2016
  
  #write-efficient algorithms, #architecture, #theory, #model-of-computation, #graph, #SSSP
  Conference paper  Full version (arXiv)  
• 2015:
  [9] Sorting with Asymmetric Read and Write Costs
  Guy Blelloch, Jeremy Fineman, Phillip Gibbons Yan Gu, and Julian Shun
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2015
  
  #write-efficient algorithms, #architecture, #theory, #model-of-computation, #sort
  Conference paper  Full version (arXiv)  
• [8] A Top-down Parallel Semisort
  Yan Gu, Julian Shun and Yihan Sun and Guy E. Blelloch
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2015
  
  #thoery, #sort, #experiments
  Conference paper  
• [7] Sequential Random Permutation, List Contraction and Tree Contraction are Highly Parallel
  Julian Shun, Yan Gu, Guy Blelloch, Jeremy T. Fineman, and Phillip B. Gibbons.
  
  SODA
   ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 431-448, 2015
  
  #theory, #parallel-ric, #list/tree contraction, #experiments, #code available
  Conference paper  
• [6] Ray Specialized BVH Contraction
  Yan Gu, Yong He, and Guy Blelloch
  
  PG
   Pacific Graphics 2015. Computer Graphics Forum 34(7), 309-318
  
  #graphics, #data-structure, #BVH, #experiments
  Conference paper  Full version  
• 2014:
  [5] Extending the Graphics Pipeline with Adaptive, Multi-Rate Shading
  Yong He, Yan Gu and Kayvon Fatahalian
  
  SIGGRAPH
   SIGGRAPH 2014. ACM Trans. Graph. 33, 4, Article 142 (2014)
  
  #graphics, #architecture, #experiments
  Project page  Conference paper  Video  
• 2013:
  [4] Efficient BVH Construction via Approximate Agglomerative Clustering
  Yan Gu, Yong He, Kayvon Fatahalian, and Guy Blelloch
  
  HPG
   High Performance Graphics 2013, pp. 81-88
  
  #graphics, #data-structure, #BVH, #experiments, #code available
  Project page  Conference paper  Code
• [3] Mixed-Domain Edge-Aware Image Manipulation
  Xian-Ying Li, Yan Gu, Shi-Min Hu, and Ralph R. Martin
  
  TIP
   IEEE Transactions on Image Processing (TIP), 2013, 22(5), 1915-1925
  
  #graphics, #image-processing, #experiments, #code available
  Project page  Conference paper  Code
• [2] Algorithms on Minimizing the Maximum Sensor Movement for Barrier Coverage of a Linear Domain
  Danny Z. Chen, Yan Gu, Jian Li, and Haitao Wang
  
  SWAT
   SWAT 2012. Discrete & Computational Geometry, 2013, 50(2), pp. 374-408
  
  #theory, #geometry
  Full version  
• 2011:
  [1] A Geometric Study of V-style Pop-ups: Theories and Algorithms
  Xian-Ying Li, Tao Ju Yan Gu, and Shi-Min Hu
  
  SIGGRAPH
   SIGGRAPH 2011. ACM Transactions on Graphics , 30(4): article 98
  
  #graphics, #experiments, #code available
  Project page  Conference paper  Video