I/O- (Cache-) Efficient Algorithms

[Back to full publication list]

• 2025:
  [5] 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  
• 2023:
  [4] 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  
• 2022:
  [3] 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:
  [2] 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   
• 2020:
  [1] 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