Parallel Algorithms

[Back to full publication list]

Parallel algorithms and data structures.

2025:
[39] 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 }
}

  DOI:
10.1145/3694906.3743311
  Software Library:
Orionet: Parallel Single and Batch PPSP  [Github]
Paper   ArXiV  Code
[38] 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 }
}

  DOI:
10.1145/3721145.3725744
  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
[37] 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 }
}

  DOI:
10.1145/3725332
  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
[36] 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 }
}

  DOI:
10.1145/3709712
  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
[35] 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 }
}

  DOI:
10.1137/1.9781611978339.4
  Software Library:
CBFS: Cluster Breadth-First Search  [Zenodo]
Paper   ArXiV  Code  Slides
2024:
[34] 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 }
}

  Software Library:
Parallel Work-Efficient Dynamic Programming  [Github]
Paper   ArXiV  Code  Slides
[33] 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 }
}

  Software Library:
PASGAL: Parallel And Scalable Graph Algorithm Library  [Github]
Paper   ArXiV  Code  Slides  Poster
[32] 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 }
}

  Software Library:
Parallel Single-linkage Dendrogram Construction Algorithm  [Github]
Paper   ArXiV  Code
[31] 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 }
}

  DOI:
10.1145/3627535.3638475
  Software Library:
ParlayANN: Parallel Graph-Based Algorithms for Approximate Nearest Neighbor Search  [Github]
Paper   ArXiV  Code
[30] 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 }
}

  DOI:
10.1145/3627535.3638483
  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
[29] 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 }
}

  DOI:
10.14778/3632093.3632104
  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:
[28] 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 }
}

  DOI:
10.4230/LIPIcs.ESA.2023.40
  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
[27] 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 }
}

  DOI:
10.1145/3558481.3591071
  Software Library:
Parallel Semisort  [Github]
Paper   ArXiV  Code  Slides
[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{ 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 }
}

  DOI:
10.1145/3558481.3591069
  Software Library:
Parallel Longest Increasing Subsequence  [Github]
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{ 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 }
}

  DOI:
10.1145/3589259
  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
[24] 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 }
}

  DOI:
10.1145/3572848.3577483
  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:
[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 }
}

  DOI:
10.1145/3490148.3538581
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 }
}

  DOI:
10.1145/3490148.3538574
  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 }
}

  DOI:
10.1145/3519939.3523733
  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 }
}

  DOI:
10.1145/3512769
  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 }
}

  DOI:
10.1145/3503221.3508422
  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 }
}

  DOI:
10.1137/1.9781611977059.4
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 }
}

  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 }
}

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 }
}

  DOI:
10.4230/LIPIcs.DISC.2021.12
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 }
}

  DOI:
10.1145/3409964.3461782
  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 }
}

  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 }
}

  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 }
}

  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 }
}

  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 }
}

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 }
}

  DOI:
10.1145/3437801.3441602
  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 }
}

  DOI:
10.1145/3350755.3400227
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 }
}

  DOI:
10.1145/3350755.3400255
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 }
}

  DOI:
10.1145/3402819
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 }
}

  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 }
}

  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 }
}

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 }
}

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