A previous paper by the authors introduced the basics of fast evolutionary algorithms for relational data and proposed a new asymptotic complexity analysis of the algorithms in terms of running time. This paper is an extension of that work.

The basic k-medoids (BKM) class of clustering algorithms and the relational hard c-means (RHCM) algorithms are briefly described in the second section of the paper.

In the third section, the authors introduce the fast evolutionary algorithm for relational clustering (F-EARC) and two of its variants--F-EARC-BKM and F-EARC-RHCM, which differ in the way the prototypes are considered. A series of comments follows, concerning different strategies for defining the setting of the initial population and the recombination operators.

Conclusions concerning the computational efficiency of F-EARC, when tested against pseudo-exhaustive clustering methods, are presented in the fourth section of the paper; several comments and suggestions for future extensions are provided. The Silhouette index, extensively used in the performed tests, and the computational complexity analysis of the proposed algorithms are presented in the appendices.

The reported research brings together a series of interesting, new theoretical developments, and provides faster versions of the evolutionary approaches in relational clustering. The proposed algorithms’ performance was evaluated by the authors through a long series of tests that pointed out the real potential in developing faster clustering schemes for relational data.