Julian Shun   信哲文

Publications

  1. Jessica Shi, Laxman Dhulipala, and Julian Shun
    Parallel Algorithms for Hierarchical Nucleus Decomposition
    To appear in Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD), 2024.
  2. Quanquan Liu, Julian Shun, and Igor Zablotchi
    Parallel k-core Decomposition with Batched Updates and Asynchronous Reads
    To appear in Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 2024.
    pdf   arXiv   Source code
  3. Pattara Sukprasert, Quanquan Liu, Laxman Dhulipala, and Julian Shun
    Practical Parallel Algorithms for Near-Optimal Densest Subgraphs on Massive Graphs
    Proceedings of the SIAM Meeting on Algorithm Engineering and Experiments (ALENEX), pp. 59-73, 2024.
    pdf   arXiv   Source code
  4. Zhi Wei Gan, Grace Cai, Noble Harasha, Nancy Lynch, and Julian Shun
    ParSwarm: A C++ Framework for Evaluating Distributed Algorithms for Robot Swarms
    Proceedings of the Workshop on Advanced Tools, Programming Languages, and Platforms for Implementing and Evaluating Algorithms for Distributed Systems (ApPLIED), Article No. 14, pp. 1-5, 2023.
    pdf   Source code
  5. Yihao Huang, Shangdi Yu, and Julian Shun
    Faster Parallel Exact Density-Peak Clustering
    Proceedings of the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), pp. 49-62, 2023.
    pdf   arXiv   Source code
  6. Shangdi Yu and Julian Shun
    Parallel Filtered Graphs for Hierarchical Clustering
    Proceedings of the IEEE International Conference on Data Engineering (ICDE), 2023.
    pdf   arXiv   Source code
  7. Yihao Huang, Claire Wang, Jessica Shi, and Julian Shun
    Efficient Algorithms for Parallel Bi-core Decomposition
    Proceedings of the SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS), pp. 17-32, 2023.
    pdf   Source code
  8. Jessica Shi, Louisa Huang, and Julian Shun
    Parallel Five-Cycle Counting Algorithms
    ACM Journal of Experimental Algorithmics (JEA), Vol. 27, Article No. 4:1, pp.1-23, 2022.
    Special Issue of SEA 2021
    pdf   Source code
  9. Laxman Dhulipala, Quanquan Liu, Sofya Raskhodnikova, Jessica Shi, Julian Shun, and Shangdi Yu
    Differential Privacy from Locally Adjustable Graph Algorithms: k-Core Decomposition, Low Outdegree Ordering, and Densest Subgraphs
    Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), pp. 754-765, 2022.
    pdf   arXiv
  10. Yiqiu Wang, Rahul Yesantharao, Shangdi Yu, Laxman Dhulipala, Yan Gu, and Julian Shun
    ParGeo: A Library for Parallel Computational Geometry
    Proceedings of the European Symposium on Algorithms (ESA), pp. 88:1-88:19, 2022.
    pdf   arXiv   Source code
  11. Jessica Shi and Julian Shun
    Parallel Algorithms for Butterfly Computations
    Massive Graph Analytics, pp. 287-330, 2022. (Earlier version appears in APOCS 2020.)
    Book   Source code
  12. Quanquan Liu, Jessica Shi, Shangdi Yu, Laxman Dhulipala, and Julian Shun
    Parallel Batch-Dynamic Algorithms for k-Core Decomposition and Related Graph Problems
    Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 191-204, 2022.
    Best Paper Award
    pdf   arXiv   Source code
  13. Tom Tseng, Laxman Dhulipala, and Julian Shun
    Parallel Batch-Dynamic Minimum Spanning Forest and the Efficiency of Dynamic Agglomerative Graph Clustering
    Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 233-245, 2022.
    pdf   arXiv
  14. Jessica Shi, Laxman Dhulipala, and Julian Shun
    Theoretically and Practically Efficient Parallel Nucleus Decomposition
    Proceedings of the VLDB Endowment, 15(3), pp. 583-596, 2022.
    pdf   arXiv   Source code
  15. Shangdi Yu, Yiqiu Wang, Yan Gu, Laxman Dhulipala, and Julian Shun
    ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain
    Proceedings of the VLDB Endowment, 15(2), pp. 285-298, 2022.
    pdf   arXiv   Source code
  16. Siddhartha Jayanti and Julian Shun
    Fast Arrays: Atomic Arrays with Constant Time Initialization
    Proceedings of the International Symposium on Distributed Computing (DISC), pp. 25:1-25:19, 2021.
    pdf
  17. Yiqiu Wang, Shangdi Yu, Laxman Dhulipala, Yan Gu, and Julian Shun
    GeoGraph: A Framework for Graph Processing on Geometric Data
    ACM SIGOPS Operating Systems Review, Vol. 55 Issue 1, pp. 38-46, 2021.
    pdf   Source code
  18. Jessica Shi, Laxman Dhulipala, and Julian Shun
    Parallel Clique Counting and Peeling Algorithms
    Proceedings of the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), pp. 135-146, 2021.
    pdf   arXiv   Source code
  19. 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
    Proceedings of the IEEE/ACM International Symposium on Computer Architecture (ISCA), pp. 429-442, 2021.
    pdf
  20. Louisa Huang, Jessica Shi, and Julian Shun
    Parallel Five-Cycle Counting Algorithms
    Proceedings of the International Symposium on Experimental Algorithms (SEA), pp. 2:1-2:18, 2021.
    Invited to Special Issue
    pdf   Source code
  21. Yiqiu Wang, Shangdi Yu, Yan Gu, and Julian Shun
    A Parallel Batch-Dynamic Data Structure for the Closest Pair Problem
    Proceedings of the International Symposium on Computational Geometry (SoCG), pp. 60:1-60:16, 2021.
    pdf   arXiv   Source code
  22. Yiqiu Wang, Shangdi Yu, Yan Gu, and Julian Shun
    Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering
    Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD), pp. 1982-1995, 2021.
    pdf   arXiv   Source code
  23. Tom Tseng, Laxman Dhulipala, and Julian Shun
    Parallel Index-Based Structural Graph Clustering and Its Approximation
    Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD), pp. 1851-1864, 2021.
    pdf   arXiv   Source code
  24. 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
    pdf   Website
  25. 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.
    pdf   arXiv (full version)   Source code
  26. 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.
    pdf   arXiv (full version)
  27. 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.
    pdf
  28. Laxman Dhulipala, Guy Blelloch, and Julian Shun
    Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable
    ACM Transactions on Parallel Computing (TOPC), Vol. 8 Issue 1, Article No. 4, 2021.
    Special Issue of SPAA 2018
    pdf   Website
  29. Erfan Zamanian, Julian Shun, Carsten Binnig, and Tim Kraska
    Chiller: Contention-centric Transaction Execution and Data Partitioning for Modern Networks
    ACM SIGMOD Record, Vol. 50 Issue 1, pp. 15-22, 2021. (Earlier and longer version appears in SIGMOD 2020.)
    2021 ACM SIGMOD Research Highlight Award
    pdf
  30. 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.
    pdf   arXiv (full version)   Source code
  31. 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.
    pdf   arXiv (full version)   Source code
  32. 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.
    pdf   arXiv (full version)   Source code
  33. 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.
    pdf
  34. 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
    pdf
  35. 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.
    pdf   arXiv (full version)    Source code
  36. 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.
    pdf   Website
  37. 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.
    pdf
  38. Julian Shun
    Practical Parallel Hypergraph Algorithms
    Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), pp. 232-249, 2020.
    pdf   Source code
  39. 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.
    pdf   Website
  40. 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.
    pdf   arXiv (full version)   Source code
  41. Julian Shun
    Improved Parallel Construction of Wavelet Trees and Rank/Select Structures
    Information and Computation, 2020.
    Special Issue of DCC 2017-2018
    arXiv
  42. 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. (Earlier version appears in SPAA 2016.)
    pdf
  43. 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
    pdf   arXiv (full version)   Source code
  44. 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
    pdf   Source code
  45. 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
    pdf   Source code
  46. 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.
    pdf   Website
  47. Laxman Dhulipala, Guy Blelloch, and Julian Shun
    Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable
    Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 393-404, 2018. (Journal version in Transactions of Parallel Computing, 2021, special issue of SPAA 2018.)
    Best Paper Award
    pdf   Website
  48. 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.
    pdf   arXiv (full version)
  49. 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.
    pdf   arXiv (full version)
  50. 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.
    pdf   arXiv (full version)
  51. Kimon Fountoulakis, Farbod Roosta-Khorasani, Julian Shun, Xiang Cheng, and Michael Mahoney.
    Variational Perspective on Local Graph Clustering
    Mathematical Programming, Series B, Vol. 17, pp. 553-573, 2017.
    arXiv
  52. 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
    pdf   Source code
  53. 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.
    pdf   Source code
  54. Julian Shun
    Improved Parallel Construction of Wavelet Trees and Rank/Select Structures
    Proceedings of the IEEE Data Compression Conference (DCC), pp. 92-101, 2017. (Journal version in Information and Computation, 2020, special issue of DCC 2017-2018.)
    arXiv (full version)
  55. 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.
    pdf
  56. 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.
    pdf
  57. Guy Blelloch, Yan Gu, Julian Shun, and Yihan Sun
    Parallelism in Randomized Incremental Algorithms
    Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 467-478, 2016. (Journal version in Journal of the ACM, 2020.)
    pdf
  58. 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.
    pdf
  59. Julian Labeit, Julian Shun, and Guy Blelloch
    Parallel Lightweight Wavelet Tree, Suffix Array and FM-Index Construction
    Proceedings of the IEEE Data Compression Conference (DCC), pp. 33-42, 2016. (Journal version in Journal of Discrete Algorithms, 2017.)
    pdf   Source code
  60. 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.
    arXiv (full version)
  61. 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.
    pdf
  62. 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.
    pdf
  63. 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.
    pdf
  64. Julian Shun and Kanat Tangwongsan
    Multicore Triangle Computations Without Tuning
    Proceedings of the IEEE International Conference on Data Engineering (ICDE), pp. 149-160, 2015.
    pdf   Source code
  65. 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.
    pdf   Webpage
  66. Julian Shun
    Parallel Wavelet Tree Construction
    Proceedings of the IEEE Data Compression Conference (DCC), pp. 63-72, 2015.
    Capocelli Prize for Best Student Paper
    arXiv (full version)   Source code
  67. 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.
    pdf
  68. 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. (Earlier version appears in ALENEX 2011.)
    pdf   Source code
  69. 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.
    pdf
  70. 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.
    pdf
  71. 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.
    pdf   Source code
  72. 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.
    pdf
  73. 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.
    pdf
  74. 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.
    pdf   Source code
  75. 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.
    pdf   Webpage
  76. 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.
    pdf   MIS Source Code   Maximal Matching Source Code
  77. Julian Shun, Guy Blelloch, Jeremy Fineman, Phillip Gibbons, Aapo Kyrola, Harsha 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.
    pdf   Website
  78. 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.
    pdf   Website
  79. Guy Blelloch and Julian Shun
    A Simple Parallel Cartesian Tree Algorithm and its Application to Suffix Tree Construction
    Proceedings of the SIAM Meeting on Algorithm Engineering and Experiments (ALENEX), pp. 48-58, 2011. (Journal version in ACM Transactions on Parallel Computing, 2014.)
    pdf   Source code
  80. David Aldous and Julian Shun
    Connected Spatial Networks over Random Points and a Route-Length Statistic
    Statistical Science, Vol. 25, No. 3, pp. 275-288, 2010.
    pdf

Other