Parallelization of a graph-cut based algorithm for hierarchical clustering of web documents

摘要

We propose a parallelization scheme for an existing algorithm for constructing a web-directory, that containsrncategories of web documents organized hierarchically. The clustering algorithm automatically infers thernnumber of clusters using a quality function based on graph cuts. A parallel implementation of the algorithmrnhas been developed to run on a cluster of multi-core processors interconnected by an intranet. The effect ofrnthe well-known Latent Semantic Indexing on the performance of the clustering algorithm is also considered.rnThe parallelized graph-cut based clustering algorithm achieves an F-measure in the range OE0:69; 0:91u0002rnfor the generated leaf-level clusters while yielding a precision-recall performance in the range OE0:66; 0:84u0002rnfor the entire hierarchy of the generated clusters. As measured via empirical observations, the parallelrnalgorithm achieves an average speedup of 7.38 over its sequential variant, at the same time yielding a betterrnclustering performance than the sequential algorithm in terms of F-measure.