poster

TeraHAC: Hierarchical Agglomerative Clustering of Trillion-Edge Graphs (Abstract)

Authors:

Laxman Dhulipala,

Jakub Lacki,

Jason Lee,

Vahab MirrokniAuthors Info & Claims

HOPC'24: Proceedings of the 2024 ACM Workshop on Highlights of Parallel Computing

Pages 15 - 16

https://doi.org/10.1145/3670684.3673421

Published: 26 July 2024 Publication History

Get Access

Abstract

This paper presents a new distributed algorithm for hierarchical agglomerative clustering (HAC), a widely-used clustering algorithm known for its high quality in a variety of applications.

References

[1]

Mohammadhossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, Mohammad- Taghi Hajiaghayi, Raimondas Kiveris, Silvio Lattanzi, and Vahab Mirrokni. Affinity clustering: Hierarchical clustering at scale. In NeurIPS, 2017.

Google Scholar

[2]

MohammadHossein Bateni, Laxman Dhulipala, Willem Fletcher, Kishen N Gowda, D Ellis Hershkowitz, Rajesh Jayaram, and Jakub Lacki. Efficient centroid-linkage clustering. arXiv preprint arXiv:2406.05066, 2024.

Google Scholar

[3]

MohammadHossein Bateni, Laxman Dhulipala, Kishen N Gowda, D Ellis Hershkowitz, Rajesh Jayaram, and Jakub Lacki. It's hard to HAC with average linkage! arXiv preprint arXiv:2404.14730, 2024.

Google Scholar

[4]

J-P Benzécri. Construction d'une classification ascendante hiérarchique par la recherche en chaîne des voisins réciproques. L'analyse des données, 1982.

Google Scholar

[5]

Laxman Dhulipala, David Eisenstat, Jakub Lacki, Vahab Mirrokni, and Jessica Shi. Hierarchical agglomerative graph clustering in nearly-linear time. In ICML, 2021.

Google Scholar

[6]

Laxman Dhulipala, David Eisenstat, Jakub Lacki, Vahab Mirrokni, and Jessica Shi. Hierarchical agglomerative graph clustering in poly-logarithmic depth. In NeurIPS, 2022.

Google Scholar

[7]

Laxman Dhulipala, Jakub Lacki, Jason Lee, and Vahab Mirrokni. TeraHAC: Hierarchical agglomerative clustering of trillion-edge graphs. SIGMOD, 2023.

Digital Library

Google Scholar

[8]

Nicholas Monath, Kumar Avinava Dubey, Guru Guruganesh, Manzil Zaheer, et al. Scalable hierarchical agglomerative clustering. In KDD, 2021.

Digital Library

Google Scholar

[9]

Baris Sumengen, Anand Rajagopalan, Gui Citovsky, David Simcha, et al. Scaling hierarchical agglomerative clustering to billion-sized datasets. arXiv preprint arXiv:2105.11653, 2021.

Google Scholar

Index Terms

TeraHAC: Hierarchical Agglomerative Clustering of Trillion-Edge Graphs (Abstract)
1. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
    2. Parallel algorithms

Recommendations

TeraHAC: Hierarchical Agglomerative Clustering of Trillion-Edge Graphs
PACMMOD

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-...
Particle Swarm Optimization Based Hierarchical Agglomerative Clustering
WI-IAT '10: Proceedings of the 2010 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology - Volume 02

Clustering- an important data mining task, which groups the data on the basis of similarities among the data, can be divided into two broad categories, partitional clustering and hierarchal. We combine these two methods and propose a novel clustering ...
Clustering Large Attributed Graphs: A Balance between Structural and Attribute Similarities

Social networks, sensor networks, biological networks, and many other information networks can be modeled as a large graph. Graph vertices represent entities, and graph edges represent their relationships or interactions. In many large graphs, there is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

HOPC'24: Proceedings of the 2024 ACM Workshop on Highlights of Parallel Computing

June 2024

47 pages

ISBN:9798400707001

DOI:10.1145/3670684

Program Chairs:
Laxman Dhulipala
University of Maryland, USA
,
Yihan Sun
University of California, Riverside, USA

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 July 2024

Check for updates

Author Tags

Qualifiers

Poster

Conference

SPAA '24

Sponsor:

SPAA '24: 36th ACM Symposium on Parallelism in Algorithms and Architectures

June 17, 2024

Nantes, France

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
19
Total Downloads

Downloads (Last 12 months)19
Downloads (Last 6 weeks)1

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Index Terms

Recommendations

TeraHAC: Hierarchical Agglomerative Clustering of Trillion-Edge Graphs

Particle Swarm Optimization Based Hierarchical Agglomerative Clustering

Clustering Large Attributed Graphs: A Balance between Structural and Attribute Similarities