Publications

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

You can also view my publications by category:

Tree algorithms   P-trees and PAM   Graph algorithms   Geometric algorithms

Incremental algorithms   Concurrent data structures   Write-efficient algorithms  

Code available   Theory   Experiments  

Shortcut to Some Papers:

 [Stepping Algorithms]  [Binary Forking]  [Incremental]  [PAM-Database]  [PAM-Geometry]  [PAM]  [Just Join]  [Semisort]  

• Space and Time Bounded Multiversion Garbage Collection
  Naama Ben-David, Guy E. Blelloch, Panagiota Fatourou, Eric Ruppert, Yihan Sun and Yuanhao Wei
  
  DISC
   International Symposium on Distributed Computing (DISC), 2021. (To appear)
  
  Proposed algorithm for garbage collection in multi-versioned concurrent systems.
  #concurrent data structures, #range-tracking, #garbage collection, #memory management, #wait-free and lock-free algorithms, #time and space bounds
  Paper   
• 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.
  
  Proposed the stepping framework and two new algorithms for parallel single source shortest path (SSSP).
  #single source shortest path (SSSP), #time bounds, #rho-stepping, #delta*-stepping, #delta-stepping, #Bellman-Ford, #experiments, #code available
  Paper   Video  ArXiV  Code
• 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
   Principles and Practice of Parallel Programming (PPoPP), 2021.
  
  Proposed a general framework to support multi-versioning for CAS objects.
  #concurrent data structures, #wait-free and lock-free algorithms, #experiments, #time bounds, #code available
  Paper   Video  ArXiV  Code
• Optimal (Randomized) Parallel Algorithms in the Binary-Forking Model
  Guy E. Blelloch, Jeremy Fineman, Yan Gu, and Yihan Sun
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020.
  
  Proposed the binary-forking (BF) model and several parallel algorithms with optimal work and span under the BF model.
  #binary-forking (BF) model, #sorting, #semisorting, #list/tree contraction, #set-set algorithms, #join-based tree algorithms, #time bounds
  Paper   Video  
• 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.
  
  Proved the low depth of the dependence in randomized construction incremental (RIC) algorithm for d-D convex hull. Showed a new parallel work-efficient convex hull algorithm with low span.
  #parallel randomized incremental algorithms #computational geometry, #convex hull #time bounds
  Paper   Video  
• Parallelism in Randomized Incremental Algorithms
  Guy E. Blelloch, Yan Gu, Julian Shun and Yihan Sun
  
  JACM
   Journal of the ACM (JACM).
  
  Proposed the framework of parallel randomized incremental construction (RIC) algorithms. Showed several algorithms based on RIC with efficient work and low span.
  #parallel randomized incremental algorithms, #computational geometry, #graph algorithms, #sorting, #Delaunay triangulation, #closest pair, #smallest enclosing disk, #strongly connected conponent (SCC), #least-element (LE) list, #prefix doubling, #time bounds
  Paper   
• 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 (PVLDB), 13(2).
  
  Applying P-trees and the PAM library to support efficient multi-verioned indexes in DBMS.
  #multi-version concurrency control (MVCC), #OLAP/OLTP/HTAP database systems, #join-based tree algorithms, #PAM library, #persistent/pure data structures, #nested indexes, #YCSB/TPCH/TPCC experiments, #code available
  Paper   Video  Code
• 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.
  
  Proposed a framework for garbage collection (GC) in transactional systems. Showed a linearizable wait-free algorithm to achieve safe and precise GC. Applied P-trees in experiments.
  #transactional system, #garbage collection, #wait-free algorithms, #persistent/pure data structures, #P-trees, #the PAM libaray, #time bounds, #experiments
  Paper   ArXiV  
• Implementing Parallel and Concurrent Tree Structures
  Yihan Sun and Guy Blelloch
  
  PPoPP
   ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2019.
  
  Tutorial on join-based trees (or P-trees) and the PAM libaray.
  #join-based tree algorithms, #PAM library, #code available
  Paper   
• Parallel Range, Segment and Rectangle Queries with Augmented Maps
  Yihan Sun and Guy E. Blelloch
  
  ALENEX
   Algorithm Engineering and Experiments (ALENEX), 2019.
  
  Used augmented maps to model 2-D range, segment, and rectangle queries in parallel. Showed implementations and experimental results based on PAM.
  #P-trees, #join-based tree algorithms, #the PAM library, #range/segment/rectangle query, #computational geometry, #augmented maps, #augmented trees, #prefix structures, #experiments, #code available
  Paper   ArXiV  
• Algorithmic Building Blocks for Asymmetric Memories
  Yan Gu, Yihan Sun and Guy E. Blelloch
  
  ESA
   European Symposium on Algorithms (ESA), 2018.
  
  Discussed write-efficient algorithms and their implementations. Showed experimental evaluations of these algorithms in a software simulator.
  #write-effient algorithms, #algorithms for NVRAM, #k-level hash table, #join-based tree algorithms, #sorting, #bread-first search (BFS), #single-source shortest path, #phased Dijkstra, #experiments
  Paper   ArXiV  
• Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry
  Guy E. Blelloch, Yan Gu, Julian Shun and Yihan Sun
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2018.
  
  Proposed write-efficient algorithms for several computational geometry problems based on the randomized incremental construction (RIC) and parallel augmented trees.
  #parallel randomized incremental algorithms, #computational geometry, #Delaunay triangulation, #k-d trees, #interval tree, #priority search tree, #range tree, #augmented trees, #sorting, #DAG tracing, #history graph, #prefix doubling, #time bounds
  Paper   ArXiV  
• PAM: Parallel Augmented Maps
  Yihan Sun, Daniel Ferizovic and Guy Blelloch
  
  PPoPP
   ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2018.
  
  Proposed the augmented map ADT and its implementation using parallel balanced BST based on join-based algorithms. Implemented the augmented map in the PAM (parallel augmented map) library. Showed four applications and their implementations/experiments.
  #ordered maps, #augmented maps, #augmented trees, #join-based algorithms, #the PAM library, #persistent/pure data structures, #range sum, #interval tree, #2-D range tree, #inverted index searching #experiments, #code available
  Paper   ArXiV  Code
• Efficient Construction of Probabilistic Tree Embeddings
  Guy E. Blelloch, Yan Gu and Yihan Sun
  
  ICALP
   International Colloquium on Automata, Languages, and Programming (ICALP), 2017.
  
  Proposed an efficient algorithm to construct probablistic tree embeddings with improved bounds, with a key component as a novel approximate single-source shortest path algorithm.
  #probablistic tree embedding, #FRT trees, #Ramsey partitions, #LE-list, #approximate single-source shortest path (SSSP), #bucket-tree, #distance oracle, #improved bounds
  Paper   ArXiV  
• 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.
  
  Proposed an efficient algorithm to construct probablistic tree embeddings with improved bounds, with a key component as a novel approximate single-source shortest path algorithm.
  #join-based tree algorithms, #P-trees, #efficient parallel set-set algorithms, #balancing-scheme independent tree algorithms, #AVL trees, #red-black trees, #weight-balanced trees, #treaps, #rank-based analysis, #time bounds, #experiments
  Paper   ArXiV  Code
• Parallel Shortest-paths Using Radius Stepping
  Guy Blelloch, Yan Gu, Yihan Sun and Kanat Tangwongsan
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016.
  
  Proposed the radius-stepping algorithm for parallel single-source shortest path (SSSP) problem with work-span tradeoff.
  #graph algorithms, #single-source shortest path (SSSP), #radius-stepping, #delta-stepping, #time bounds, #experiments
  Paper   
• Parallelism in Randomized Incremental Algorithms
  Guy Blelloch, Yan Gu, Julian Shun and Yihan Sun
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016.
  
  Proposed the framework of parallel randomized incremental construction (RIC) algorithms. Showed several algorithms based on RIC that are work-efficient with low span.
  #parallel randomized incremental algorithms, #computational geometry, #graph algorithms, #sorting, #Delaunay triangulation, #closest pair, #smallest enclosing disk, #strongly connected conponent (SCC), #least-element (LE) list, #prefix-doubling
  Paper   ArXiV  
• Simultaneous Optimization of Both Node and Edge Conservation in Network Alignment via WAVE
  Yihan Sun, Joseph Crawford, Jie Tang and Tijana Milenkovic
  
  WABI
   Workshop on Algorithms in Bioinformatics (WABI), 2015.
  
  Proposed graph aligner algorithm WAVE for protein-protein interaction (PPI) networks.
  #computational biology, #graph algorithms, #protein-protein interaction (PPI) networks, #graph alignment, #WAVE, #experimental results
  Paper   ArXiV  
• A Top-down Parallel Semisort
  Yan Gu, Julian Shun and Yihan Sun and Guy E. Blelloch
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2015.
  
  Proposed the parallel semisort algorithm with linear work and low depth.
  #semisort, #integer sort, #random sampling, #light/heavy bucket, #improved bounds, #experimental results
  Paper   Slides
• Fair Evaluation of Global Network Aligners
  Joseph Crawford, Yihan Sun, and Tijana Milenkovic
  
  AMB
   Algorithms for Molecular Biology, 10:19.
  
  Provided experimental evaluation about different combinations of existing node cost function (NCF) and alignment strategy (AS).
  #computational biology, #graph algorithms, #protein-protein interaction (PPI) networks, #graph alignment, #experiments
  Paper   ArXiV  
• Influence Maximization in Dynamic Social Networks
  Honglei Zhuang, Yihan Sun, Jie Tang, Jialin Zhang and Xiaoming Sun
  
  ICDM
   IEEE International Conference on Data Mining (ICDM), 2013.
  
  Defined the problem of dynamic influence maximization (IM) on social networks. Showed several algorithms for dynamic IM.
  #data mining, #social networks, #social influence, #(dynamic) influence maximization, #maximum gap probing (MaxG), #experiments
  Paper   ArXiV