Laxman Dhulipala

I am an Assistant Professor in the Department of Computer Science at the University of Maryland, College Park, and a research scientist at Google Research with the Graph Mining team.

I obtained my Ph.D. from Carnegie Mellon University, where I was advised by Guy Blelloch, and was a postdoc at MIT working with Julian Shun.

I am broadly interested in efficient parallel algorithms, e.g., for parallel clustering and parallel graph processing. I am also interested in models of parallel computation motivated by emerging hardware and exploring these models theoretically and practically.

Teaching

• S24: CMSC858N, Scalable Parallel Algorithms and Data Structures
• F23: CMSC451: Design and Analysis of Computer Algorithms
• S23: CMSC858N, Scalable Parallel Algorithms and Data Structures
• F22: CMSC451: Design and Analysis of Computer Algorithms

Publications

Optimal Parallel Algorithms for Dendrogram Computation and Single-Linkage Clustering
Laxman Dhulipala, Xiaojun Dong, Kishen Gowda, and Yan Gu
To appear at SPAA'24
Parallel and Sequential Hardness of Hierarchical Graph Clustering
Mohammad Hossein Bateni, Laxman Dhulipala, Kishen Gowda, D Ellis Hershkowitz, Rajesh Jarayam and Jakub Łącki
To appear at ICALP'24
Scaling Graph-Based ANNS Algorithms to Billion-Size Datasets: A Comparative Analysis
[arxiv]
Magdalen Dobson, Zheqi Shen, Guy E. Blelloch, Laxman Dhulipala, Yan Gu, Harsha Vardhan Simhadri, and Yihan Sun
Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 2024.
Parallel Integer Sort: Theory and Practice
[arxiv]
Xiaojun Dong, Laxman Dhulipala, Yan Gu, and Yihan Sun
Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 2024.
TeraHAC: Hierarchical Agglomerative Clustering of Trillion-Edge Graphs
[arxiv]
Laxman Dhulipala, Jason Lee, Jakub Łącki, and Vahab Mirrokni
Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD), 2024.
Parallel Algorithms for Hierarchical Nucleus Decomposition
[arxiv]
Jessica Shi, Laxman Dhulipala, and Julian Shun
Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD), 2024.
Practical Parallel Algorithms for Near-Optimal Densest Subgraphs on Massive Graphs
[arxiv]
Pattara Sukprasert, Quanquan C. Liu, Laxman Dhulipala, and Julian Shun
Proceedings of the SIAM Meeting on Algorithm Engineering and Experiments (ALENEX), 2024.
Fast, Parallel, and Cache-Friendly Suffix Array Construction
[pdf]
Jamshed Khan, Tobias Rubel, Laxman Dhulipala, Erin K. Molloy, and Rob Patro:
Workshop on Algorithms in Bioinformatics (WABI), 2023.
PIM-trie: A Skew-resistant Trie for Processing-in-Memory.
[pdf]
Hongbo Kang, Yiwei Zhao, Guy E. Blelloch, Laxman Dhulipala, Yan Gu, Charles McGuffey and Phillip B. Gibbons
Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2023.
High-Performance and Flexible Parallel Algorithms for Semisort and Related Problems
[pdf] [arxiv]
Xiaojun Dong, Yunshu Wu, Zhongqi Wang, Laxman Dhulipala, Yan Gu, and Yihan Sun
Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2023.
Towards Lightweight and Automated Representation Learning System for Networks.
[arxiv]
Yuyang Xie, Jiezhong Qiu, Laxman Dhulipala, Wenjian Yu, Jie Tang, Richard Peng, and Chi Wang
IEEE Transactions on Knowledge and Data Engineering, 2023.
Hierarchical Agglomerative Graph Clustering in Poly-Logarithmic Depth
[arxiv]
Laxman Dhulipala, David Eisenstat, Jakub Łącki, Vahab Mirronki, and Jessica Shi
Conference on Neural Information Processing Systems (NeurIPS), 2022.
PIM-tree: A Skew-resistant Index for Processing-in-Memory
[arxiv]
Hongbo Kang, Yiwei Zhao, Guy E. Blelloch, Laxman Dhulipala, Yan Gu, Charles McGuffey and Phillip B. Gibbons
Proceedings of the VLDB Endowment, 2022.
Best Paper Runner Up
Differential Privacy from Locally Adjustable Graph Algorithms: k-Core Decomposition, Low Out-Degree Ordering, and Densest Subgraphs
[arxiv]
Laxman Dhulipala, Quanquan C. Liu, Sofya Raskhodnikova, Jessica Shi, Julian Shun, and Shangdi Yu
Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), 2022.
ParGeo: A Library for Parallel Computational Geometry
[arxiv]
Yiqiu Wang, Rahul Yesantharao, Shangdi Yu, Laxman Dhulipala, Yan Gu, and Julian Shun
Proceedings of the European Symposium on Algorithms (ESA), 2022.
Parallel Batch-Dynamic Algorithms for k-Core Decomposition and Related Graph Problems
[pdf]
Quanquan Liu, Jessica Shi, Shangdi Yu, Laxman Dhulipala, and Julian Shun
Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2022.
Best Paper Award
Theoretically and Practically Efficient Parallel Nucleus Decomposition
[pdf] [arxiv]
Jessica Shi, Laxman Dhulipala, and Julian Shun
Proceedings of the VLDB Endowment, 2022.
PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections
[pdf] [code]
Laxman Dhulipala, Guy E. Blelloch, Yan Gu, and Yihan Sun
ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2022.
ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain
[pdf] [arxiv]
Shangdi Yu, Yiqiu Wang, Yan Gu, Laxman Dhulipala, and Julian Shun
To appear in Proceedings of the VLDB Endowment, 2022.
POSTER: The Problem-Based Benchmark Suite (PBBS), V2
[pdf] [code]
Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, Magdalen Dobson, and Yihan Sun
Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 2022.
POSTER: ParGeo: A Library for Parallel Computational Geometry
[pdf] [code]
Yiqiu Wang, Shangdi Yu, Laxman Dhulipala, Yan Gu, and Julian Shun
Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 2022.
Hierarchical Agglomerative Graph Clustering in Nearly Linear Time
[pdf] [arxiv]
Laxman Dhulipala, David Eisenstat, Jakub Łącki, Vahab Mirronki, and Jessica Shi
Proceedings of the International Conference on Machine Learning (ICML), 2021.
Scalable Community Detection via Parallel Correlation Clustering
[pdf] [arxiv] [code]
Jessica Shi, Laxman Dhulipala, David Eisenstat, Jakub Łącki, and Vahab Mirrokni
Proceedings of the VLDB Endowment (PVLDB), 2021.
Parallel Clique Counting and Peeling Algorithms
[pdf] [arxiv] [code]
Jessica Shi, Laxman Dhulipala, and Julian Shun
Proceedings of the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2021.
The Processing-in-Memory Model
[pdf]
Hongbo Kang, Phillip B. Gibbons, Guy E. Blelloch, Laxman Dhulipala, Yan Gu, and Charles McGuffey
Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2021.
GeoGraph: A Framework for Graph Processing on Geometric Data
[pdf] [code]
Yiqiu Wang, Shangdi Yu, Laxman Dhulipala, Yan Gu, and Julian Shun
ACM SIGOPS Operating Systems Review, 2021
LightNE: A Lightweight Graph Processing System for Network Embedding
[pdf] [code]
Jiezhong Qiu, Laxman Dhulipala, Jie Tang, Richard Peng, and Chi Wang
Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD), 2021.
Parallel Index-Based Structural Graph Clustering and Its Approximation
[pdf] [arxiv] [code]
Tom Tseng, Laxman Dhulipala, and Julian Shun
Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD), 2021.
ConnectIt: A Framework for Static and Incremental Parallel Connectivity Algorithms
[pdf] [arxiv] [code]
Laxman Dhulipala, Changwan Hong, and Julian Shun
Proceedings of the VLDB Endowment (PVLDB), 2021.
Parallel Batch-Dynamic k-Clique Counting
[pdf] [arxiv]
Laxman Dhulipala, Quanquan Liu, Julian Shun, and Shangdi Yu
Proceedings of the SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS), 2021.
The Read-Only Semi-External Model
[pdf]
Guy Blelloch, Laxman Dhulipala, Phillip Gibbons, Yan Gu, Charles McGuffey, and Julian Shun
Proceedings of the SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS), 2021.
Parallel Graph Algorithms in Constant Adaptive Rounds: Theory meets Practice
[pdf] [arxiv] [Google AI Blog Post]
Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Łącki, Vahab Mirrokni, and Warren Schudy
Proceedings of the VLDB Endowment (PVLDB), 2020. (To be presented at VLDB'21)
Exploring the Design Space of Static and Incremental Graph Connectivity Algorithms on GPUs
[pdf] [arxiv]
Changwan Hong, Laxman Dhulipala, and Julian Shun
Proceedings of International Conference on Parallel Architectures and Compilation Techniques (PACT), 2020.
Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs
[pdf] [arxiv] [code]
Laxman Dhulipala, Charles McGuffey, Hongbo Kang, Yan Gu, Guy Blelloch, Phillip Gibbons, and Julian Shun
Proceedings of the VLDB Endowment (PVLDB), 2020.
Memorable Paper Award Finalist at the Non-Volatile Memories Workshop (NVMW’20)
The Graph Based Benchmark Suite (GBBS)
[pdf] [code]
Laxman Dhulipala, Jessica Shi, Tom Tseng, Guy E. Blelloch, and Julian Shun
Proceedings of the Joint Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA), 2020
Brief Announcement: ParlayLib – A Toolkit for Parallel Algorithms on Shared-Memory Multicore Machines
[pdf] [code]
Guy E. Blelloch, Daniel Anderson, and Laxman Dhulipala
Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020.
Optimizing Ordered Graph Algorithms with GraphIt
[pdf] [arxiv] [code]
Yunming Zhang, Ajay Brahmakshatriya, Xinyi Chen, Laxman Dhulipala, Shoaib Kamil, Saman Amarasinghe, and Julian Shun
Proceedings of the International Symposium on Code Generation and Optimization (CGO), 2020.
Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds
[pdf] [arxiv]
Laxman Dhulipala, David Durfee, Janardhan Kulkarni, Richard Peng, Saurabh Sawlani, and Xiaorui Sun
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2020.
Parallel Batch-Dynamic Trees via Change Propagation
[pdf] [arxiv]
Umut Acar, Daniel Anderson, Guy Blelloch, Laxman Dhulipala, and Sam Westrick
Proceedings of the European Symposium on Algorithms (ESA), 2020.
Near-Optimal Massively Parallel Graph Connectivity
[pdf] [arxiv]
Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Łącki, and Vahab Mirrokni
Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), 2019.
Low-Latency Graph Streaming Using Compressed Purely-Functional Trees
[pdf] [arxiv] [code]
Laxman Dhulipala, Guy Blelloch, and Julian Shun
Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2019.
Distinguished Paper Award
Massively Parallel Computation via Remote Memory Access
[pdf] [arxiv]
Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Łącki, Vahab Mirrokni, and Warren Schudy
Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2019.
Invited to Special Issue
Parallel Batch-Dynamic Graph Connectivity
[pdf] [arxiv]
Umut Acar, Daniel Anderson, Guy Blelloch, and Laxman Dhulipala
Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2019.
Batch Parallel Euler-Tour Trees
[pdf] [arxiv] [code]
Thomas Tseng, Laxman Dhulipala, and Guy Blelloch
Proceedings of the SIAM Meeting on Algorithm Engineering and Experiments (ALENEX), 2019.
Theoretically Efficient Parallel Algorithms Can Be Fast and Scalable
[pdf] [arxiv] [code]
Laxman Dhulipala, Guy Blelloch, and Julian Shun
Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2018.
Best Paper Award
Invited to Special Issue
Julienne: A Framework for Parallel Graph Algorithms using Work-efficient Bucketing
[pdf] [code]
Laxman Dhulipala, Guy Blelloch, and Julian Shun
Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2017.
Compressing Graphs and Indexes with Recursive Graph Bisection
[pdf] [arxiv]
Laxman Dhulipala, Igor Kabiljo, Brian Karrer, Giuseppe Ottaviano, Sergey Pupyrev, and Alon Shalita
Proceedings of the ACM Conference on Knowledge Discovery and Data Mining (KDD), 2016.
Smaller and Faster: Parallel Processing of Compressed Graphs with Ligra+
[pdf] [code]
Julian Shun, Laxman Dhulipala, and Guy Blelloch
Proceedings of the IEEE Data Compression Conference (DCC), 2015.
A simple and practical linear-work parallel algorithm for connectivity
[pdf] [code]
Julian Shun, Laxman Dhulipala, and Guy Blelloch
Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2014.

Ph.D. Thesis

Provably Efficient and Scalable Shared-Memory Graph Processing
[abstract] [pdf]
Laxman Dhulipala
Carnegie Mellon University, 2020
Received an Honorable Mention in CMU's SCS Dissertation Award.
Nominated for ACM Dissertation Award.

Notes

Introduction to Parallel Algorithms (draft)
[pdf]
Guy Blelloch and Laxman Dhulipala

Older Theses/Proposals

Thesis Proposal: Provably Efficient and Scalable Shared-Memory Graph Algorithms
[pdf]
Carnegie Mellon University, 2019

Undergraduate Thesis: Compressing Natural Graphs and a Practical Work-Efficient Parallel Connectivity Algorithm
[pdf]
Carnegie Mellon University, 2014