Publications - Tree Algorithms

You can also find my publication list on Google Scholar and DBLP.

[Back to full publication list]

• 2024:
  [13] Fast and Space-Efficient Parallel Algorithms for Influence Maximization
  Letong Wang, Xiangyun Ding, Yan Gu, and Yihan Sun
  
  VLDB
   Proceedings of the VLDB Endowment (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 = {Proceedings of the VLDB Endowment (VLDB)},
  year = { 2024 }
  }

  [copy]
  
  
    DOI:
  10.14778/3632093.3632104    [copy]
  
    Software:
  PaC-IM: Parallel and Compressed Influence Maximization  [Github]
  
  HOPC
   Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2024
  
  P-tree and parallel tournament tree for parallelizing CELF
  Paper   ArXiV  Code  Poster  
• 2023:
  [12] 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:
  Parallel Longest Increasing Subsequence  [Github]
  
  Parallel van Emde Boas Tree
  Paper   ArXiV  Code  Slides  
• 2021:
  [11] 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:
  Rho-Stepping: Parallel single-source shortes paths, integrated in PASGAL  [Github]
  
  parallel tournament trees
  Paper   Video  ArXiV  Code  Slides  
• 2020:
  [10] 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]
  
  Parallel set operations with optimal work and span using BST
  Paper   Video  Slides  
• [9] On Supporting Efficient Snapshot Isolation for Hybrid Workloads with Multi-Versioned Indexes
  Yihan Sun, Guy E. Blelloch, Wan Shen Lim, and Andrew Pavlo
  
  VLDB
   Proceedings of the VLDB Endowment (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 = {Proceedings of the VLDB Endowment (VLDB)},
  year = { 2020 }
  }

  [copy]
  
  
    DOI:
  10.14778/3364324.3364334    [copy]
  
    Software:
  Part of the PAM library: Parallel Augmented Maps  [Github]
  
  Supporting snapshot isolation and MVCC in databases using P-trees in PAM
  Paper   Video  Code  Slides  
• 2019:
  [8] Multiversion Concurrency with Bounded Delay and Precise Garbage Collection
  Naama Ben-David, Guy E. Blelloch, Yihan Sun, and Yuanhao Wei
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2019    [BibTeX]
  @inproceedings{ Ben-David2019Multiversion,
  title = { Multiversion Concurrency with Bounded Delay and Precise Garbage Collection },
  author = { Ben-David, Naama and  Blelloch, Guy E. and  Sun, Yihan and  Wei, Yuanhao},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2019 }
  }

  [copy]
  
  
    DOI:
  10.1145/3323165.3323185    [copy]
  
  Garbage collection of multi-versioned P-tree-like structures (path-copying data structures)
  Paper   ArXiV  
• [7] Implementing Parallel and Concurrent Tree Structures
  Yihan Sun, and Guy E. Blelloch
  
  PPoPP
   ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2019    [BibTeX]
  @inproceedings{ Sun2019Implementing,
  title = { Implementing Parallel and Concurrent Tree Structures },
  author = { Sun, Yihan and  Blelloch, Guy E.},
  booktitle = {ACM Symposium on Principles and Practice of Parallel Programming (PPoPP)},
  year = { 2019 }
  }

  [copy]
  
  
    DOI:
  10.1145/3293883.3302576    [copy]
  
  Tutorial about P-trees and the PAM library
  Paper   
• [6] Parallel Range, Segment and Rectangle Queries with Augmented Maps
  Yihan Sun, and Guy E. Blelloch
  
  ALENEX
   Algorithm Engineering and Experiments (ALENEX), 2019    [BibTeX]
  @inproceedings{ Sun2019Parallel,
  title = { Parallel Range, Segment and Rectangle Queries with Augmented Maps },
  author = { Sun, Yihan and  Blelloch, Guy E.},
  booktitle = {Algorithm Engineering and Experiments (ALENEX)},
  year = { 2019 }
  }

  [copy]
  
  
    DOI:
  10.1137/1.9781611975499.13    [copy]
  
    Software:
  Part of the PAM library: Parallel Augmented Maps  [Github]
  
  Using P-trees and PAM to solve range, segment and rectangle queries in parallel
  Paper   ArXiV  
• 2018:
  [5] Algorithmic Building Blocks for Asymmetric Memories
  Yan Gu, Yihan Sun, and Guy E. Blelloch
  
  ESA
   European Symposium on Algorithms (ESA), 2018    [BibTeX]
  @inproceedings{ Gu2018Algorithmic,
  title = { Algorithmic Building Blocks for Asymmetric Memories },
  author = { Gu, Yan and  Sun, Yihan and  Blelloch, Guy E.},
  booktitle = {European Symposium on Algorithms (ESA)},
  year = { 2018 }
  }

  [copy]
  
  
    DOI:
  10.4230/LIPIcs.ESA.2018.44    [copy]
  
  write-efficient join-based tree algorithms
  Paper   ArXiV  
• [4] Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry
  Guy E. Blelloch, Yan Gu, Yihan Sun, and Julian Shun
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2018    [BibTeX]
  @inproceedings{ Blelloch2018Parallel,
  title = { Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry },
  author = { Blelloch, Guy E. and  Gu, Yan and  Sun, Yihan and  Shun, Julian},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2018 }
  }

  [copy]
  
  
    DOI:
  10.1145/3210377.3210380    [copy]
  
  Parallel write-efficient algorithms on interval tree, priority search tree, range tree
  Paper   ArXiV  
• [3] PAM: Parallel Augmented Maps
  Yihan Sun, Daniel Ferizovic, and Guy E. Blelloch
  
  PPoPP
   ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2018    [BibTeX]
  @inproceedings{ Sun2018PAM:,
  title = { PAM: Parallel Augmented Maps },
  author = { Sun, Yihan and  Ferizovic, Daniel and  Blelloch, Guy E.},
  booktitle = {ACM Symposium on Principles and Practice of Parallel Programming (PPoPP)},
  year = { 2018 }
  }

  [copy]
  
  
    DOI:
  10.1145/3200691.3178509    [copy]
  
    Software:
  PAM: Parallel Augmented Maps  [Github]
  
  Introducing P-tree and the PAM library
  Paper   ArXiV  Code  
• 2017:
  [2] Efficient Construction of Probabilistic Tree Embeddings
  Guy E. Blelloch, Yan Gu, and Yihan Sun
  
  ICALP
   International Colloquium on Automata, Languages, and Programming (ICALP), 2017    [BibTeX]
  @inproceedings{ Blelloch2017Efficient,
  title = { Efficient Construction of Probabilistic Tree Embeddings },
  author = { Blelloch, Guy E. and  Gu, Yan and  Sun, Yihan},
  booktitle = {International Colloquium on Automata, Languages, and Programming (ICALP)},
  year = { 2017 }
  }

  [copy]
  
  
    DOI:
  10.4230/LIPIcs.ICALP.2017.26    [copy]
  
  FRT trees
  Paper   ArXiV  
• 2016:
  [1] Just Join for Parallel Ordered Sets
  Guy E. Blelloch, Daniel Ferizovic, and Yihan Sun
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016    [BibTeX]
  @inproceedings{ Blelloch2016Just,
  title = { Just Join for Parallel Ordered Sets },
  author = { Blelloch, Guy E. and  Ferizovic, Daniel and  Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2016 }
  }

  [copy]
  
  
    DOI:
  10.1145/2935764.2935768    [copy]
  
    Software:
  Part of the PAM library: Parallel Augmented Maps  [Github]
  
  Introducing join-based algorithms for BSTs
  Paper   ArXiV  Code