Publications - Experimental Evaluations

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

[Back to full publication list]

• 2025:
  [27] Parallel Point-to-Point Shortest Paths and Batch Queries (To Appear)
  Xiaojun Dong, Andy Li, Yan Gu, and Yihan Sun
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2025  [BibTeX]
  @inproceedings{ Dong2025Parallel,
  title = { Parallel Point-to-Point Shortest Paths and Batch Queries (To Appear) },
  author = {Dong, Xiaojun and Li, Andy and Gu, Yan and Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2025 }
  }

  [copy]
  
  
    Software:
  Orionet: Parallel Single and Batch PPSP  [Link]
  Paper   ArXiV  Code  
• [26] New Algorithms for Incremental Minimum Spanning Trees and Temporal Graph Applications (To Appear)
  Xiangyun Ding, Yan Gu, and Yihan Sun
  
  ACDA
   SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2025  [BibTeX]
  @inproceedings{ Ding2025New,
  title = { New Algorithms for Incremental Minimum Spanning Trees and Temporal Graph Applications (To Appear) },
  author = {Ding, Xiangyun and Gu, Yan and Sun, Yihan},
  booktitle = {SIAM Conference on Applied and Computational Discrete Algorithms (ACDA)},
  year = { 2025 }
  }

  [copy]
  
  
    Software:
  AM-tree: Anti-Monoply tree for incremental MST and temporal connectivity  [Link]
  Paper   Code  
• [25] Parallel Contraction Hierarchies Can Be Efficient and Scalable
  Zijin Wan, Xiaojun Dong, Letong Wang, Enzuo Zhu, Yan Gu, and Yihan Sun
  
  🏆 Best Paper Finalist!
  ICS
   International Conference on Supercomputing (ICS), 2025  [BibTeX]
  @inproceedings{ Wan2025Parallel,
  title = { Parallel Contraction Hierarchies Can Be Efficient and Scalable },
  author = {Wan, Zijin and Dong, Xiaojun and Wang, Letong and Zhu, Enzuo and Gu, Yan and Sun, Yihan},
  booktitle = {International Conference on Supercomputing (ICS)},
  year = { 2025 }
  }

  [copy]
  
  
    Software:
  SPoCH: Scalable Parallelization of Contraction Hierarchies  [Link]
  
    DOI:
  10.1145/3721145.3725744    [copy]
  Paper   ArXiV  Code  
• [24] Parallel Cluster-BFS and Applications to Shortest Paths
  Letong Wang, Guy Blelloch, Yan Gu, and Yihan Sun
  
  ALENEX
   Algorithm Engineering and Experiments (ALENEX), 2025  [BibTeX]
  @inproceedings{ Wang2025Parallel,
  title = { Parallel Cluster-BFS and Applications to Shortest Paths },
  author = {Wang, Letong and Blelloch, Guy and Gu, Yan and Sun, Yihan},
  booktitle = {Algorithm Engineering and Experiments (ALENEX)},
  year = { 2025 }
  }

  [copy]
  
  
    Software:
  CBFS: Cluster Breadth-First Search  [Link]
  Paper   ArXiV  Code  
• 2024:
  [23] Parallel and (Nearly) Work-Efficient Dynamic Programming
  Xiangyun Ding, Yan Gu, and Yihan Sun
  
  🏆 Outstanding Paper Award (Best paper finalist)!
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2024  [BibTeX]
  @inproceedings{ Ding2024Parallel,
  title = { Parallel and (Nearly) Work-Efficient Dynamic Programming },
  author = {Ding, Xiangyun and Gu, Yan and Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2024 }
  }

  [copy]
  
  
    Software:
  Parallel Work-Efficient Dynamic Programming  [Link]
  Paper   ArXiV  Code  Slides
• [22] ParlayANN: Scalable and Deterministic Parallel Graph-Based Algorithms for Approximate Nearest Neighbor Search
  Magdalen Dobson, Zheqi Shen, Guy Blelloch, Laxman Dhulipala, Yan Gu, Harsha Simhadri, and Yihan Sun
  
  PPoPP
   ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2024  [BibTeX]
  @inproceedings{ Dobson2024ParlayANN:,
  title = { ParlayANN: Scalable and Deterministic Parallel Graph-Based Algorithms for Approximate Nearest Neighbor Search },
  author = {Dobson, Magdalen and Shen, Zheqi and Blelloch, Guy and Dhulipala, Laxman and Gu, Yan and Simhadri, Harsha and Sun, Yihan},
  booktitle = {ACM Symposium on Principles and Practice of Parallel Programming (PPoPP)},
  year = { 2024 }
  }

  [copy]
  
  
    Software:
  ParlayANN: Parallel Graph-Based Algorithms for Approximate Nearest Neighbor Search  [Link]
  
    DOI:
  10.1145/3627535.3638475    [copy]
  Paper   ArXiV  Code  
• [21] Parallel Integer Sort: Theory and Practice
  Xiaojun Dong, Laxman Dhulipala, Yan Gu, and Yihan Sun
  
  PPoPP
   ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2024  [BibTeX]
  @inproceedings{ Dong2024Parallel,
  title = { Parallel Integer Sort: Theory and Practice },
  author = {Dong, Xiaojun and Dhulipala, Laxman and Gu, Yan and Sun, Yihan},
  booktitle = {ACM Symposium on Principles and Practice of Parallel Programming (PPoPP)},
  year = { 2024 }
  }

  [copy]
  
  
    Software:
  Parallel Integer Sort  [Link]
  
    DOI:
  10.1145/3627535.3638483    [copy]
  
  HOPC
   Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2024
  Paper   ArXiV  Code  Slides
• [20] 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]
  
  
    Software:
  PaC-IM: Parallel and Compressed Influence Maximization  [Link]
  
    DOI:
  10.14778/3632093.3632104    [copy]
  
  HOPC
   Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2024
  Paper   ArXiV  Code  
• 2023:
  [19] Efficient Parallel Output-Sensitive Edit Distance
  Xiangyun Ding, Xiaojun Dong, Yan Gu, Youzhe Liu, and Yihan Sun
  
  🏆 Best Paper Award!
  ESA
   European Symposium on Algorithms (ESA), 2023  [BibTeX]
  @inproceedings{ Ding2023Efficient,
  title = { Efficient Parallel Output-Sensitive Edit Distance },
  author = {Ding, Xiangyun and Dong, Xiaojun and Gu, Yan and Liu, Youzhe and Sun, Yihan},
  booktitle = {European Symposium on Algorithms (ESA)},
  year = { 2023 }
  }

  [copy]
  
  
    Software:
  Parallel Output-Sensitive Edit Distance  [Link]
  
    DOI:
  10.4230/LIPIcs.ESA.2023.40    [copy]
  
  HOPC
   Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2024
  Paper   ArXiV  Code  Slides
• [18] High-Performance and Flexible Parallel Algorithms for Semisort and Related Problems
  Xiaojun Dong, Yunshu Wu, Zhongqi Wang, Laxman Dhulipala, Yan Gu, and Yihan Sun
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2023  [BibTeX]
  @inproceedings{ Dong2023High-Performance,
  title = { High-Performance and Flexible Parallel Algorithms for Semisort and Related Problems },
  author = {Dong, Xiaojun and Wu, Yunshu and Wang, Zhongqi and Dhulipala, Laxman and Gu, Yan and Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2023 }
  }

  [copy]
  
  
    Software:
  Parallel Semisort  [Link]
  
    DOI:
  10.1145/3558481.3591071    [copy]
  Paper   ArXiV  Code  Slides
• [17] 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]
  
  
    Software:
  Parallel Longest Increasing Subsequence  [Link]
  
    DOI:
  10.1145/3558481.3591069    [copy]
  Paper   ArXiV  Code  Slides
• [16] Parallel Strong Connectivity Based on Faster Reachability
  Letong Wang, Xiaojun Dong, Yan Gu, and Yihan Sun
  
  SIGMOD
   ACM Special Interest Group on Management of Data (SIGMOD), 2023  [BibTeX]
  @inproceedings{ Wang2023Parallel,
  title = { Parallel Strong Connectivity Based on Faster Reachability },
  author = {Wang, Letong and Dong, Xiaojun and Gu, Yan and Sun, Yihan},
  booktitle = {ACM Special Interest Group on Management of Data (SIGMOD)},
  year = { 2023 }
  }

  [copy]
  
  
    Software:
  Parallel SCC, integrated in PASGAL  [Link]
  
    DOI:
  10.1145/3589259    [copy]
  
  ACDA
   Poster presented at the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2023
  
  HOPC
   Poster presented at the Highlights of Parallel Computing (HOPC@SPAA), 2023
  Paper   ArXiV  Code  Slides
• [15] Provably Fast and Space-Efficient Parallel Biconnectivity
  Xiaojun Dong, Letong Wang, Yan Gu, and Yihan Sun
  
  🏆 Best Paper Award!
  PPoPP
   ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2023  [BibTeX]
  @inproceedings{ Dong2023Provably,
  title = { Provably Fast and Space-Efficient Parallel Biconnectivity },
  author = {Dong, Xiaojun and Wang, Letong and Gu, Yan and Sun, Yihan},
  booktitle = {ACM Symposium on Principles and Practice of Parallel Programming (PPoPP)},
  year = { 2023 }
  }

  [copy]
  
  
    Software:
  Parallel BCC, integrated in PASGAL  [Link]
  
    DOI:
  10.1145/3572848.3577483    [copy]
  
  ACDA
   Poster and oral presentation at the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2023
  
  HOPC
   Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2023
  Paper   ArXiV  Code  Slides
• 2022:
  [14] 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  [BibTeX]
  @inproceedings{ Shen2022Many,
  title = { Many Sequential Iterative Algorithms Can Be Parallel and (Nearly) Work-efficient },
  author = {Shen, Zheqi and Wan, Zijin and Gu, Yan and Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2022 }
  }

  [copy]
  
  
    Software:
  Parallel DP and greedy algorithms  [Link]
  
    DOI:
  10.1145/3490148.3538574    [copy]
  Paper   ArXiV  Slides
• [13] 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  [BibTeX]
  @inproceedings{ Dhulipala2022PaC-trees:,
  title = { PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections },
  author = {Dhulipala, Laxman and Blelloch, Guy and Gu, Yan and Sun, Yihan},
  booktitle = {ACM Conference on Programming Language Design and Implementation (PLDI)},
  year = { 2022 }
  }

  [copy]
  
  
    Software:
  CPAM: Compressed Parallel Augmented Maps  [Link]
  
    DOI:
  10.1145/3519939.3523733    [copy]
  Paper   ArXiV  Code  Slides
• [12] Joinable Parallel Balanced Binary Trees
  Guy E. Blelloch, Daniel Ferizovic, and Yihan Sun
  
  TOPC
   ACM Transactions on Parallel Computing (TOPC), 2022  [BibTeX]
  @inproceedings{ Blelloch2022Joinable,
  title = { Joinable Parallel Balanced Binary Trees },
  author = {Blelloch, Guy E. and Ferizovic, Daniel and Sun, Yihan},
  booktitle = {ACM Transactions on Parallel Computing (TOPC)},
  year = { 2022 }
  }

  [copy]
  
  
    Software:
  Part of the PAM library: Parallel Augmented Maps  [Link]
  
    DOI:
  10.1145/3512769    [copy]
  Paper   Code  
• 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]
  
  
    Software:
  Rho-Stepping: Parallel single-source shortes paths, integrated in PASGAL  [Link]
  
    DOI:
  10.1145/3409964.3461782    [copy]
  Paper   Video  ArXiV  Code  
• 2019:
  [10] 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), 2019  [BibTeX]
  @inproceedings{ Sun2019On,
  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 = { 2019 }
  }

  [copy]
  
  
    Software:
  Part of the PAM library: Parallel Augmented Maps  [Link]
  
    DOI:
  10.14778/3364324.3364334    [copy]
  Paper   Video  Code  
• [9] 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]
  
  
    Software:
  Efficient Garbage Collection for Transactional Systems  [Link]
  
    DOI:
  10.1145/3323165.3323185    [copy]
  Paper   ArXiV  
• 2018:
  [8] 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]
  Paper   ArXiV  
• [7] 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]
  
  
    Software:
  Part of the PAM library: Parallel Augmented Maps  [Link]
  
    DOI:
  10.1145/3200691.3178509    [copy]
  Paper   ArXiV  Code  
• 2016:
  [6] 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]
  
  
    Software:
  Part of the PAM library: Parallel Augmented Maps  [Link]
  
    DOI:
  10.1145/2935764.2935768    [copy]
  Paper   ArXiV  Code  
• [5] Parallel Shortest-paths Using Radius Stepping
  Guy E. Blelloch, Yan Gu, Yihan Sun, and Kanat Tangwongsan
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016  [BibTeX]
  @inproceedings{ Blelloch2016Parallel,
  title = { Parallel Shortest-paths Using Radius Stepping },
  author = {Blelloch, Guy E. and Gu, Yan and Sun, Yihan and Tangwongsan, Kanat},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2016 }
  }

  [copy]
  
  
    DOI:
  10.1145/2935764.2935765    [copy]
  Paper   
• 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  [BibTeX]
  @inproceedings{ Sun2015Simultaneous,
  title = { Simultaneous Optimization of Both Node and Edge Conservation in Network Alignment via WAVE },
  author = {Sun, Yihan and Crawford, Joseph and Tang, Jie and Milenkovic, Tijana},
  booktitle = {Workshop on Algorithms in Bioinformatics (WABI)},
  year = { 2015 }
  }

  [copy]
  
  
    DOI:
  10.1007/978-3-662-48221-6_2    [copy]
  Paper   ArXiV  
• [3] A Top-down Parallel Semisort
  Yan Gu, Julian Shun, Yihan Sun, and Guy E. Blelloch
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2015  [BibTeX]
  @inproceedings{ Gu2015A,
  title = { A Top-down Parallel Semisort },
  author = {Gu, Yan and Shun, Julian and Sun, Yihan and Blelloch, Guy E.},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2015 }
  }

  [copy]
  
  Paper   Slides
• 2014:
  [2] Fair Evaluation of Global Network Aligners
  Joseph Crawford, Yihan Sun, and Tijana Milenkovic
  
  AMB
   Algorithms for Molecular Biology (AMB), 2014  [BibTeX]
  @inproceedings{ Crawford2014Fair,
  title = { Fair Evaluation of Global Network Aligners },
  author = {Crawford, Joseph and Sun, Yihan and Milenkovic, Tijana},
  booktitle = {Algorithms for Molecular Biology (AMB)},
  year = { 2014 }
  }

  [copy]
  
  
    DOI:
  10.1145/2755573.2755597    [copy]
  Paper   ArXiV  
• 2013:
  [1] Influence Maximization in Dynamic Social Networks
  Honglei Zhuang, Yihan Sun, Jie Tang,  Zhang Jialin, and Xiaoming Sun
  
  ICDM
   IEEE International Conference on Data Mining (ICDM), 2013  [BibTeX]
  @inproceedings{ Zhuang2013Influence,
  title = { Influence Maximization in Dynamic Social Networks },
  author = {Zhuang, Honglei and Sun, Yihan and Tang, Jie and Zhang Jialin and Sun, Xiaoming},
  booktitle = {IEEE International Conference on Data Mining (ICDM)},
  year = { 2013 }
  }

  [copy]
  
  
    DOI:
  10.1109/ICDM.2013.145    [copy]
  Paper   ArXiV  Slides