Jakub Łącki
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Jakub Łącki has a total of 47 co-authors. Here are the top co-authors by number of shared publications:
- Laxman Dhulipala
University of Maryland, College Park, College PARK, USA
4 shared publications - Lars Gottesbüren
Karlsruhe Institute of Technology
2 shared publications - Vahab Mirrokni
Google research
2 shared publications - Adam Karczmarz
University of Warsaw Poland
1 shared publication - Albert-Jan N. Yzelman
Computing Systems Lab, Huawei Zurich Research Center, Zurich, Switzerland
1 shared publication - Blair D. Sullivan
University of Utah, Salt Lake City, Utah, USA
1 shared publication
Latest Publications
- Top Cited PapersOpen Access
- 8 August 2026
- Published by Association for Computing Machinery (ACM)
- p. 4092-4102
PiPNN: Ultra-Scalable Graph-Based Nearest Neighbor Indexing
- 8 August 2026
- Published by Association for Computing Machinery (ACM)
- p. 4092-4102
Top Cited PapersOpen AccessPiPNN: Ultra-Scalable Graph-Based Nearest Neighbor Indexing
- Open Access
- 28 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 16-18
Towards Scalable and Practical Batch-Dynamic Connectivity (Abstract)
- 28 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 16-18
Open AccessTowards Scalable and Practical Batch-Dynamic Connectivity (Abstract)
- Open Access
- 16 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 339-349
Faster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs
- 16 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 339-349
Open AccessFaster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs
- Open Access
- 13 November 2023
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 1 (3) , 1-27
TeraHAC: Hierarchical Agglomerative Clustering of Trillion-Edge Graphs
We introduce TeraHAC, a (1+ε)-approximate hierarchical agglomerative clustering (HAC) algorithm which scales to trillion-edge graphs. Our algorithm is based on a new approach to computing (1+ε)-approximate HAC, which is a novel combination of the nearest-neighbor chain algorithm and the notion of (1+ε)-approximate HAC. Our approach allows us to partition the graph among multiple machines and make significant progress in computing the clustering within each partition before any communication with other partitions is needed. We evaluate TeraHAC on a number of real-world and synthetic graphs of up to 8 trillion edges. We show that TeraHAC requires over 100x fewer rounds compared to previously known approaches for computing HAC. It is up to 8.3x faster than SCC, the state-of-the-art distributed algorithm for hierarchical clustering, while achieving 1.16x higher quality. In fact, TeraHAC essentially retains the quality of the celebrated HAC algorithm while significantly improving the running time.
- 13 November 2023
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 1 (3) , 1-27
Open AccessTeraHAC: Hierarchical Agglomerative Clustering of Trillion-Edge Graphs
We introduce TeraHAC, a (1+ε)-approximate hierarchical agglomerative clustering (HAC) algorithm which scales to trillion-edge graphs. Our algorithm is based on a new approach to computing (1+ε)-approximate HAC, which is a novel combination of the nearest-neighbor chain algorithm and the notion of (1+ε)-approximate HAC. Our approach allows us to partition the graph among multiple machines and make significant progress in computing the clustering within each partition before any communication with other partitions is needed. We evaluate TeraHAC on a number of real-world and synthetic graphs of up to 8 trillion edges. We show that TeraHAC requires over 100x fewer rounds compared to previously known approaches for computing HAC. It is up to 8.3x faster than SCC, the state-of-the-art distributed algorithm for hierarchical clustering, while achieving 1.16x higher quality. In fact, TeraHAC essentially retains the quality of the celebrated HAC algorithm while significantly improving the running time.
- Open Access
Open Problems in (Hyper)Graph Decomposition
Large networks are useful in a wide range of applications. Sometimes problem instances are composed of billions of entities. Decomposing and analyzing these structures helps us gain new insights about our surroundings. Even if the final application concerns a different problem (such as traversal, finding paths, trees, and flows), decomposing large graphs is often an important subproblem for complexity reduction or parallelization. This report is a summary of discussions that happened at Dagstuhl seminar 23331 on "Recent Trends in Graph Decomposition" and presents currently open problems and future directions in the area of (hyper)graph decomposition.
Open AccessOpen Problems in (Hyper)Graph Decomposition
Large networks are useful in a wide range of applications. Sometimes problem instances are composed of billions of entities. Decomposing and analyzing these structures helps us gain new insights about our surroundings. Even if the final application concerns a different problem (such as traversal, finding paths, trees, and flows), decomposing large graphs is often an important subproblem for complexity reduction or parallelization. This report is a summary of discussions that happened at Dagstuhl seminar 23331 on "Recent Trends in Graph Decomposition" and presents currently open problems and future directions in the area of (hyper)graph decomposition.
- Open Access
- 17 June 2023
- Published by Association for Computing Machinery (ACM)
- p. 431-441
Adaptive Massively Parallel Connectivity in Optimal Space
- 17 June 2023
- Published by Association for Computing Machinery (ACM)
- p. 431-441
Open AccessAdaptive Massively Parallel Connectivity in Optimal Space
- Open Access
- 1 September 2020
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 13 (13) , 3588-3602
Parallel graph algorithms in constant adaptive rounds
We study fundamental graph problems such as graph connectivity, minimum spanning forest (MSF), and approximate maximum (weight) matching in a distributed setting. In particular, we focus on the Adaptive Massively Parallel Computation (AMPC) model, which is a theoretical model that captures MapReduce-like computation augmented with a distributed hash table. We show the first AMPC algorithms for all of the studied problems that run in a constant number of rounds and use only O(nϵ) space per machine, where 0 < ϵ < 1. Our results improve both upon the previous results in the AMPC model, as well as the best-known results in the MPC model, which is the theoretical model underpinning many popular distributed computation frameworks, such as MapReduce, Hadoop, Beam, Pregel and Giraph. Finally, we provide an empirical comparison of the algorithms in the MPC and AMPC models in a fault-tolerant distributed computation environment. We empirically evaluate our algorithms on a set of large real-world graphs and show that our AMPC algorithms can achieve improvements in both running time and round-complexity over optimized MPC baselines.
- 1 September 2020
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 13 (13) , 3588-3602
Open AccessParallel graph algorithms in constant adaptive rounds
We study fundamental graph problems such as graph connectivity, minimum spanning forest (MSF), and approximate maximum (weight) matching in a distributed setting. In particular, we focus on the Adaptive Massively Parallel Computation (AMPC) model, which is a theoretical model that captures MapReduce-like computation augmented with a distributed hash table. We show the first AMPC algorithms for all of the studied problems that run in a constant number of rounds and use only O(nϵ) space per machine, where 0 < ϵ < 1. Our results improve both upon the previous results in the AMPC model, as well as the best-known results in the MPC model, which is the theoretical model underpinning many popular distributed computation frameworks, such as MapReduce, Hadoop, Beam, Pregel and Giraph. Finally, we provide an empirical comparison of the algorithms in the MPC and AMPC models in a fault-tolerant distributed computation environment. We empirically evaluate our algorithms on a set of large real-world graphs and show that our AMPC algorithms can achieve improvements in both running time and round-complexity over optimized MPC baselines.