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]   [Binary Forking]   [Incremental]   [PAM-Database]   [PAM-Geometry]   [PAM]   [Just Join]   [Semisort]  

  • 2022:
    [28] Bi-directional Log-Structured Merge Tree (To Appear)
    Xin Zhang, Qizhong Mao, Ahmed Eldawy, Vagelis Hristidis and Yihan Sun
    SSDBM
     International Conference on Scientific and Statistical Database Management, 2022  
    #LSM tree, #range query, #database
    Paper   
  • [27] 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  
    #cover tree, #data structure, #agglomerative clustering
    Paper   Slides
  • [26] 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  
    #paralleling sequential iterative algorithms, #data structure, #LIS, #MIS, #SSSP
    Paper   ArXiV  Slides
  • [25] PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections
    Laxman Dhulipala, Guy Blelloch, Yan Gu, and Yihan Sun
    PLDI
     ACM Conference on Programming Language Design and Implementation (PLDI), 2022  
    #join-based trees, #data structure, #compressed trees, #graph streaming, #functional data structures
    Paper   ArXiV  CodeSlides
  • [24] Joinable Parallel Balanced Binary Trees
    Guy Blelloch, Daniel Ferizovic and Yihan Sun
    TOPC
     ACM Transactions on Parallel Computing  
    #ptrees, #join-based algorithms, #theory, #experiments, #code available
    Paper   Code
  • [23] POSTER: The Problem-Based Benchmark Suite (PBBS), V2
    Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, Magdalen Dobson, and Yihan Sun
    PPoPP
     ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2022  
    #library, #benchmark, #code available
    Paper   Code
  • [22] 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  
    #work-stealing scheduler, #I/O bounds
    Paper   
  • 2021:
    [21] 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.  
    #concurrent data structures, #range-tracking, #garbage collection, #memory management, #wait-free and lock-free algorithms, #MVCC, #time and space bounds
    Paper   Video  ArXiV  
  • [20] 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.  
    #SSSP, #time bounds, #rho-stepping, #delta*-stepping, #delta-stepping, #Bellman-Ford, #experiments, #code available
    Paper   Video  ArXiV  Code
  • [19] 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.  
    #concurrent data structures, #wait-free and lock-free algorithms, #experiments, #time bounds, #code available
    Paper   Video  ArXiV  Code
  • 2020:
    [18] 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.  
    #binary-forking model, #sorting, #semisorting, #list/tree contraction, #set-set algorithms, #join-based tree algorithms, #time bounds
    Paper   Video  
  • [17] 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.  
    #parallel randomized incremental algorithms #computational geometry, #convex hull #time bounds
    Paper   Video  
  • [16] Parallelism in Randomized Incremental Algorithms
    Guy E. Blelloch, Yan Gu, Julian Shun and Yihan Sun
    JACM
     Journal of the ACM (JACM).  
    #parallel randomized incremental algorithms, #computational geometry, #graph algorithms, #sorting, #Delaunay triangulation, #closest pair, #smallest enclosing disk, #SCC, #LE list, #prefix doubling, #time bounds
    Paper   
  • 2019:
    [15] 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).  
    #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
  • [14] 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.  
    #transactional system, #GC, #wait-free algorithms, #persistent/functional data structures, #P-trees, #the PAM libaray, #time bounds, #experiments
    Paper   ArXiV  
  • [13] Implementing Parallel and Concurrent Tree Structures
    Yihan Sun and Guy Blelloch
    PPoPP
     ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2019.  
    #join-based tree algorithms, #PAM library, #code available
    Paper   
  • [12] Parallel Range, Segment and Rectangle Queries with Augmented Maps
    Yihan Sun and Guy E. Blelloch
    ALENEX
     Algorithm Engineering and Experiments (ALENEX), 2019.  
    #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  
  • 2018:
    [11] Algorithmic Building Blocks for Asymmetric Memories
    Yan Gu, Yihan Sun and Guy E. Blelloch
    ESA
     European Symposium on Algorithms (ESA), 2018.  
    #write-effient algorithms, #algorithms for NVRAM, #k-level hash table, #join-based tree algorithms, #sorting, #BFS, #single-source shortest path, #phased Dijkstra, #experiments
    Paper   ArXiV  
  • [10] 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.  
    #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  
  • [9] PAM: Parallel Augmented Maps
    Yihan Sun, Daniel Ferizovic and Guy Blelloch
    PPoPP
     ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2018.  
    #ordered maps, #augmented maps, #augmented trees, #join-based algorithms, #the PAM library, #persistent/functional data structures, #range sum, #interval tree, #2-D range tree, #inverted index searching #experiments, #code available
    Paper   ArXiV  Code
  • 2017:
    [8] Efficient Construction of Probabilistic Tree Embeddings
    Guy E. Blelloch, Yan Gu and Yihan Sun
    ICALP
     International Colloquium on Automata, Languages, and Programming (ICALP), 2017.  
    #probablistic tree embedding, #FRT trees, #Ramsey partitions, #LE-list, #approximate single-source shortest path (SSSP), #bucket-tree, #distance oracle, #improved bounds
    Paper   ArXiV  
  • 2016:
    [7] 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.  
    #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
  • [6] 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.  
    #graph algorithms, #single-source shortest path (SSSP), #radius-stepping, #delta-stepping, #time bounds, #experiments
    Paper   
  • [5] 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.  
    #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  
  • 2015:
    [4] 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.  
    #computational biology, #graph algorithms, #protein-protein interaction (PPI) networks, #graph alignment, #WAVE, #experimental results
    Paper   ArXiV  
  • [3] 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.  
    #semisort, #integer sort, #random sampling, #light/heavy bucket, #improved bounds, #experimental results
    Paper   Slides
  • 2014:
    [2] Fair Evaluation of Global Network Aligners
    Joseph Crawford, Yihan Sun, and Tijana Milenkovic
    AMB
     Algorithms for Molecular Biology, 10:19.  
    #computational biology, #graph algorithms, #protein-protein interaction (PPI) networks, #graph alignment, #experiments
    Paper   ArXiV  
  • 2013:
    [1] 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.  
    #data mining, #social networks, #social influence, #(dynamic) influence maximization, #maximum gap probing (MaxG), #experiments
    Paper   ArXiV  Slides