ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain

Summary: ParChain parallelizes HAC via NN-chain, enabling linear-memory complete/average/Ward linkages. Two optimizations: range-pruning and distance caching cut computations and memory, yielding speedups on hardware scalable to tens of millions of points. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12769
Venue: VLDB
Year: 2022
Pagerank: 4.1945683e-05
Overall Rank: 11,383 | 20.82%
DOI: 10.14778/3489496.3489509

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,681	TeraHAC: Hierarchical Agglomerative Clustering of Trillion-Edge Graphs	2023	SIGMOD	4.3047774e-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
4,296	Twister Tries: Approximate Hierarchical Agglomerative Clustering for Average Distance in Linear Time	2015	SIGMOD	6.2885419e-05
7,871	ConnectIt: A Framework for Static and Incremental Parallel Graph Connectivity Algorithms	2021	VLDB	4.6308128e-05
11,477	Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering*	2021	SIGMOD	4.1945683e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,947	Parallel Algorithms for Hierarchical Nucleus Decomposition	2024	SIGMOD	4.1945683e-05
7,850	Efficient and Effective Attributed Hypergraph Clustering via K-Nearest Neighbor Augmentation	2023	SIGMOD	4.6362484e-05
10,387	Parallel kd-tree with Batch Updates	2025	SIGMOD	4.1945683e-05
5,417	Theoretically-Efficient and Practical Parallel DBSCAN	2020	SIGMOD	5.5194222e-05
3,597	Parallel Local Graph Clustering	2016	VLDB	6.9345175e-05
4,021	Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures	2016	PODS	6.5225987e-05
11,466	Fast Density-Peaks Clustering: Multicore-based Parallelization Approach	2021	SIGMOD	4.1945683e-05
11,368	PACk: An Efficient Partition-based Distributed Agglomerative Hierarchical Clustering Algorithm for Deduplication	2022	VLDB	4.1945683e-05
11,477	Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering*	2021	SIGMOD	4.1945683e-05
9,681	TeraHAC: Hierarchical Agglomerative Clustering of Trillion-Edge Graphs	2023	SIGMOD	4.3047774e-05