TeraHAC: Hierarchical Agglomerative Clustering of Trillion-Edge Graphs

Summary: TeraHAC achieves (1+ε)-approximate HAC for trillion-edge graphs by fusing nearest-neighbor chain with (1+ε)-HAC, enabling partitioned, communication-efficient clustering. Scales to 8T edges; >100x fewer rounds than prior HAC, up to 8.3x faster than SCC, and preserves HAC quality. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6786
Venue: SIGMOD
Year: 2023
Pagerank: 5.214913e-05
Overall Rank: 9,816 | 32.66%
DOI: 10.1145/3617341

Incoming Non-self Citations Over Time

Authors

1. Laxman Dhulipala (Google; University of Maryland)
2. Jakub Łącki (Google)
3. Jason Lee (Google)
4. Vahab Mirrokni (Google)

BibTeX Citation

@inproceedings{dhulipala_sigmod23,
        title = {{TeraHAC: Hierarchical Agglomerative Clustering of Trillion-Edge Graphs}},
        author = {Dhulipala, Laxman and Łącki, Jakub and Lee, Jason and Mirrokni, Vahab},
        series = {{SIGMOD} '23},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3617341},
        url = {https://dl.acm.org/doi/10.1145/3617341},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,102	The ParClusterers Benchmark Suite (PCBS): A Fine-Grained Analysis of Scalable Graph Clustering	2025	VLDB	5.093636e-05
11,236	Improving Graph Compression for Efficient Resource-Constrained Graph Analytics	2024	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
3	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0012250108
4,697	Multi-Dimensional Balanced Graph Partitioning via Projected Gradient Descent	2019	VLDB	6.5575113e-05
11,581	ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain	2022	VLDB	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,457	TrillionG: A Trillion-scale Synthetic Graph Generator using a Recursive Vector Model	2017	SIGMOD
2	8,623	A Near-Optimal Approach to Edge Connectivity-Based Hierarchical Graph Decomposition	2022	VLDB
3	11,675	Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering*	2021	SIGMOD
4	9,301	Accelerating Core Decomposition in Billion-Scale Hypergraphs	2025	SIGMOD
5	3,752	Distributed Edge Partitioning for Trillion-edge Graphs	2019	VLDB
6	3,511	Scalable Discovery of Best Clusters on Large Graphs	2010	VLDB
7	5,960	On Graph Representation for Attributed Hypergraph Clustering	2025	SIGMOD
8	11,566	PACk: An Efficient Partition-based Distributed Agglomerative Hierarchical Clustering Algorithm for Deduplication	2022	VLDB
9	8,188	Efficient and Effective Attributed Hypergraph Clustering via K-Nearest Neighbor Augmentation	2023	SIGMOD
10	11,581	ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain	2022	VLDB