Geometric Algorithms

[Back to full publication list]

• 2025:
  [12] 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  
• 2024:
  [11] 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  
• 2022:
  [10] 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  
• [9] 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  
• [8] 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  
• 2021:
  [7] 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  
• [6] 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  
• [5] 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  
• [4] 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  
• 2020:
  [3] 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  
• [2] 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   
• [1] 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