Laxman Dhulipala
research interests
scalable parallel algorithms, parallel graph processing for static, dynamic, and streaming graphs.
contactemail: laxman [at] umd.edu CV -- GitHub -- Hobbies
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 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
- 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
TeraHAC: Hierarchical Agglomerative Clustering of Trillion-Edge Graphs
[arxiv]
Laxman Dhulipala, Jason Lee, Jakub Łącki, and Vahab Mirrokni
To appear in SIGMOD 2024.
[arxiv]
Laxman Dhulipala, Jason Lee, Jakub Łącki, and Vahab Mirrokni
To appear in SIGMOD 2024.
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.
[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.
[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.
[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.
[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
[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.
[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.
[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
[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.
[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.
[pdf] [code]
Laxman Dhulipala, Guy E. Blelloch, Yan Gu, and Yihan Sun
ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2022.
Theoretically and Practically Efficient Parallel Nucleus Decomposition
[pdf] [arxiv]
Jessica Shi, Laxman Dhulipala, and Julian Shun
Proceedings of the VLDB Endowment, 2022.
[pdf] [arxiv]
Jessica Shi, Laxman Dhulipala, and Julian Shun
Proceedings of the VLDB Endowment, 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.
[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.
[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.
[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.
[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.
[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.
[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.
[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
[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.
[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.
[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.
[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.
[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.
[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)
[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.
[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)
[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
[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.
[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.
[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.
[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.
[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.
[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
[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
[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.
[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.
[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
[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.
[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.
[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.