publications

  • 2023:
    [52] Parallel Strong Connectivity Based on Faster Reachability (To Appear)
    Letong Wang, Xiaojun Dong, Yan Gu, and Yihan Sun
    #Strong connectivity, #graph algorithms, #high-performance implementation, #BGSS SCC algorithm, #LE-list, #connectivity
    SIGMOD
     ACM Special Interest Group on Management of Data (SIGMOD), 2023   
  • [51] Provably Fast and Space-Efficient Parallel Biconnectivity
    Xiaojun Dong, Letong Wang, Yan Gu, and Yihan Sun
    #FAST-BCC, #Biconnectivity, #graph algorithms, #theoretically-efficient, #high-performance implementation
    🏆 Best Paper Award!
    PPoPP
     ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2023   
    Paper   ArXiV  Code  
  • 2022:
    [50] Bi-directional Log-Structured Merge Tree
    Xin Zhang, Qizhong Mao, Ahmed Eldawy, Vagelis Hristidis, and Yihan Sun
    #LSM tree, #range query, #database
    SSDBM
     International Conference on Scientific and Statistical Database Management (SSDBM), 2022   
    Paper   Video  
  • [49] Parallel Cover Trees and Applications
    Yan Gu, Zachary Napier, Yihan Sun, and Letong Wang
    #cover tree, #data structure, #agglomerative clustering
    SPAA
     ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2022   
    Paper   Slides  
  • [48] Many Sequential Iterative Algorithms Can Be Parallel and (Nearly) Work-efficient
    Zheqi Shen, Zijin Wan, Yan Gu, and Yihan Sun
    #paralleling sequential iterative algorithms, #data structure, #LIS, #MIS, #SSSP
    SPAA
     ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2022   
    Paper   ArXiV  Slides  
  • [47] PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections
    Laxman Dhulipala, Guy Blelloch, Yan Gu, and Yihan Sun
    #join-based trees, #data structure, #compressed trees, #graph streaming, #functional data structures
    PLDI
     ACM Conference on Programming Language Design and Implementation (PLDI), 2022   
    Paper   ArXiV  Code  Slides  
  • [46] Joinable Parallel Balanced Binary Trees
    Guy E. Blelloch, Daniel Ferizovic, and Yihan Sun
    #ptrees, #join-based algorithms, #theory, #experiments, #code available
    TOPC
     ACM Transactions on Parallel Computing (TOPC), 2022   
    Paper   Code  
  • [45] POSTER: The Problem-Based Benchmark Suite (PBBS), V2
    Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, Magdalen Dobson, and Yihan Sun
    #library, #benchmark, #code available
    PPoPP
     ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2022   
    Paper   Code  
  • [44] Analysis of Work-Stealing and Parallel Cache Complexity
    Yan Gu, Zachary Napier, and Yihan Sun
    #work-stealing scheduler, #I/O bounds
    APOCS
     ACM-SIAM Algorithmic Principles of Computer Systems (APOCS), 2022   
    Paper   
  • 2021:
    [43] ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain
    Shangdi Yu, Yiqiu Wang, Yan Gu, Laxman Dhulipala, and Julian Shun
    #geometry, #data-science, #experiments, #code available
    VLDB
     Proceedings of the VLDB Endowment (VLDB), 2021   
    Paper   
  • [42] The Processing-in-Memory Model
    Hongbo Kang, Phillip B. Gibbons, Guy E. Blelloch, Laxman Dhulipala, Yan Gu, and Charles McGuffey
    #architecture, #model-of-computation, #data structure, #set/tree algorithms
    SPAA
     ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2021   
    Paper   Video  
  • [41] Space and Time Bounded Multiversion Garbage Collection
    Naama Ben-David, Guy E. Blelloch, Panagiota Fatourou, Eric Ruppert, Yihan Sun, and Yuanhao Wei
    #concurrent data structures, #range-tracking, #garbage collection, #memory management, #wait-free and lock-free algorithms, #MVCC, #time and space bounds
    DISC
     International Symposium on Distributed Computing (DISC), 2021   
    Paper   Video  ArXiV  
  • [40] Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths
    Xiaojun Dong, Yan Gu, Yihan Sun, and Yunming Zhang
    #SSSP, #time bounds, #rho-stepping, #delta*-stepping, #delta-stepping, #Bellman-Ford, #experiments, #code available
    SPAA
     ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2021   
    Paper   Video  ArXiV  Code  
  • [39] GeoGraph: A Framework for Graph Processing on Geometric Data
    Yiqiu Wang, Shangdi Yu, Laxman Dhulipala, Yan Gu, and Julian Shun
    #system #graph #geometry
    SIGOPS-OSR
     ACM SIGOPS Operating Systems Review (SIGOPS-OSR), 2021   
    Paper   Code  
  • [38] Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering
    Yiqiu Wang, Shangdi Yu, Yan Gu, and Julian Shun
    #geometry, #data-science, #theory, #experiments, #code available
    SIGMOD
     ACM Special Interest Group on Management of Data (SIGMOD), 2021   
    Paper   Video  ArXiV  Code  
  • [37] An Experimental Study of a New Parallel Batch-Dynamic Closest Pair Data Structure
    Wang Yiqiu, Shangdi Yu, Yan Gu, and Julian Shun
    #geometry, #theory, #experiments, #code available
    SoCG
     ACM Symposium on Computational Geometry (SoCG), 2021   
    Paper   ArXiV  Code  
  • [36] Parallel In-Place Algorithms: Theory and Practice
    Yan Gu, Omar Obeya, and Julian Shun
    #architecture, #model-of-computation, #theory, #experiments, #code available
    APOCS
     ACM-SIAM Algorithmic Principles of Computer Systems (APOCS), 2021   
    Paper   Video  Code  
  • [35] The Read-Only Semi-External Model
    Guy E. Blelloch, Laxman Dhulipala, Phillip B. Gibbons, Yan Gu, Charles McGuffey, and Julian Shun
    #architecture, #model-of-computation, #graph, #theory
    APOCS
     ACM-SIAM Algorithmic Principles of Computer Systems (APOCS), 2021   
    Paper   
  • [34] Constant-Time Snapshots with Applications to Concurrent Data Structures
    Yuanhao Wei, Naama Ben-David, Guy E. Blelloch, Panagiota Fatourou, Eric Ruppert, and Yihan Sun
    #concurrent data structures, #wait-free and lock-free algorithms, #experiments, #time bounds, #code available
    PPoPP
     ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2021   
    Paper   Video  ArXiV  Code  
  • 2020:
    [33] Optimal (Randomized) Parallel Algorithms in the Binary-Forking Model
    Guy E. Blelloch, Jeremy Fineman, Yan Gu, and Yihan Sun
    #binary-forking model, #sorting, #semisorting, #list/tree contraction, #set-set algorithms, #join-based tree algorithms, #time bounds
    🏆 Best Paper Candidate!
    SPAA
     ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020   
    Paper   Video  
  • [32] Randomized Incremental Convex Hull is Highly Parallel
    Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun
    #parallel randomized incremental algorithms #computational geometry, #convex hull #time bounds
    SPAA
     ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020   
    Paper   Video  
  • [31] Parallelism in Randomized Incremental Algorithms
    Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun
    #parallel randomized incremental algorithms, #computational geometry, #graph algorithms, #sorting, #Delaunay triangulation, #closest pair, #smallest enclosing disk, #SCC, #LE list, #prefix doubling, #time bounds
    JACM
     Journal of the ACM (JACM), 2020   
    Paper   
  • [30] Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs
    Laxman Dhulipala, Charles McGuffey, Hongbo Kang, Yan Gu, Guy E. Blelloch, Phillip B. Gibbons, and Julian Shun
    #architecture, #system, #graph, #experiments, #code available
    VLDB
     Proceedings of the VLDB Endowment (VLDB), 2020   
    Paper   ArXiV  Code  
  • [29] Theoretically-Efficient and Practical Parallel DBSCAN
    Yiqiu Wang, Yan Gu, and Julian Shun
    #geometry #data-science #experiments #code-available
    SIGMOD
     ACM Special Interest Group on Management of Data (SIGMOD), 2020   
    Paper   Video  ArXiV  Code  Page  
  • [28] Improved Parallel Cache-Oblivious Algorithms for Dynamic Programming
    Yan Gu, and Guy E. Blelloch
    #dynamic-programming #linear-algebra #architecture #theory
    APOCS
     ACM-SIAM Algorithmic Principles of Computer Systems (APOCS), 2020   
    Paper   ArXiV  
  • 2019:
    [27] On Supporting Efficient Snapshot Isolation for Hybrid Workloads with Multi-Versioned Indexes
    Yihan Sun, Guy E. Blelloch, Wan Shen Lim, and Andrew Pavlo
    #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
    VLDB
     Proceedings of the VLDB Endowment (VLDB), 2019   
    Paper   Video  Code  
  • [26] Multiversion Concurrency with Bounded Delay and Precise Garbage Collection
    Naama Ben-David, Guy E. Blelloch, Yihan Sun, and Yuanhao Wei
    #transactional system, #GC, #wait-free algorithms, #persistent/functional data structures, #P-trees, #the PAM libaray, #time bounds, #experiments
    SPAA
     ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2019   
    Paper   ArXiV  
  • [25] Implementing Parallel and Concurrent Tree Structures
    Yihan Sun, and Guy E. Blelloch
    #join-based tree algorithms, #PAM library, #code available
    PPoPP
     ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2019   
    Paper   
  • [24] Parallel Range, Segment and Rectangle Queries with Augmented Maps
    Yihan Sun, and Guy E. Blelloch
    #P-trees, #join-based tree algorithms, #the PAM library, #range/segment/rectangle query, #computational geometry, #augmented maps, #augmented trees, #prefix structures, #experiments, #code available
    ALENEX
     Algorithm Engineering and Experiments (ALENEX), 2019   
    Paper   ArXiV  
  • 2018:
    [23] Algorithmic Building Blocks for Asymmetric Memories
    Yan Gu, Yihan Sun, and Guy E. Blelloch
    #write-effient algorithms, #algorithms for NVRAM, #k-level hash table, #join-based tree algorithms, #sorting, #BFS, #single-source shortest path, #phased Dijkstra, #experiments
    ESA
     European Symposium on Algorithms (ESA), 2018   
    Paper   ArXiV  
  • [22] The Parallel Persistent Memory Model
    Guy E. Blelloch, Phillip B. Gibbons, Yan Gu, Charles McGuffey, and Julian Shun
    #architecture #scheduling
    SPAA
     ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2018   
    Paper   
  • [21] Implicit Decomposition for Write-Efficient Connectivity Algorithms
    Naama Ben-David, Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, Charles McGuffey, and Julian Shun
    #write-efficient algorithms, #graph, #theory, #architecture, #connectivity
    IPDPS
     IEEE International Parallel & Distributed Processing Symposium (IPDPS), 2018   
    Paper   ArXiV  
  • [20] Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry
    Guy E. Blelloch, Yan Gu, Yihan Sun, and Julian Shun
    #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
    SPAA
     ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2018   
    Paper   ArXiV  
  • [19] PAM: Parallel Augmented Maps
    Yihan Sun, Daniel Ferizovic, and Guy E. Blelloch
    #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
    PPoPP
     ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2018   
    Paper   ArXiV  Code  
  • 2017:
    [18] Efficient Construction of Probabilistic Tree Embeddings
    Guy E. Blelloch, Yan Gu, and Yihan Sun
    #probablistic tree embedding, #FRT trees, #Ramsey partitions, #LE-list, #approximate single-source shortest path (SSSP), #bucket-tree, #distance oracle, #improved bounds
    ICALP
     International Colloquium on Automata, Languages, and Programming (ICALP), 2017   
    Paper   ArXiV  
  • 2016:
    [17] Just Join for Parallel Ordered Sets
    Guy E. Blelloch, Daniel Ferizovic, and Yihan Sun
    #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
    SPAA
     ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016   
    Paper   ArXiV  Code  
  • [16] Parallel Shortest-paths Using Radius Stepping
    Guy E. Blelloch, Yan Gu, Yihan Sun, and Kanat Tangwongsan
    #graph algorithms, #single-source shortest path (SSSP), #radius-stepping, #delta-stepping, #time bounds, #experiments
    SPAA
     ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016   
    Paper   
  • [15] Parallelism in Randomized Incremental Algorithms
    Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun
    #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
    SPAA
     ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016   
    Paper   ArXiV  
  • [14] Parallel Algorithms with Asymmetric Read and Write Costs
    Naama Ben-David, Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, Charles McGuffey, and Julian Shun
    #write-efficient algorithms, #architecture, #theory, #model-of-computation, #graph, #geometry, #BFS, list/tree contraction
    SPAA
     ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016   
    Paper   
  • [13] Efficient Algorithms with Asymmetric Read and Write Costs
    Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, Charles McGuffey, and Julian Shun
    #write-efficient algorithms, #architecture, #theory, #model-of-computation, #graph, #SSSP
    ESA
     European Symposium on Algorithms (ESA), 2016   
    Paper   ArXiV  
  • 2015:
    [12] Simultaneous Optimization of Both Node and Edge Conservation in Network Alignment via WAVE
    Yihan Sun, Joseph Crawford, Jie Tang, and Tijana Milenkovic
    #computational biology, #graph algorithms, #protein-protein interaction (PPI) networks, #graph alignment, #WAVE, #experimental results
    WABI
     Workshop on Algorithms in Bioinformatics (WABI), 2015   
    Paper   ArXiV  
  • [11] Sorting with Asymmetric Read and Write Costs
    Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, Charles McGuffey, and Julian Shun
    #write-efficient algorithms, #architecture, #theory, #model-of-computation, #sort
    SPAA
     ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2015   
    Paper   ArXiV  
  • [10] A Top-down Parallel Semisort
    Yan Gu, Julian Shun, Yihan Sun, and Guy E. Blelloch
    #semisort, #integer sort, #random sampling, #light/heavy bucket, #improved bounds, #experimental results
    SPAA
     ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2015   
    Paper   Slides  
  • [9] Sequential Random Permutation, List Contraction and Tree Contraction are Highly Parallel
    Julian Shun, Yan Gu, Guy E. Blelloch, Jeremy T. Fineman, and Phillip B. Gibbons
    #theory, #parallel-ric, #list/tree contraction, #experiments, #code available
    SODA
     ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015   
    Paper   
  • [8] Ray Specialized BVH Contraction
    Yan Gu, Yong He, and Guy E. Blelloch
    #graphics, #data-structure, #BVH, #experiments
    PG
     Pacific Graphics. Computer Graphics Forum (PG), 2015   
    Paper   
  • 2014:
    [7] Extending the Graphics Pipeline with Adaptive, Multi-Rate Shading
    Yong He, Yan Gu, and Kayvon Fatahalian
    #graphics, #architecture, #experiments
    SIGGRAPH
     ACM Transactions on Graphics (SIGGRAPH), 2014   
    Paper   Video  Page  
  • [6] Fair Evaluation of Global Network Aligners
    Joseph Crawford, Yihan Sun, and Tijana Milenkovic
    #computational biology, #graph algorithms, #protein-protein interaction (PPI) networks, #graph alignment, #experiments
    AMB
     Algorithms for Molecular Biology (AMB), 2014   
    Paper   ArXiV  
  • 2013:
    [5] Influence Maximization in Dynamic Social Networks
    Honglei Zhuang, Yihan Sun, Jie Tang,  Zhang Jialin, and Xiaoming Sun
    #data mining, #social networks, #social influence, #(dynamic) influence maximization, #maximum gap probing (MaxG), #experiments
    ICDM
     IEEE International Conference on Data Mining (ICDM), 2013   
    Paper   ArXiV  Slides  
  • [4] Efficient BVH Construction via Approximate Agglomerative Clustering
    Yan Gu, Yong He, Kayvon Fatahalian, and Guy E. Blelloch
    #graphics, #data-structure, #BVH, #experiments, #code available
    HPG
     High Performance Graphics (HPG), 2013   
    Paper   Code  Page  
  • [3] Mixed-Domain Edge-Aware Image Manipulation
    Xian-Ying Li, Yan Gu, Shi-Min Hu, and Ralph R. Martin
    #graphics, #image-processing, #experiments, #code available
    TIP
     IEEE Transactions on Image Processing (TIP), 2013   
    Paper   Code  Page  
  • [2] Algorithms on Minimizing the Maximum Sensor Movement for Barrier Coverage of a Linear Domain
    Danny Z. Chen, Yan Gu, Jian Li, and Haitao Wang
    #theory, #geometry
    SWAT
     SWAT. Discrete & Computational Geometry (SWAT), 2013   
    Paper   
  • 2011:
    [1] A Geometric Study of V-style Pop-ups: Theories and Algorithms
    Xian-Ying Li, Tao Ju, Yan Gu, and Shi-Min Hu
    #graphics, #experiments, #code available
    SIGGRAPH
     ACM Transactions on Graphics (SIGGRAPH), 2011   
    Paper   Video  Page