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

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

January 1972 | R. Sibson
Sibson's SLINK algorithm is an efficient method for performing single-link cluster analysis on arbitrary dissimilarity coefficients. It provides a representation of the resulting dendrogram that can be converted into a tree-diagram. The algorithm achieves theoretical bounds for storage and speed, making it feasible for large datasets with up to 10^4 OTUs. It is easily programmable in various languages, including FORTRAN. The single-link method is a hierarchical clustering technique that defines clusters based on the nearest neighbor. It is defined by a dissimilarity coefficient and produces a dendrogram, which is a nested sequence of partitions. The algorithm efficiently computes the dendrogram by updating a pointer representation, which allows for efficient storage and computation. The SLINK algorithm uses a pointer representation to store the dendrogram, which is more efficient than traditional methods. This representation allows for recursive updates when adding new OTUs. The algorithm processes the dissimilarity values in a specific order, minimizing the need for sorting or rearrangement. The algorithm is implemented with three arrays to store the pointer and lambda values, and it efficiently computes the dendrogram in O(N^2) time. The SLINK algorithm is optimal in terms of order-of-magnitude efficiency and is suitable for large datasets. It is also capable of converting the pointer representation into a packed representation for output, which can be used to generate a tree-diagram. The algorithm is described in detail, including its recursive updating process and the use of pointer and lambda functions. The algorithm is also accompanied by a FORTRAN program that implements the SLINK algorithm, which reads the dissimilarity coefficients from an input stream and produces the dendrogram. The program is efficient and suitable for large datasets.Sibson's SLINK algorithm is an efficient method for performing single-link cluster analysis on arbitrary dissimilarity coefficients. It provides a representation of the resulting dendrogram that can be converted into a tree-diagram. The algorithm achieves theoretical bounds for storage and speed, making it feasible for large datasets with up to 10^4 OTUs. It is easily programmable in various languages, including FORTRAN. The single-link method is a hierarchical clustering technique that defines clusters based on the nearest neighbor. It is defined by a dissimilarity coefficient and produces a dendrogram, which is a nested sequence of partitions. The algorithm efficiently computes the dendrogram by updating a pointer representation, which allows for efficient storage and computation. The SLINK algorithm uses a pointer representation to store the dendrogram, which is more efficient than traditional methods. This representation allows for recursive updates when adding new OTUs. The algorithm processes the dissimilarity values in a specific order, minimizing the need for sorting or rearrangement. The algorithm is implemented with three arrays to store the pointer and lambda values, and it efficiently computes the dendrogram in O(N^2) time. The SLINK algorithm is optimal in terms of order-of-magnitude efficiency and is suitable for large datasets. It is also capable of converting the pointer representation into a packed representation for output, which can be used to generate a tree-diagram. The algorithm is described in detail, including its recursive updating process and the use of pointer and lambda functions. The algorithm is also accompanied by a FORTRAN program that implements the SLINK algorithm, which reads the dissimilarity coefficients from an input stream and produces the dendrogram. The program is efficient and suitable for large datasets.
Reach us at info@study.space
[slides] SLINK%3A An Optimally Efficient Algorithm for the Single-Link Cluster Method | StudySpace