## Julian Shun 信哲文Assistant Professor (Associate Professor effective July 2021)Douglas T. Ross Career Development Professor of Software Technology Electrical Engineering and Computer Science Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology Office: 32-G736 Email: jshun at mit.edu Address |
LinksI am teaching 6.886: Algorithm Engineering in Spring 2021. MIT Fast Code Seminar Papers on graph analytics |

I am an assistant professor at MIT in the EECS department and a principal investigator in CSAIL. Prior to that, I was a Miller Research Fellow at UC Berkeley working with Michael Mahoney. I obtained my Ph.D. from Carnegie Mellon University, and was advised by Guy Blelloch.

- Julian Shun

Practical Parallel Hypergraph Algorithms

Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), pp. 232-249, 2020.

- Laxman Dhulipala, Guy Blelloch, and Julian Shun

Low-Latency Graph Streaming Using Compressed Purely-Functional Trees

Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pp. 918-934, 2019.

**Distinguished Paper Award**

Source code - Laxman Dhulipala, Guy Blelloch, and Julian Shun

Julienne: A Framework for Parallel Graph Algorithms using Work-efficient Bucketing

Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 293-304, 2017. - Julian Shun, Farbod Roosta-Khorasani, Kimon Fountoulakis, and Michael Mahoney

Parallel Local Graph Clustering

Proceedings of the VLDB Endowment, 9(12), pp. 1041-1052, 2016. - Julian Shun

An Evaluation of Parallel Eccentricity Estimation Algorithms on Undirected Real-World Graphs

Proceedings of the ACM Conference on Knowledge Discovery and Data Mining (KDD), pp. 1095-1104, 2015. - Julian Shun, Laxman Dhulipala,
and Guy
Blelloch

Smaller and Faster: Parallel Processing of Compressed Graphs with Ligra+

Proceedings of the IEEE Data Compression Conference (DCC), pp. 403-412, 2015. - Julian Shun and Guy Blelloch

Ligra: A Lightweight Graph Processing Framework for Shared Memory

Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), pp. 135-146, 2013.

Webpage for Ligra/Ligra+ Source code

- Laxman Dhulipala, Charles McGuffey, Hongbo Kang, Yan Gu, Guy Blelloch, Phillip Gibbons, and Julian Shun

Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs

Proceedings of the VLDB Endowment, 13(9), pp. 1598-1613, 2020.

Source code

- Ajay Brahmakshatriya,
Emily Furst,
Victor Ying,
Claire Hsu,
Changwan Hong,
Max Ruttenberg,
Yunming Zhang,
Tommy Jung,
Dustin Richmond,
Michael Taylor,
Julian Shun,
Mark Oskin,
Daniel Sanchez, and
Saman Amarasinghe

Taming the Zoo: A Unified Graph Compiler Framework for Novel Architectures

To appear in Proceedings of the IEEE/ACM International Symposium on Computer Architecture (ISCA), 2021. - Ajay Brahmakshatriya, Yunming Zhang, Changwan Hong, Shoaib Kamil, Julian Shun, and Saman Amarasinghe

Compiling Graph Applications for GPUs with GraphIt

Proceedings of the International Symposium on Code Generation and Optimization (CGO), pp. 55-69, 2021.

**Best Paper Award**

- Yunming Zhang, Ajay Brahmakshatriya, Xinyi Chen, Laxman Dhulipala, Shoaib Kamil, Saman Amarasinghe, and Julian Shun

Optimizing Ordered Graph Algorithms with Graphlt

Proceedings of the International Symposium on Code Generation and Optimization (CGO), pp. 158-170, 2020.

- Yunming Zhang, Mengjiao Yang, Riyadh Baghdadi, Shoaib Kamil, Julian Shun, and Saman Amarasinghe

GraphIt: A High-Performance Graph DSL

Proceedings of Object-Oriented Programming, Systems, Languages & Applications (OOPSLA), pp. 121:1-121:30, 2018.

Website

- Louisa Huang, Jessica Shi, and Julian Shun

Parallel Five-Cycle Counting Algorithms

To appear in Proceedings of the International Symposium on Experimental Algorithms (SEA), 2021. - Laxman Dhulipala, Quanquan Liu, Julian Shun, and Shangdi Yu

Parallel Batch-Dynamic k-Clique Counting

Proceedings of the SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS), pp. 129-143, 2021.

Source code - Changwan Hong, Laxman Dhulipala, and Julian Shun

Exploring the Design Space of Static and Incremental Graph Connectivity Algorithms on GPUs

Proceedings of International Conference on Parallel Architectures and Compilation Techniques (PACT), pp. 55-69 2020.

Source code - Laxman Dhulipala, Changwan Hong, and Julian Shun

ConnectIt: A Framework for Static and Incremental Parallel Graph Connectivity Algorithms

Proceedings of the VLDB Endowment, 14(4), pp. 653-667, 2020.

Source code - Laxman Dhulipala, Jessica Shi, Tom Tseng, Guy Blelloch, and Julian Shun

The Graph Based Benchmark Suite (GBBS)

Proceedings of the Joint Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA), pp. 1-8, 2020.

Website - Joana M. F. da Trindade, Konstantinos Karanasos, Carlo Curino, Samuel Madden, and Julian Shun

Kaskade: Graph Views for Efficient Graph Analytics

Proceedings of the IEEE International Conference on Data Engineering (ICDE), pp. 193-204, 2020.

- Jessica Shi and Julian Shun

Parallel Algorithms for Butterfly Computations

Proceedings of the SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS), pp. 16-30, 2020.

Source code - Laxman Dhulipala, Guy Blelloch, and Julian Shun

Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable

ACM Transactions on Parallel Computing (TOPC), 2021.**Best Paper Award of SPAA 2018**,**Special Issue in TOPC 2021**

Website -
Niklas Baumstark, Guy Blelloch, and Julian Shun

Efficient Implementation of a Synchronous Parallel Push-Relabel Algorithm

Proceedings of the European Symposium on Algorithms (ESA), pp. 106-117, 2015. - Julian Shun and Kanat Tangwongsan

Multicore Triangle Computations Without Tuning

Proceedings of the IEEE International Conference on Data Engineering (ICDE), pp. 149-160, 2015.

Source code - Julian Shun, Laxman Dhulipala, and Guy Blelloch

A Simple and Practical Linear-Work Parallel Algorithm for Connectivity

Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 143-153, 2014.

Source code - Aapo Kyrola, Julian Shun, and Guy Blelloch

Beyond Synchronous: New Techniques for External Memory Graph Algorithms

Proceedings of the International Symposium on Experimental Algorithms (SEA), pp. 123-137, 2014.

- Yiqiu Wang, Shangdi Yu, Yan Gu, and Julian Shun

A Parallel Batch-Dynamic Data Structure for the Closest Pair Problem

To appear in Proceedings of the International Symposium on Computational Geometry (SoCG), 2021.

- Yiqiu Wang, Shangdi Yu, Yan Gu, and Julian Shun

Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering

To appear in Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD), 2021.

- Yiqiu Wang, Yan Gu, and Julian Shun

Theoretically-Efficient and Practical Parallel DBSCAN

Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD), pp. 2555-2571, 2020.

Source code

- Yan Gu, Omar Obeya, and Julian Shun

Parallel In-Place Algorithms: Theory and Practice

Proceedings of the SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS), pp. 114-128, 2021. - Omar Obeya, Endrias Kahssay, Edward Fan, and Julian Shun

Theoretically-Efficient and Practical Parallel In-Place Radix Sorting

Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 213-224, 2019.**Invited to Special Issue**

Source code

- Guy Blelloch, Laxman Dhulipala, Phillip Gibbons, Yan Gu, Charles McGuffey, and Julian Shun

The Read-Only Semi-External Model

Proceedings of the SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS), pp. 70-84, 2021.

- Laxman Dhulipala, Charles McGuffey, Hongbo Kang, Yan Gu, Guy Blelloch, Phillip Gibbons, and Julian Shun

Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs

Proceedings of the VLDB Endowment, pp. 1598-1613, 2020.

- Guy Blelloch, Phillip Gibbons, Yan Gu, Charles McGuffey, and Julian Shun

The Parallel Persistent Memory Model

Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 247-258, 2018. - Guy Blelloch, Yan Gu, Julian Shun, and Yihan Sun

Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry

Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 235-246, 2018. - Naama Ben-David, Guy Blelloch, Jeremy Fineman, Phillip Gibbons, Yan Gu, Charles McGuffey, and Julian Shun

Implicit Decomposition for Write-Efficient Connectivity Algorithms

Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 711-722, 2018. - Guy Blelloch, Jeremy Fineman, Phillip Gibbons, Yan Gu, and Julian Shun

Efficient Algorithms with Asymmetric Read and Write Costs

Proceedings of the European Symposium on Algorithms (ESA), pp. 14:1-14:18, 2016. - Naama Ben-David, Guy Blelloch, Jeremy Fineman, Phillip Gibbons, Yan Gu, Charles McGuffey, and Julian Shun

Parallel Algorithms for Asymmetric Read-Write Costs

Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 145-156, 2016. - Guy Blelloch, Jeremy Fineman, Phillip Gibbons, Yan Gu, and Julian Shun

Sorting with Asymmetric Read and Write Costs

Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 1-12, 2015.

- Erfan Zamanian, Julian Shun, Carsten Binnig, and Tim Kraska

Chiller: Contention-centric Transaction Execution and Data Partitioning for Modern Networks

Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD), pp. 511-526, 2020.

**Invited to Best of SIGMOD 2020**

**2021 ACM SIGMOD Research Highlight Award**

- Guy Blelloch, Yan Gu, Julian Shun, and Yihan Sun

Randomized Incremental Convex Hull is Highly Parallel

Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 103-115, 2020.

- Guy Blelloch, Yan Gu, Julian Shun, and Yihan Sun

Parallelism in Randomized Incremental Algorithms

Journal of the ACM, Vol. 67 Issue 5, Article No. 27, 2020. - Yu Xia, Xiangyao Yu, William Moses, Julian Shun, and Srini Devadas

LiTM: A Lightweight Deterministic Software Transactional Memory System

Proceedings of the International Workshop on Programming Models and Applications for Multicores and Manycores (PMAM), pp. 1-10, 2019.**Invited to Special Issue**

Source code - Julian Shun, Yan Gu, Guy Blelloch, Jeremy Fineman, and Phillip Gibbons

Sequential Random Permutation, List Contraction and Tree Contraction are Highly Parallel

Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 431-448, 2015. - Julian Shun and Guy Blelloch

Phase-concurrent Hash Tables for Determinism

Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 96-107, 2014. - Julian Shun, Guy Blelloch, Jeremy Fineman, and Phillip Gibbons

Reducing Contention Through Priority Updates

Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 152-163, 2013. - Guy Blelloch, Jeremy Fineman, and Julian
Shun

Greedy Sequential Maximal Independent Set and Matching are Parallel on Average

Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 308-317, 2012.

MIS Source Code Maximal Matching Source Code - Guy Blelloch, Jeremy Fineman,
Phillip Gibbons, and Julian Shun

Internally Deterministic Parallel Algorithms Can Be Fast

Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), pp. 181-192, 2012.

Website

- Julian Shun

Improved Parallel Construction of Wavelet Trees and Rank/Select Structures

Information and Computation, 2020.**Special Issue of DCC 2017-2018** - Julian Labeit, Julian Shun,
and Guy
Blelloch

Parallel lightweight wavelet tree, suffix array and FM-index construction

Journal of Discrete Algorithms, Vol. 43, pp. 2-17, 2017.**Special Issue of DCC 2016**

Source code - Julian Shun

Parallel Wavelet Tree Construction

Proceedings of the IEEE Data Compression Conference (DCC), pp. 63-72, 2015.**Capocelli Prize for Best Student Paper**

Source code - Julian Shun

Fast Parallel Computation of Longest Common Prefixes

Proceedings of the ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis (SC), pp. 387-398, 2014. - Julian Shun and Guy Blelloch

A Simple Parallel Cartesian Tree Algorithm and its Application to Parallel Suffix Tree Construction

ACM Transactions on Parallel Computing (TOPC), Vol. 1 Issue 1, Article No. 8, 2014.

Source code - Julian Shun and Fuyao Zhao (joint first author)

Practical Parallel Lempel-Ziv Factorization

Proceedings of the IEEE Data Compression Conference (DCC), pp. 123-132, 2013.

Source code

- Yan Gu,
Julian Shun, Yihan Sun,
and Guy
Blelloch

A Top-Down Parallel Semisort

Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 24-34, 2015.

- Julian Shun, Guy Blelloch, Jeremy Fineman,
Phillip Gibbons, Aapo Kyrola, Vardhan Simhadri, and Kanat Tangwongsan

Brief Announcement: The Problem Based Benchmark Suite

Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 68-70, 2012.

Website

- Shared Memory Parallelism Can Be Simple, Fast, and Scalable, Carnegie Mellon University, 2015.

Winner of the ACM Doctoral Dissertation Award and the CMU SCS Doctoral Dissertation Award

Revised version available from ACM Digital Library and ACM Books.