in software implementationsthe ward linkage function is often rescaled by multiplying it by factor of in this waythe distance between one-point clusters {xi and { is the squared euclidean distance kxi having chosen distance on and linkage criteriona general agglomerative clustering algorithm proceeds in the following "greedymanner algorithm greedy agglomerative clustering inputdistance function distlinkage function dnumber of clusters outputthe label sets for the tree initialize the set of cluster identifiersi { initialize the corresponding label setsli { } initialize distance matrix [di with di ({ } } for to do find and in such that di is minimal create new label set lk :li add the new identifier to and remove the old identifiers and from update the distance matrix with respect to the identifiers ijand return li initiallythe distance matrix contains the (linkagedistances between the one-point clusters containing one of the data points xn and hence with identifiers finding the shortest distance amounts to table lookup in when the closest clusters are foundthey are merged into new clusterand new identifier (the smallest positive integer that has not yet been used as an identifieris assigned to this cluster the old identifiers and are removed from the cluster identifier set the matrix is then updated by adding -th column and row that contain the distances between and any this updating step could be computationally quite costly if the cluster sizes are large and the linkage distance between the clusters depends on all points within the clusters fortunatelyfor many linkage functionsthe matrix can be updated in an efficient manner suppose that at some stage in the algorithmclusters and jwith identifiers and jrespectivelyare merged into cluster with identifier let mwith identifier mbe previously assigned cluster an update rule of the linkage distance dkm between and is called lance-williams update if it can be written in the form dkm dim jm di |dim jm |where ad depend only on simple characteristics of the clusters involvedsuch as the number of elements within the clusters table shows the update constants for number of common linkage functions for examplefor single linkagedim is the minimal distance between and mand jm is the minimal distance between and the smallest of these is the minimal distance between and that isdkm min{dim jm dim / jm / |dim jm |/ lancewilliams