publications by year

[View our publications by topic]

• 2025:
  [44] Optimal Batch-Dynamic kd-trees for Processing-in-Memory with Applications (To Appear)
  Yiwei Zhao, Hongbo Kang, Yan Gu*, Guy E. Blelloch, Laxman Dhulipala, Charles McGuffey, and Phillip B. Gibbons
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2025    [BibTeX]
  @inproceedings{ Zhao2025Optimal,
  title = { Optimal Batch-Dynamic kd-trees for Processing-in-Memory with Applications (To Appear) },
  author = { Zhao, Yiwei and  Kang, Hongbo and  Gu, Yan and  Blelloch, Guy E. and  Dhulipala, Laxman and  McGuffey, Charles and  Gibbons, Phillip B.},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2025 }
  }

  [copy]
  
  Paper   
• [43] Parallel Point-to-Point Shortest Paths and Batch Queries (To Appear)
  Xiaojun Dong*, Andy Li*, Yan Gu*, and Yihan Sun*
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2025    [BibTeX]
  @inproceedings{ Dong2025Parallel,
  title = { Parallel Point-to-Point Shortest Paths and Batch Queries (To Appear) },
  author = { Dong, Xiaojun and  Li, Andy and  Gu, Yan and  Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2025 }
  }

  [copy]
  
  
    DOI:
  10.1145/3694906.3743311    [copy]
  
    Software Library:
  Orionet: Parallel Single and Batch PPSP  [Github]
  Paper   ArXiV  Code  
• [42] New Algorithms for Incremental Minimum Spanning Trees and Temporal Graph Applications (To Appear)
  Xiangyun Ding*, Yan Gu*, and Yihan Sun*
  
  ACDA
   SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2025    [BibTeX]
  @inproceedings{ Ding2025New,
  title = { New Algorithms for Incremental Minimum Spanning Trees and Temporal Graph Applications (To Appear) },
  author = { Ding, Xiangyun and  Gu, Yan and  Sun, Yihan},
  booktitle = {SIAM Conference on Applied and Computational Discrete Algorithms (ACDA)},
  year = { 2025 }
  }

  [copy]
  
  
    Software Library:
  AM-tree: Anti-Monoply tree for incremental MST and temporal connectivity  [Github]
  Paper   Code  
• [41] Parallel Contraction Hierarchies Can Be Efficient and Scalable
  Zijin Wan*, Xiaojun Dong*, Letong Wang*, Enzuo Zhu*, Yan Gu*, and Yihan Sun*
  
  🏆 Best Paper Finalist!
  ICS
   International Conference on Supercomputing (ICS), 2025    [BibTeX]
  @inproceedings{ Wan2025Parallel,
  title = { Parallel Contraction Hierarchies Can Be Efficient and Scalable },
  author = { Wan, Zijin and  Dong, Xiaojun and  Wang, Letong and  Zhu, Enzuo and  Gu, Yan and  Sun, Yihan},
  booktitle = {International Conference on Supercomputing (ICS)},
  year = { 2025 }
  }

  [copy]
  
  
    DOI:
  10.1145/3721145.3725744    [copy]
  
    Software Library:
  SPoCH: Scalable Parallelization of Contraction Hierarchies  [Github]
  
  HOPC
   Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2025
  Paper   ArXiV  Code  Slides  
• [40] Parallel k-Core Decomposition: Theory and Practice
  Youzhe Liu*, Xiaojun Dong*, Yan Gu*, and Yihan Sun*
  
  SIGMOD
   ACM Special Interest Group on Management of Data (SIGMOD), 2025    [BibTeX]
  @inproceedings{ Liu2025Parallel,
  title = { Parallel k-Core Decomposition: Theory and Practice },
  author = { Liu, Youzhe and  Dong, Xiaojun and  Gu, Yan and  Sun, Yihan},
  booktitle = {ACM Special Interest Group on Management of Data (SIGMOD)},
  year = { 2025 }
  }

  [copy]
  
  
    DOI:
  10.1145/3725332    [copy]
  
    Software Library:
  Parallel k-core implementation, integrated in PASGAL  [Github]
  
  ACDA
   Poster and oral presentation at the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2025
  
  HOPC
   Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2025
  Paper   ArXiV  Code  Slides  
• [39] Pkd-tree: Parallel kd-tree with Batch Updates
  Ziyang Men*, Zheqi Shen*, Yan Gu*, and Yihan Sun*
  
  SIGMOD
   ACM Special Interest Group on Management of Data (SIGMOD), 2025    [BibTeX]
  @inproceedings{ Men2025Pkd-tree:,
  title = { Pkd-tree: Parallel kd-tree with Batch Updates },
  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]
  
  
    DOI:
  10.1145/3709712    [copy]
  
    Software Library:
  Pkd-tree: Parallel kd-tree  [Github]
  
  ACDA
   Poster and oral presentation at the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2025
  
  HOPC
   Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2025
  Paper   ArXiV  Code  Slides  Poster  
• [38] Parallel Cluster-BFS and Applications to Shortest Paths
  Letong Wang*, Guy E. Blelloch, Yan Gu*, and Yihan Sun*
  
  ALENEX
   Algorithm Engineering and Experiments (ALENEX), 2025    [BibTeX]
  @inproceedings{ Wang2025Parallel,
  title = { Parallel Cluster-BFS and Applications to Shortest Paths },
  author = { Wang, Letong and  Blelloch, Guy E. and  Gu, Yan and  Sun, Yihan},
  booktitle = {Algorithm Engineering and Experiments (ALENEX)},
  year = { 2025 }
  }

  [copy]
  
  
    DOI:
  10.1137/1.9781611978339.4    [copy]
  
    Software Library:
  CBFS: Cluster Breadth-First Search  [Zenodo]
  Paper   ArXiV  Code  Slides  
• 2024:
  [37] Parallel and (Nearly) Work-Efficient Dynamic Programming
  Xiangyun Ding*, Yan Gu*, and Yihan Sun*
  
  🏆 Outstanding Paper Award (Best paper finalist)!
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2024    [BibTeX]
  @inproceedings{ Ding2024Parallel,
  title = { Parallel and (Nearly) Work-Efficient Dynamic Programming },
  author = { Ding, Xiangyun and  Gu, Yan and  Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2024 }
  }

  [copy]
  
  
    Software Library:
  Parallel Work-Efficient Dynamic Programming  [Github]
  Paper   ArXiV  Code  Slides  
• [36] Brief Announcement: PASGAL: Parallel And Scalable Graph Algorithm Library
  Xiaojun Dong*, Yan Gu*, Yihan Sun*, and Letong Wang*
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2024    [BibTeX]
  @inproceedings{ Dong2024Brief,
  title = { Brief Announcement: PASGAL: Parallel And Scalable Graph Algorithm Library },
  author = { Dong, Xiaojun and  Gu, Yan and  Sun, Yihan and  Wang, Letong},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2024 }
  }

  [copy]
  
  
    Software Library:
  PASGAL: Parallel And Scalable Graph Algorithm Library  [Github]
  Paper   ArXiV  Code  Slides  Poster  
• [35] Optimal Parallel Algorithms for Dendrogram Computation and Single-Linkage Clustering
  Laxman Dhulipala, Xiaojun Dong*, , and Yan Gu*
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2024    [BibTeX]
  @inproceedings{ Dhulipala2024Optimal,
  title = { Optimal Parallel Algorithms for Dendrogram Computation and Single-Linkage Clustering },
  author = { Dhulipala, Laxman and  Dong, Xiaojun and  , and  Gu, Yan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2024 }
  }

  [copy]
  
  
    Software Library:
  Parallel Single-linkage Dendrogram Construction Algorithm  [Github]
  Paper   ArXiV  Code  
• [34] BYO: A Unified Framework for Benchmarking Large-Scale Graph Containers
  Brian Wheatman, Xiaojun Dong*, Zheqi Shen*, Laxman Dhulipala, Jakub Łącki, Prashant Pandey, and Helen Xu
  
  VLDB
   International Conference on Very Large Data Bases (VLDB), 2024    [BibTeX]
  @inproceedings{ Wheatman2024BYO:,
  title = { BYO: A Unified Framework for Benchmarking Large-Scale Graph Containers },
  author = { Wheatman, Brian and  Dong, Xiaojun and  Shen, Zheqi and  Dhulipala, Laxman and  Łącki, Jakub and  Pandey, Prashant and  Xu, Helen},
  booktitle = {International Conference on Very Large Data Bases (VLDB)},
  year = { 2024 }
  }

  [copy]
  
  
    DOI:
  10.14778/3665844.3665859    [copy]
  
    Software Library:
  BYO: A Unified Framework for Benchmarking Large-Scale Graph Containers  [Github]
  Paper   ArXiV  Code  
• [33] Teaching Parallel Algorithms Using the Binary-Forking Model
  Guy E. Blelloch, Yan Gu*, and Yihan Sun*
  
  EduPar
   (@IPDPS) NSF/TCPP Workshop on Parallel and Distributed Computing Education (EduPar), 2024    [BibTeX]
  @inproceedings{ Blelloch2024Teaching,
  title = { Teaching Parallel Algorithms Using the Binary-Forking Model },
  author = { Blelloch, Guy E. and  Gu, Yan and  Sun, Yihan},
  booktitle = {(@IPDPS) NSF/TCPP Workshop on Parallel and Distributed Computing Education (EduPar)},
  year = { 2024 }
  }

  [copy]
  
  Paper   Slides  
• [32] ParlayANN: Scalable and Deterministic Parallel Graph-Based Algorithms for Approximate Nearest Neighbor Search
  Magdalen Dobson Manohar, Zheqi Shen*, , Laxman Dhulipala, Yan Gu*, Harsha Simhadri, and Yihan Sun*
  
  PPoPP
   ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2024    [BibTeX]
  @inproceedings{ Manohar2024ParlayANN:,
  title = { ParlayANN: Scalable and Deterministic Parallel Graph-Based Algorithms for Approximate Nearest Neighbor Search },
  author = { Manohar, Magdalen Dobson and  Shen, Zheqi and  , and  Dhulipala, Laxman and  Gu, Yan and  Simhadri, Harsha and  Sun, Yihan},
  booktitle = {ACM Symposium on Principles and Practice of Parallel Programming (PPoPP)},
  year = { 2024 }
  }

  [copy]
  
  
    DOI:
  10.1145/3627535.3638475    [copy]
  
    Software Library:
  ParlayANN: Parallel Graph-Based Algorithms for Approximate Nearest Neighbor Search  [Github]
  Paper   ArXiV  Code  
• [31] Parallel Integer Sort: Theory and Practice
  Xiaojun Dong*, Laxman Dhulipala, Yan Gu*, and Yihan Sun*
  
  PPoPP
   ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2024    [BibTeX]
  @inproceedings{ Dong2024Parallel,
  title = { Parallel Integer Sort: Theory and Practice },
  author = { Dong, Xiaojun and  Dhulipala, Laxman and  Gu, Yan and  Sun, Yihan},
  booktitle = {ACM Symposium on Principles and Practice of Parallel Programming (PPoPP)},
  year = { 2024 }
  }

  [copy]
  
  
    DOI:
  10.1145/3627535.3638483    [copy]
  
    Software Library:
  DovetailSort: Parallel Integer Sort  [Github]
  
  HOPC
   Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2024
  Paper   ArXiV  Code  Slides  Poster  
• [30] Fast and Space-Efficient Parallel Algorithms for Influence Maximization
  Letong Wang*, Xiangyun Ding*, Yan Gu*, and Yihan Sun*
  
  VLDB
   International Conference on Very Large Data Bases (VLDB), 2024    [BibTeX]
  @inproceedings{ Wang2024Fast,
  title = { Fast and Space-Efficient Parallel Algorithms for Influence Maximization },
  author = { Wang, Letong and  Ding, Xiangyun and  Gu, Yan and  Sun, Yihan},
  booktitle = {International Conference on Very Large Data Bases (VLDB)},
  year = { 2024 }
  }

  [copy]
  
  
    DOI:
  10.14778/3632093.3632104    [copy]
  
    Software Library:
  PaC-IM: Parallel and Compressed Influence Maximization  [Github]
  
  HOPC
   Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2024
  Paper   ArXiV  Code  Poster  
• 2023:
  [29] 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    [BibTeX]
  @inproceedings{ Ding2023Efficient,
  title = { Efficient Parallel Output-Sensitive Edit Distance },
  author = { Ding, Xiangyun and  Dong, Xiaojun and  Gu, Yan and  Liu, Youzhe and  Sun, Yihan},
  booktitle = {European Symposium on Algorithms (ESA)},
  year = { 2023 }
  }

  [copy]
  
  
    DOI:
  10.4230/LIPIcs.ESA.2023.40    [copy]
  
    Software Library:
  Parallel Output-Sensitive Edit Distance  [Github]
  
  HOPC
   Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2024
  Paper   ArXiV  Code  Slides  
• [28] 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    [BibTeX]
  @inproceedings{ Dong2023High-Performance,
  title = { High-Performance and Flexible Parallel Algorithms for Semisort and Related Problems },
  author = { Dong, Xiaojun and  Wu, Yunshu and  Wang, Zhongqi and  Dhulipala, Laxman and  Gu, Yan and  Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2023 }
  }

  [copy]
  
  
    DOI:
  10.1145/3558481.3591071    [copy]
  
    Software Library:
  Parallel Semisort  [Github]
  Paper   ArXiV  Code  Slides  
• [27] 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{ Gu2023Parallel,
  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]
  
  
    DOI:
  10.1145/3558481.3591069    [copy]
  
    Software Library:
  Parallel Longest Increasing Subsequence  [Github]
  Paper   ArXiV  Code  Slides  
• [26] 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{ Wang2023Parallel,
  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]
  
  
    DOI:
  10.1145/3589259    [copy]
  
    Software Library:
  Parallel Strongly Connected Components (SCC), integrated in PASGAL  [Github]
  
  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
  Paper   ArXiV  Code  Slides  Poster  
• [25] 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    [BibTeX]
  @inproceedings{ Dong2023Provably,
  title = { Provably Fast and Space-Efficient Parallel Biconnectivity },
  author = { Dong, Xiaojun and  Wang, Letong and  Gu, Yan and  Sun, Yihan},
  booktitle = {ACM Symposium on Principles and Practice of Parallel Programming (PPoPP)},
  year = { 2023 }
  }

  [copy]
  
  
    DOI:
  10.1145/3572848.3577483    [copy]
  
    Software Library:
  Parallel Biconnected Components (BCC), integrated in PASGAL  [Github]
  
  ACDA
   Poster and oral presentation at the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2023
  
  HOPC
   Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2023
  Paper   ArXiV  Code  Poster  
• 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{ Zhang2022Bi-directional,
  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]
  
  
    DOI:
  10.1145/3538712.3538730    [copy]
  
    Software Library:
  Bi-directional LSM Tree  [Github]
  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{ Gu2022Parallel,
  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]
  
  
    DOI:
  10.1145/3490148.3538581    [copy]
  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{ Shen2022Many,
  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]
  
  
    DOI:
  10.1145/3490148.3538574    [copy]
  
    Software Library:
  Parallel Dynamic Programming (DP) and greedy algorithms  [Github]
  Paper   ArXiV  Slides  
• [21] PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections
  Laxman Dhulipala, Guy E. Blelloch, Yan Gu*, and Yihan Sun*
  
  PLDI
   ACM Conference on Programming Language Design and Implementation (PLDI), 2022    [BibTeX]
  @inproceedings{ Dhulipala2022PaC-trees:,
  title = { PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections },
  author = { Dhulipala, Laxman and  Blelloch, Guy E. and  Gu, Yan and  Sun, Yihan},
  booktitle = {ACM Conference on Programming Language Design and Implementation (PLDI)},
  year = { 2022 }
  }

  [copy]
  
  
    DOI:
  10.1145/3519939.3523733    [copy]
  
    Software Library:
  CPAM: Compressed Parallel Augmented Maps  [Github]
  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{ Blelloch2022Joinable,
  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]
  
  
    DOI:
  10.1145/3512769    [copy]
  
    Software Library:
  PAM: Parallel Augmented Maps  [Github]
  Paper   Code  
• [19] POSTER: The Problem-Based Benchmark Suite (PBBS), V2
  Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, Magdalen Dobson Manohar, and Yihan Sun*
  
  PPoPP
   ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2022    [BibTeX]
  @inproceedings{ Anderson2022POSTER:,
  title = { POSTER: The Problem-Based Benchmark Suite (PBBS), V2 },
  author = { Anderson, Daniel and  Blelloch, Guy E. and  Dhulipala, Laxman and  Manohar, Magdalen Dobson and  Sun, Yihan},
  booktitle = {ACM Symposium on Principles and Practice of Parallel Programming (PPoPP)},
  year = { 2022 }
  }

  [copy]
  
  
    DOI:
  10.1145/3503221.3508422    [copy]
  
    Software Library:
  PBBS: The Problem-Based Benchmark Suite  [Github]
  Paper   Code  
• [18] 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    [BibTeX]
  @inproceedings{ Gu2022Analysis,
  title = { Analysis of Work-Stealing and Parallel Cache Complexity },
  author = { Gu, Yan and  Napier, Zachary and  Sun, Yihan},
  booktitle = {ACM-SIAM Algorithmic Principles of Computer Systems (APOCS)},
  year = { 2022 }
  }

  [copy]
  
  
    DOI:
  10.1137/1.9781611977059.4    [copy]
  Paper   
• 2021:
  [17] ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain
  Shangdi Yu, Yiqiu Wang, Yan Gu*, Laxman Dhulipala, and Julian Shun
  
  VLDB
   International Conference on Very Large Data Bases (VLDB), 2021    [BibTeX]
  @inproceedings{ Yu2021ParChain:,
  title = { ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain },
  author = { Yu, Shangdi and  Wang, Yiqiu and  Gu, Yan and  Dhulipala, Laxman and  Shun, Julian},
  booktitle = {International Conference on Very Large Data Bases (VLDB)},
  year = { 2021 }
  }

  [copy]
  
  
    Software Library:
  ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain  [Github]
  Paper   Code  
• [16] 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{ Kang2021The,
  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]
  
  Paper   Video  
• [15] Space and Time Bounded Multiversion Garbage Collection
  Naama Ben-David, Guy E. Blelloch, , , Yihan Sun*, and Yuanhao Wei
  
  DISC
   International Symposium on Distributed Computing (DISC), 2021    [BibTeX]
  @inproceedings{ Ben-David2021Space,
  title = { Space and Time Bounded Multiversion Garbage Collection },
  author = { Ben-David, Naama and  Blelloch, Guy E. and  , and  , and  Sun, Yihan and  Wei, Yuanhao},
  booktitle = {International Symposium on Distributed Computing (DISC)},
  year = { 2021 }
  }

  [copy]
  
  
    DOI:
  10.4230/LIPIcs.DISC.2021.12    [copy]
  Paper   Video  ArXiV  Slides  
• [14] 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{ Dong2021Efficient,
  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]
  
  
    DOI:
  10.1145/3409964.3461782    [copy]
  
    Software Library:
  Rho-Stepping: Parallel single-source shortes paths, integrated in PASGAL  [Github]
  Paper   Video  ArXiV  Code  Slides  
• [13] 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 (SIGOPS-OSR), 2021    [BibTeX]
  @inproceedings{ Wang2021GeoGraph:,
  title = { GeoGraph: A Framework for Graph Processing on Geometric Data },
  author = { Wang, Yiqiu and  Yu, Shangdi and  Dhulipala, Laxman and  Gu, Yan and  Shun, Julian},
  booktitle = {ACM SIGOPS Operating Systems Review (SIGOPS-OSR)},
  year = { 2021 }
  }

  [copy]
  
  
    Software Library:
  GeoGraph: A Framework for Graph Processing on Geometric Data  [Github]
  Paper   Code  
• [12] Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering
  Yiqiu Wang, Shangdi Yu, Yan Gu*, and Julian Shun
  
  SIGMOD
   ACM Special Interest Group on Management of Data (SIGMOD), 2021    [BibTeX]
  @inproceedings{ Wang2021Fast,
  title = { Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering },
  author = { Wang, Yiqiu and  Yu, Shangdi and  Gu, Yan and  Shun, Julian},
  booktitle = {ACM Special Interest Group on Management of Data (SIGMOD)},
  year = { 2021 }
  }

  [copy]
  
  
    Software Library:
  Parallel HDBSCAN  [Github]
  Paper   Video  ArXiV  Code  
• [11] 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    [BibTeX]
  @inproceedings{ Wang2021An,
  title = { An Experimental Study of a New Parallel Batch-Dynamic Closest Pair Data Structure },
  author = { Wang, Yiqiu and  Yu, Shangdi and  Gu, Yan and  Shun, Julian},
  booktitle = {ACM Symposium on Computational Geometry (SoCG)},
  year = { 2021 }
  }

  [copy]
  
  
    Software Library:
  Parallel Batch-Dynamic Closest Pair  [Github]
  Paper   ArXiV  Code  
• [10] Parallel In-Place Algorithms: Theory and Practice
  Yan Gu*, , and Julian Shun
  
  APOCS
   ACM-SIAM Algorithmic Principles of Computer Systems (APOCS), 2021    [BibTeX]
  @inproceedings{ Gu2021Parallel,
  title = { Parallel In-Place Algorithms: Theory and Practice },
  author = { Gu, Yan and  , and  Shun, Julian},
  booktitle = {ACM-SIAM Algorithmic Principles of Computer Systems (APOCS)},
  year = { 2021 }
  }

  [copy]
  
  
    Software Library:
  Parallel In-Place (PIP) Algorithms  [Github]
  Paper   Video  ArXiV  Code  
• [9] The Read-Only Semi-External Model
  Guy E. Blelloch, Laxman Dhulipala, Phillip B. Gibbons, Yan Gu*, Charles McGuffey, and Julian Shun
  
  APOCS
   ACM-SIAM Algorithmic Principles of Computer Systems (APOCS), 2021    [BibTeX]
  @inproceedings{ Blelloch2021The,
  title = { The Read-Only Semi-External Model },
  author = { Blelloch, Guy E. and  Dhulipala, Laxman and  Gibbons, Phillip B. and  Gu, Yan and  McGuffey, Charles and  Shun, Julian},
  booktitle = {ACM-SIAM Algorithmic Principles of Computer Systems (APOCS)},
  year = { 2021 }
  }

  [copy]
  
  Paper   
• [8] 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{ Wei2021Constant-Time,
  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]
  
  
    DOI:
  10.1145/3437801.3441602    [copy]
  
    Software Library:
  VCASLib  [Github]
  Paper   Video  ArXiV  Code  
• 2020:
  [7] Optimal (Randomized) Parallel Algorithms in the Binary-Forking Model
  Guy E. Blelloch, Jeremy T. Fineman, Yan Gu*, and Yihan Sun*
  
  🏆 Best Paper Candidate!
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020    [BibTeX]
  @inproceedings{ Blelloch2020Optimal,
  title = { Optimal (Randomized) Parallel Algorithms in the Binary-Forking Model },
  author = { Blelloch, Guy E. and  Fineman, Jeremy T. and  Gu, Yan and  Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2020 }
  }

  [copy]
  
  
    DOI:
  10.1145/3350755.3400227    [copy]
  Paper   Video  Slides  
• [6] 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    [BibTeX]
  @inproceedings{ Blelloch2020Randomized,
  title = { Randomized Incremental Convex Hull is Highly Parallel },
  author = { Blelloch, Guy E. and  Gu, Yan and  Shun, Julian and  Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2020 }
  }

  [copy]
  
  
    DOI:
  10.1145/3350755.3400255    [copy]
  Paper   Video  Slides  
• [5] Parallelism in Randomized Incremental Algorithms
  Guy E. Blelloch, Yan Gu*, Julian Shun, and Yihan Sun*
  
  JACM
   Journal of the ACM (JACM), 2020    [BibTeX]
  @inproceedings{ Blelloch2020Parallelism,
  title = { Parallelism in Randomized Incremental Algorithms },
  author = { Blelloch, Guy E. and  Gu, Yan and  Shun, Julian and  Sun, Yihan},
  booktitle = {Journal of the ACM (JACM)},
  year = { 2020 }
  }

  [copy]
  
  
    DOI:
  10.1145/3402819    [copy]
  Paper   
• [4] 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
   International Conference on Very Large Data Bases (VLDB), 2020    [BibTeX]
  @inproceedings{ Dhulipala2020Sage:,
  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 = {International Conference on Very Large Data Bases (VLDB)},
  year = { 2020 }
  }

  [copy]
  
  
    Software Library:
  SAGE: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs  [Github]
  Paper   ArXiV  Code  
• [3] Theoretically-Efficient and Practical Parallel DBSCAN
  Yiqiu Wang, Yan Gu*, and Julian Shun
  
  SIGMOD
   ACM Special Interest Group on Management of Data (SIGMOD), 2020    [BibTeX]
  @inproceedings{ Wang2020Theoretically-Efficient,
  title = { Theoretically-Efficient and Practical Parallel DBSCAN },
  author = { Wang, Yiqiu and  Gu, Yan and  Shun, Julian},
  booktitle = {ACM Special Interest Group on Management of Data (SIGMOD)},
  year = { 2020 }
  }

  [copy]
  
  
    Software Library:
  Parallel DBSCAN  [Github]
  Paper   Video  ArXiV  Code  Page  
• [2] Improved Parallel Cache-Oblivious Algorithms for Dynamic Programming
  Yan Gu*, and Guy E. Blelloch
  
  APOCS
   ACM-SIAM Algorithmic Principles of Computer Systems (APOCS), 2020    [BibTeX]
  @inproceedings{ Gu2020Improved,
  title = { Improved Parallel Cache-Oblivious Algorithms for Dynamic Programming },
  author = { Gu, Yan and  Blelloch, Guy E.},
  booktitle = {ACM-SIAM Algorithmic Principles of Computer Systems (APOCS)},
  year = { 2020 }
  }

  [copy]
  
  Paper   ArXiV  
• [1] On Supporting Efficient Snapshot Isolation for Hybrid Workloads with Multi-Versioned Indexes
  Yihan Sun*, Guy E. Blelloch, Wan Shen Lim, and Andrew Pavlo
  
  VLDB
   International Conference on Very Large Data Bases (VLDB), 2020    [BibTeX]
  @inproceedings{ Sun2020On,
  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 = {International Conference on Very Large Data Bases (VLDB)},
  year = { 2020 }
  }

  [copy]
  
  
    DOI:
  10.14778/3364324.3364334    [copy]
  
    Software Library:
  Part of the PAM library: Parallel Augmented Maps  [Github]
  Paper   Video  Code  Slides