SLINK: An optimally efficient algorithm for the single-link cluster method

1973/01/01 by R. Sibson, Robin Sibson · 1,200 citations
Computer Science · Mathematics · Physics and Astronomy · #Advanced Clustering Algorithms Research #Algorithm #Cluster (spacecraft) #Combinatorics #Compact space #Complex Network Analysis Techniques #Computer science #Dendrogram #Diagram #Fortran #Link (geometry) #Mathematics #Programming language #Range (aeronautics) #Representation (politics) #Theoretical and Computational Physics #Theoretical computer science #Tree (set theory)

paper · pdf · doi:10.1093/comjnl/16.1.30

published in The Computer Journal 16(1), 30-34 (Oxford University Press)

openalex publication_date 1973/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30

Abstract

The SLINK algorithm carries out single-link (nearest-neighbour) cluster analysis on an arbitrary dissimilarity coefficient and provides a representation of the resultant dendrogram which can readily be converted into the usual tree-diagram. The algorithm achieves the theoretical order-of-magnitude bounds for both compactness of storage and speed of operation, and makes the application of the single-link method feasible for a number of OTU's well into the range 103 to 104. The algorithm is easily programmable in a variety of languages including FORTRAN.

Cited by

• Enhancing Noise Resilience in Face Clustering via Sparse Differential Transformer
• Methods of Hierarchical Clustering
• Big-Data Clustering: K-Means or K-Indicators?
• Hyperbolic Continuous Structural Entropy for Hierarchical Clustering
• Learning to Cluster Faces on an Affinity Graph
• Adaptive Correlated Monte Carlo for Contextual Categorical Sequence Generation
• A Groupwise Approach for Inferring Heterogeneous Treatment Effects in Causal Inference
• A Parameter-free Affinity Based Clustering
• WebFace260M: A Benchmark Unveiling the Power of Million-Scale Deep Face Recognition
• ELKI: A large open-source library for data analysis - ELKI Release 0.7.5 "Heidelberg"
• Rediscovering Recurring Routing Results
• A Linkage-based Doubly Imbalanced Graph Learning Framework for Face Clustering
• Distributed clustering in partially overlapping feature spaces
• Hybrid Graph Embeddings and Louvain Algorithm for Unsupervised Community Detection
• Structure-Aware Face Clustering on a Large-Scale Graph with \bf10⁷ Nodes
• Topological graph clustering with thin position
• Ultrametric Component Analysis with Application to Analysis of Text and of Emotion
• Ontology from Local Hierarchical Structure in Text
• Clustering with Temporal Constraints on Spatio-Temporal Data of Human Mobility
• Learning to Cluster Faces via Transformer
• Scene Text Detection and Recognition: The Deep Learning Era
• FaceGCD: Generalized Face Discovery via Dynamic Prefix Generation
• The NOESIS Network-Oriented Exploration, Simulation, and Induction System
• Multi-Community Spectral Clustering for Geometric Graphs
• Learned Sectors: A fundamentals-driven sector reclassification project
• Coarse-to-Fine Curriculum Learning
• OPTICS
• Comparison three methods of clustering: k-means, spectral clustering and hierarchical clustering
• Unsupervised Action Proposal Ranking through Proposal Recombination
• Density-Based Clustering with Kernel Diffusion
• A Tutorial on Discriminative Clustering and Mutual Information
• Meta-learning for mixed linear regression
• Navigating the Accuracy-Size Trade-Off with Flexible Model Merging
• Information Content of a Phylogenetic Tree in a Data Matrix
• 4TaStiC: Time and trend traveling time series clustering for classifying long-term type 2 diabetes patients
• Learning Hierarchical Graph Neural Networks for Image Clustering
• kFuse: A novel density based agglomerative clustering
• Selective Clustering Annotated using Modes of Projections
• Learning to Cluster Faces via Confidence and Connectivity Estimation
• Convergence of Hierarchical Clustering and Persistent Homology Methods on Directed Networks
• The (black) art of runtime evaluation: Are we comparing algorithms or implementations?
• Counting dendrograms: A survey
• From clustering to clustering ensemble selection: A review
• Mining and modeling complex leadership–followership dynamics of movement data
• Occam’s Razor for Big Data? On Detecting Quality in Large Unstructured Datasets
• Functorial hierarchical clustering with overlaps
• An evidential classifier based on Dempster-Shafer theory and deep learning
• Approximate hierarchical density-based clustering using graph-based search indexes
• Extrapolation method to optimize linear-ramp QAOA parameters: Evaluation of QAOA runtime scaling
• Topological data analysis: A promising big data exploration tool in biology, analytical chemistry and physical chemistry
• Exploring hyperspectral imaging data sets with topological data analysis
• When remote sensing meets topological data analysis
• SEQOPTICS: a protein sequence clustering system. [europepmc]
• Efficient algorithms for fast integration on large data sets from multiple sources. [europepmc]
• Clustering rfam 10.1: clans, families, and classes. [europepmc]
• Integral-geometry characterization of photobiomodulation effects on retinal vessel morphology. [europepmc]
• TE-Tracker: systematic identification of transposition events through whole-genome resequencing. [europepmc]
• A density-based clustering approach for identifying overlapping protein complexes with functional preferences. [europepmc]
• Inhibitory and excitatory axon terminals share a common nano-architecture of their Cav2.1 (P/Q-type) Ca(2+) channels. [europepmc]
• Robust tracking and quantification of C. elegans body shape and locomotion through coiling, entanglement, and omega bends. [europepmc]
• Structural Study of Heterogeneous Biological Samples by Cryoelectron Microscopy and Image Processing. [europepmc]
• Automatic detection and decoding of honey bee waggle dances. [europepmc]
• Divisive hierarchical maximum likelihood clustering. [europepmc]
• A Literature Review: Geometric Methods and Their Applications in Human-Related Analysis. [europepmc]
• The Application of Deep Learning in Cancer Prognosis Prediction. [europepmc]
• Data mining application to healthcare fraud detection: a two-step unsupervised clustering method for outlier detection with administrative databases. [europepmc]
• A community-driven resource for genomic epidemiology and antimicrobial resistance prediction of Neisseria gonorrhoeae at Pathogenwatch. [europepmc]
• A global resource for genomic predictions of antimicrobial resistance and surveillance of Salmonella Typhi at pathogenwatch. [europepmc]
• CATBOSS: Cluster Analysis of Trajectories Based on Segment Splitting. [europepmc]
• MulticlusterKDE: a new algorithm for clustering based on multivariate kernel density estimation. [europepmc]
• Machine Learning Advances in Microbiology: A Review of Methods and Applications. [europepmc]
• 3-D breast nodule detection on automated breast ultrasound using faster region-based convolutional neural networks and U-Net. [europepmc]
• Antimicrobial Susceptibility Profiles of Commensal Escherichia coli Isolates from Chickens in Hungarian Poultry Farms Between 2022 and 2023. [europepmc]
• Antimicrobial Susceptibility Profiles of Commensal Enterococcus spp. Isolates from Chickens in Hungarian Poultry Farms Between 2022 and 2023. [europepmc]
• Antimicrobial Susceptibility Profiles of Commensal Staphylococcus spp. Isolates from Chickens in Hungarian Poultry Farms Between 2022 and 2023. [europepmc]
• Antimicrobial Susceptibility Profiles of Commensal Staphylococcus spp. Isolates from Turkeys in Hungarian Poultry Farms Between 2022 and 2023. [europepmc]
• Ultra-high-scale cytometry-based cellular interaction mapping. [europepmc]

Related

• cuSLINK: Single-linkage Agglomerative Clustering on the GPU
• Optimal Parallel Algorithms for Dendrogram Computation and Single-Linkage Clustering
• Fully-Dynamic Parallel Algorithms for Single-Linkage Clustering
• Weakest link pruning of a dendrogram
• A density-sensitive hierarchical clustering method