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]
- 2025:[54] Pkd-tree: Parallel kd-tree with Batch Updates (to appear)
Ziyang Men, Zheqi Shen, Yan Gu, and Yihan Sun
ACM International Conference on Management of Data (SIGMOD), 2025The first work, span, and I/O efficient kdtree algorithm that also support dynamic updates#theory, #data structure, #experiments, #code available - [53]
Parallel Cluster-BFS and Applications to Shortest Paths (to appear)
Letong Wang, Guy Blelloch, Yan Gu, and Yihan Sun
SIAM Symposium on Algorithm Engineering and Experiments (ALENEX), 2025A parallel framework to compute cluster BFS#graph, #experiments, #code available - 2024:[52] Parallel and (Nearly) Work-Efficient Dynamic Programming
Xiangyun Ding, Yan Gu, and Yihan Sun🏆 Outstanding Paper Award (Best Paper Finalist)ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2024A parallel framework to parallelize dynamic programming with optimizations such as sparsity and monotonicity#theory, #dynamic programming, #experiments, #code availableConference paper Full version (arXiv) Code - [51]
PASGAL: Parallel And Scalable Graph Algorithm Library
Xiaojun Dong, Yan Gu, Yihan Sun, and Letong Wang
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2024A high-performance parallel and scalable graph algorithm library#graph, #library, #experiments, #code availableConference paper Full version (arXiv) Code - [50]
Optimal Parallel Algorithms for Dendrogram Computation and Single-Linkage Clustering
Laxman Dhulipala, Xiaojun Dong, Kishen Gowda, and Yan Gu
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2024Theoretically and practically efficient parallel algorithms for computing dendrogram and single-linkage clustering#data science, #theory, #data structure, #experiments, #code availableConference paper Full version (arXiv) Code - [49]
Fast and Space-Efficient Parallel Algorithms for Influence Maximization
Letong Wang, Xiangyun Ding, Yan Gu, and Yihan Sun
Processings of the VLDB Endowment, 2024Fast, highly parallel and space-efficient solutions for influence maximization#data science, #theory, #data structure, #experiments, #code availableConference paper Full version (arXiv) Code - [48]
Parallel Integer Sort: Theory and Practice
Xiaojun Dong, Laxman Dhulipala, Yan Gu, and Yihan Sun
ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2024Highly parallel and fast integer sort, with new theoretical analysis#theory #sort, #experiments, #code availableConference paper Full version (arXiv) Code - [47]
ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms
Magdalen Dobson, Zheqi Shen, Guy Blelloch, Laxman Dhulipala, Yan Gu, Harsha Simhadri, and Yihan Sun
ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2024The first billion-scale software for ANNS, with additional features such as determinism and high parallelism#machine learning, #experiments, #code available, #graphConference paper Full version (arXiv) Code - 2023:[46] Efficient Parallel Output-Sensitive Edit Distance
Xiangyun Ding, Xiaojun Dong, Yan Gu, Youzhe Liu, and Yihan Sun🏆 Best Paper AwardEuropean Symposium on Algorithms (ESA), 2023Parallel output-sensitive edit distance#string, #experiments, #code availableConference 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
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2023Highly parallel and fast semisort software#sort, #experiments, #code availableConference 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
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2023Simple and work-efficient parallel algorithm of LIS, and parallel vEB tree#LIS, #theory, #experiments, #code availableConference 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
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2023Parallel trie for PIM#architecture, #data structure, #set/tree algorithmsConference paper - [42]
Parallel Strong Connectivity Based on Faster Reachability
Letong Wang, Xiaojun Dong, Yan Gu, and Yihan Sun
ACM International Conference on Management of Data (SIGMOD), 2023A consistently fast parallel SCC algorithm/implementation#graph, #theory, #experiments, #code availableConference paper Full version (arXiv) Code - [41]
Provably Fast and Space-Efficient Parallel Biconnectivity
Xiaojun Dong, Letong Wang, Yan Gu, and Yihan Sun🏆 Best Paper AwardACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2023The first work-, span-, and space-efficient BCC algorithm with fast practical performance#graph, #theory, #experiments, #code availableConference 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-UpProcessings of the VLDB Endowment, 2023A consistent high-performance search tree structure on PIM architecture#architecture, #data structure, #set/tree algorithms, #experiments, #code availableConference 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 2022, (journal version, published in ACM Transactions on Graphics (TOG))A high-performance rendering framework#geometry, #graphics, #experiments, #code availableConference paper - [38]
ParGeo: A Library for Parallel Computational Geometry
Yiqiu Wang, Rahul Yesantharao, Shangdi Yu, Laxman Dhulipala, Yan Gu, and Julian Shun
European Symposium on Algorithms (ESA), 2022A library for commonly used parallel algorithms in computational geometry#geometry, #data-science, #experiments, #code availableConference paper Full version (arXiv) Code - [37]
Parallel Cover Trees and Applications
Yan Gu, Zachary Napier, Yihan Sun, and Letong Wang
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2022Parallel cover tree data structure for nearest neighbor search and other applications#cover tree, #data structure, #agglomerative clusteringConference paper - [36]
Many Sequential Iterative Algorithms Can Be Parallel and (Nearly) Work-efficient
Zheqi Shen, Zijin Wan, Yan Gu, and Yihan Sun
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2022Parallelizing classic sequential iterative algorithms, including activity selection, LIS, Huffman tree, Dijkstra's algorithm, MIS, etc.#paralleling sequential iterative algorithms, #data structure, #LIS, #MIS, #SSSPConference paper Full version (arXiv) - [35]
PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections
Laxman Dhulipala, Guy Blelloch, Yan Gu, and Yihan Sun
ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2022A space and theoretically efficient data structure that support broad functionalityConference paper Full version (arXiv) - [34]
POSTER: ParGeo: A Library for Parallel Computational Geometry
Yiqiu Wang, Shagndi Yu, Laxman Dhulipala, Yan Gu, and Julian Shun
ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 2022A Library for Parallel Computational Geometry#geometry, #experiments, #code avaiableConference paper - [33]
Analysis of Work-Stealing and Parallel Cache Complexity
Yan Gu, Zachary Napier, and Yihan Sun
ACM-SIAM Algorithmic Principles of Computer Systems (APoCS), 2022New simplified analysis for RWS, and improved parallel cache bounds#theoryConference 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
Processings of the VLDB EndowmentParallel algorithms for hierarchical agglomerative clustering (HAC)#geometry, #data-science, #experiments, #code availableConference paper Full version (arXiv) - [31]
Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths
Xiaojun Dong, Yan Gu, Yihan Sun, and Yunming Zhang
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2021Theoretical and practical parallel SSSP algorithms#graph, #SSSP, #theory, #experiments, #code availableConference 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
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2021Model and algorithms (skiplists) for PIM architecture#architecture, #model-of-computation, #data structure, #set/tree algorithmsConference paper Video - [29]
GeoGraph: A Framework for Graph Processing on Geometric Data
Yiqiu Wang, Shangdi Yu, Laxman Dhulipala, Yan Gu, and Julian Shun
ACM SIGOPS Operating Systems Review, Vol. 55 Issue 1, pp. 38-46, 2021Enable parallel graph processing for geometric data#system #graph #geometryConference paper Code - [28]
Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering
Yiqiu Wang, Shangdi Yu, Yan Gu, and Julian Shun
ACM International Conference on Management of Data (SIGMOD), 2021As the title says#geometry, #data-science, #theory, #experiments, #code availableConference 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
ACM Symposium on Computational Geometry (SoCG), 2021#geometry, #theory, #experiments, #code availableConference paper Full version (arXiv) Code - [26]
Parallel In-Place Algorithms: Theory and Practice
Yan Gu, Omar Obeya, and Julian Shun
ACM-SIAM Algorithmic Principles of Computer Systems (APoCS), 2021#architecture, #model-of-computation, #theory, #experiments, #code availableConference 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
ACM-SIAM Algorithmic Principles of Computer Systems (APoCS), 2021#architecture, #model-of-computation, #graph, #theoryConference paper - 2020:[24] Optimal (Randomized) Parallel Algorithms in the Binary-Forking Model
Guy E. Blelloch, Jeremy Fineman, Yan Gu, and Yihan Sun🏆 Outstanding Paper AwardACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020.#model-of-computation, #theory, #sort, #set/tree-algorithmsConference 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
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020.#theory, #geometry, #parallel-ricConference 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)Processings of the VLDB Endowment 13(9), 2020#architecture, #system, #graph, #experiments, #code availableConference paper Full version (arXiv) Code - [21]
Theoretically-Efficient and Practical Parallel DBSCAN
Yiqiu Wang, Yan Gu, and Julian Shun
ACM International Conference on Management of Data (SIGMOD), 2020#geometry #data-science #experiments #code-availableProject page Conference paper Full version (arXiv) Video Code - [20]
Parallelism in Randomized Incremental Algorithms
Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun
Journal of the ACM (JACM)#theory, #geometry, #graph, #sort, #parallel-ric, #Delaunay triangulation, #SCC, #LE-listConference paper Journal paper - [19]
Improved Parallel Cache-Oblivious Algorithms for Dynamic Programming
Guy Blelloch and Yan Gu
ACM-SIAM Algorithmic Principles of Computer Systems (APoCS), 2020#dynamic-programming #linear-algebra #architecture #theoryConference paper Full version (arXiv) - 2018:[18] Algorithmic Building Blocks for Asymmetric Memories
Yan Gu, Yihan Sun and Guy E. Blelloch
European Symposium on Algorithms (ESA), 2018#architecture, #write-efficient algorithms, #experiments, #hash-table, #set/tree algorithms, #sort, #SSSPConference 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
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, #sortConference paper Full version (arXiv) - [16]
The Parallel Persistent Memory Model
Guy Blelloch, Phillip B. Gibbons, Yan Gu, Charles McGuffey, and Julian Shun
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2018#architecture #schedulingConference 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
IEEE International Parallel & Distributed Processing Symposium (IPDPS), 2018#write-efficient algorithms, #graph, #theory, #architecture, #connectivityConference paper Full version (arXiv) - 2017:[14] Efficient Construction of Probabilistic Tree Embeddings
Guy E. Blelloch, Yan Gu, and Yihan Sun
International Colloquium on Automata, Languages, and Programming (ICALP), 2017.#thoery, #graph, #tree-embedding, #FRT trees, #LE-list, #SSSP, #distance oracleConference paper Full version (arXiv) - 2016:[13] Parallel Shortest-paths Using Radius Stepping
Guy Blelloch, Yan Gu, Yihan Sun, and Kanat Tangwongsan
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016.#thoery, #graph, #SSSP, #experimentsConference paper - [12]
Parallelism in Randomized Incremental Algorithms
Guy Blelloch, Yan Gu, Julian Shun and Yihan Sun
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016.#theory, #geometry, #graph, #sort, #parallel-ric, #Delaunay triangulation, #SCC, #LE-listConference 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
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016.#write-efficient algorithms, #architecture, #theory, #model-of-computation, #graph, #geometry, #BFS, list/tree contractionConference paper - [10]
Efficient Algorithms with Asymmetric Read and Write Costs
Guy Blelloch, Jeremy T. Fineman, Phillip B. Gibbons Yan Gu, and Julian Shun
European Symposium on Algorithms (ESA), 2016#write-efficient algorithms, #architecture, #theory, #model-of-computation, #graph, #SSSPConference paper Full version (arXiv) - 2015:[9] Sorting with Asymmetric Read and Write Costs
Guy Blelloch, Jeremy Fineman, Phillip Gibbons Yan Gu, and Julian Shun
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2015#write-efficient algorithms, #architecture, #theory, #model-of-computation, #sortConference paper Full version (arXiv) - [8]
A Top-down Parallel Semisort
Yan Gu, Julian Shun and Yihan Sun and Guy E. Blelloch
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2015#thoery, #sort, #experimentsConference 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.
ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 431-448, 2015#theory, #parallel-ric, #list/tree contraction, #experiments, #code availableConference paper - [6]
Ray Specialized BVH Contraction
Yan Gu, Yong He, and Guy Blelloch
Pacific Graphics 2015. Computer Graphics Forum 34(7), 309-318#graphics, #data-structure, #BVH, #experimentsConference paper Full version - 2014:[5] Extending the Graphics Pipeline with Adaptive, Multi-Rate Shading
Yong He, Yan Gu and Kayvon Fatahalian
SIGGRAPH 2014. ACM Trans. Graph. 33, 4, Article 142 (2014)#graphics, #architecture, #experimentsProject page Conference paper Video - 2013:[4] Efficient BVH Construction via Approximate Agglomerative Clustering
Yan Gu, Yong He, Kayvon Fatahalian, and Guy Blelloch
High Performance Graphics 2013, pp. 81-88#graphics, #data-structure, #BVH, #experiments, #code availableProject page Conference paper Code - [3]
Mixed-Domain Edge-Aware Image Manipulation
Xian-Ying Li, Yan Gu, Shi-Min Hu, and Ralph R. Martin
IEEE Transactions on Image Processing (TIP), 2013, 22(5), 1915-1925#graphics, #image-processing, #experiments, #code availableProject 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 2012. Discrete & Computational Geometry, 2013, 50(2), pp. 374-408#theory, #geometryFull 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 2011. ACM Transactions on Graphics , 30(4): article 98#graphics, #experiments, #code availableProject page Conference paper Video