Approximate Single-Linkage Clustering Using Graph-Based Indexes: MST-Based Approaches and Incremental Searchers.

Camilla Birch Okkels; Erik Thordsen; Martin Aumüller; Arthur Zimek; Erich Schubert

Approximate Single-Linkage Clustering Using Graph-Based Indexes: MST-Based Approaches and Incremental Searchers.

Camilla Birch Okkels
, Erik Thordsen
, Martin Aumüller
, Arthur Zimek
, Erich Schubert

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Abstract

Current exact single-linkage clustering algorithms have asymptotically quadratic complexity. We present algorithms for approximate single-linkage clustering with empirically near-linear scalability. We explore both graph index-based incremental nearest neighbor search and an iterative exploration scheme on the graph index approximating the MST of the reachability graph similar to Kruskal. As graph index, we use both the bottom layer and a combination of all layers of an HNSW as a stand-in for connected search graphs. We provide experiments comparing the clusterings to baselines such as exact single linkage implementation and an algorithm using metric tree-based searchers. We explore the impact of the HNSW hyperparameters on the performance in terms of running time and clustering quality and evaluate the empirical asymptotic complexity.

Original language	English
Title of host publication	SISAP
Number of pages	15
Publication date	7 Oct 2025
Pages	233-247
ISBN (Print)	978-3-032-06068-6
ISBN (Electronic)	978-3-032-06069-3
Publication status	Published - 7 Oct 2025
Event	International Conference on Similarity Search and Applications - Reykjavik, Iceland Duration: 1 Oct 2025 → 3 Oct 2025 Conference number: 18 https://www.sisap.org/2025

Conference

Conference	International Conference on Similarity Search and Applications
Number	18
Country/Territory	Iceland
City	Reykjavik
Period	01/10/2025 → 03/10/2025
Internet address	https://www.sisap.org/2025

Keywords

Clustering
Hierarchical Clustering
Approximate Clustering

Access to Document

2025-sisap-hsslAccepted author manuscript, 665 KB

Cite this

@inproceedings{57172784345f4458bccdc403bac2f3e9,

title = "Approximate Single-Linkage Clustering Using Graph-Based Indexes: MST-Based Approaches and Incremental Searchers.",

abstract = "Current exact single-linkage clustering algorithms have asymptotically quadratic complexity. We present algorithms for approximate single-linkage clustering with empirically near-linear scalability. We explore both graph index-based incremental nearest neighbor search and an iterative exploration scheme on the graph index approximating the MST of the reachability graph similar to Kruskal. As graph index, we use both the bottom layer and a combination of all layers of an HNSW as a stand-in for connected search graphs. We provide experiments comparing the clusterings to baselines such as exact single linkage implementation and an algorithm using metric tree-based searchers. We explore the impact of the HNSW hyperparameters on the performance in terms of running time and clustering quality and evaluate the empirical asymptotic complexity.",

keywords = "Clustering, Hierarchical Clustering, Approximate Clustering",

author = "Okkels, \{Camilla Birch\} and Erik Thordsen and Martin Aum{\"u}ller and Arthur Zimek and Erich Schubert",

note = "DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.; International Conference on Similarity Search and Applications, SISAP ; Conference date: 01-10-2025 Through 03-10-2025",

year = "2025",

month = oct,

day = "7",

language = "English",

isbn = "978-3-032-06068-6",

pages = "233--247",

booktitle = "SISAP",

url = "https://www.sisap.org/2025",

}

TY - GEN

T1 - Approximate Single-Linkage Clustering Using Graph-Based Indexes: MST-Based Approaches and Incremental Searchers.

AU - Okkels, Camilla Birch

AU - Thordsen, Erik

AU - Aumüller, Martin

AU - Zimek, Arthur

AU - Schubert, Erich

N1 - Conference code: 18

PY - 2025/10/7

Y1 - 2025/10/7

N2 - Current exact single-linkage clustering algorithms have asymptotically quadratic complexity. We present algorithms for approximate single-linkage clustering with empirically near-linear scalability. We explore both graph index-based incremental nearest neighbor search and an iterative exploration scheme on the graph index approximating the MST of the reachability graph similar to Kruskal. As graph index, we use both the bottom layer and a combination of all layers of an HNSW as a stand-in for connected search graphs. We provide experiments comparing the clusterings to baselines such as exact single linkage implementation and an algorithm using metric tree-based searchers. We explore the impact of the HNSW hyperparameters on the performance in terms of running time and clustering quality and evaluate the empirical asymptotic complexity.

AB - Current exact single-linkage clustering algorithms have asymptotically quadratic complexity. We present algorithms for approximate single-linkage clustering with empirically near-linear scalability. We explore both graph index-based incremental nearest neighbor search and an iterative exploration scheme on the graph index approximating the MST of the reachability graph similar to Kruskal. As graph index, we use both the bottom layer and a combination of all layers of an HNSW as a stand-in for connected search graphs. We provide experiments comparing the clusterings to baselines such as exact single linkage implementation and an algorithm using metric tree-based searchers. We explore the impact of the HNSW hyperparameters on the performance in terms of running time and clustering quality and evaluate the empirical asymptotic complexity.

KW - Clustering

KW - Hierarchical Clustering

KW - Approximate Clustering

M3 - Article in proceedings

SN - 978-3-032-06068-6

SP - 233

EP - 247

BT - SISAP

T2 - International Conference on Similarity Search and Applications

Y2 - 1 October 2025 through 3 October 2025

ER -

Approximate Single-Linkage Clustering Using Graph-Based Indexes: MST-Based Approaches and Incremental Searchers.

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this