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
Xin Zhang, Qizhong Mao, Ahmed Eldawy, Vagelis Hristidis and Yihan Sun
International Conference on Scientific and Statistical Database Management, 2022#LSM tree, #range query, #databasePaper Video - [27]
Parallel Cover Trees and Applications
Yan Gu, Zachary Napier, Yihan Sun and Letong Wang
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2022#cover tree, #data structure, #agglomerative clusteringPaper Slides - [26]
Many Sequential Iterative Algorithms Can Be Parallel and (Nearly) Work-efficient
Zheqi Shen, Zijin Wan, Yan Gu and Yihan Sun
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2022#paralleling sequential iterative algorithms, #data structure, #LIS, #MIS, #SSSPPaper ArXiV Slides - [25]
PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections
Laxman Dhulipala, Guy Blelloch, Yan Gu, and Yihan Sun
ACM Conference on Programming Language Design and Implementation (PLDI), 2022#join-based trees, #data structure, #compressed trees, #graph streaming, #functional data structuresPaper ArXiV Code Slides - [24]
Joinable Parallel Balanced Binary Trees
Guy Blelloch, Daniel Ferizovic and Yihan Sun
ACM Transactions on Parallel Computing#ptrees, #join-based algorithms, #theory, #experiments, #code availablePaper Code - [23]
POSTER: The Problem-Based Benchmark Suite (PBBS), V2
Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, Magdalen Dobson, and Yihan Sun
ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2022#library, #benchmark, #code availablePaper Code - [22]
Analysis of Work-Stealing and Parallel Cache Complexity
Yan Gu, Zachary Napier, and Yihan Sun
ACM-SIAM Algorithmic Principles of Computer Systems (APOCS), 2022#work-stealing scheduler, #I/O boundsPaper - 2021:[21] Space and Time Bounded Multiversion Garbage Collection
Naama Ben-David, Guy E. Blelloch, Panagiota Fatourou, Eric Ruppert, Yihan Sun and Yuanhao Wei
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 boundsPaper Video ArXiV - [20]
Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths
Xiaojun Dong, Yan Gu, Yihan Sun and Yunming Zhang
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2021.#SSSP, #time bounds, #rho-stepping, #delta*-stepping, #delta-stepping, #Bellman-Ford, #experiments, #code availablePaper 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
ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2021.#concurrent data structures, #wait-free and lock-free algorithms, #experiments, #time bounds, #code availablePaper Video ArXiV Code - 2020:[18] Optimal (Randomized) Parallel Algorithms in the Binary-Forking Model
Guy E. Blelloch, Jeremy Fineman, Yan Gu, and Yihan Sun
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 boundsPaper Video - [17]
Randomized Incremental Convex Hull is Highly Parallel
Guy E. Blelloch, Yan Gu, Julian Shun and Yihan Sun
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020.#parallel randomized incremental algorithms #computational geometry, #convex hull #time boundsPaper Video - [16]
Parallelism in Randomized Incremental Algorithms
Guy E. Blelloch, Yan Gu, Julian Shun and Yihan Sun
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 boundsPaper - 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
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 availablePaper Video Code - [14]
Multiversion Concurrency with Bounded Delay and Precise Garbage Collection
Naama Ben-David, Guy E. Blelloch, Yihan Sun and Yuanhao Wei
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, #experimentsPaper ArXiV - [13]
Implementing Parallel and Concurrent Tree Structures
Yihan Sun and Guy Blelloch
ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2019.#join-based tree algorithms, #PAM library, #code availablePaper - [12]
Parallel Range, Segment and Rectangle Queries with Augmented Maps
Yihan Sun and Guy E. Blelloch
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 availablePaper ArXiV - 2018:[11] Algorithmic Building Blocks for Asymmetric Memories
Yan Gu, Yihan Sun and Guy E. Blelloch
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, #experimentsPaper ArXiV - [10]
Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry
Guy E. Blelloch, Yan Gu, Julian Shun and Yihan Sun
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 boundsPaper ArXiV - [9]
PAM: Parallel Augmented Maps
Yihan Sun, Daniel Ferizovic and Guy Blelloch
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 availablePaper ArXiV Code - 2017:[8] Efficient Construction of Probabilistic Tree Embeddings
Guy E. Blelloch, Yan Gu and Yihan Sun
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 boundsPaper ArXiV - 2016:[7] Just Join for Parallel Ordered Sets
Guy E. Blelloch, Daniel Ferizovic and Yihan Sun
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, #experimentsPaper ArXiV Code - [6]
Parallel Shortest-paths Using Radius Stepping
Guy Blelloch, Yan Gu, Yihan Sun and Kanat Tangwongsan
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016.#graph algorithms, #single-source shortest path (SSSP), #radius-stepping, #delta-stepping, #time bounds, #experimentsPaper - [5]
Parallelism in Randomized Incremental Algorithms
Guy Blelloch, Yan Gu, Julian Shun and Yihan Sun
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-doublingPaper 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
Workshop on Algorithms in Bioinformatics (WABI), 2015.#computational biology, #graph algorithms, #protein-protein interaction (PPI) networks, #graph alignment, #WAVE, #experimental resultsPaper ArXiV - [3]
A Top-down Parallel Semisort
Yan Gu, Julian Shun and Yihan Sun and Guy E. Blelloch
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2015.#semisort, #integer sort, #random sampling, #light/heavy bucket, #improved bounds, #experimental resultsPaper Slides - 2014:[2] Fair Evaluation of Global Network Aligners
Joseph Crawford, Yihan Sun, and Tijana Milenkovic
Algorithms for Molecular Biology, 10:19.#computational biology, #graph algorithms, #protein-protein interaction (PPI) networks, #graph alignment, #experimentsPaper ArXiV - 2013:[1] Influence Maximization in Dynamic Social Networks
Honglei Zhuang, Yihan Sun, Jie Tang, Jialin Zhang and Xiaoming Sun
IEEE International Conference on Data Mining (ICDM), 2013.#data mining, #social networks, #social influence, #(dynamic) influence maximization, #maximum gap probing (MaxG), #experimentsPaper ArXiV Slides