Towards Effective and Efficient Distributed Clustering

Abstract

Clustering has become an increasingly important task in modern application domains such as marketing and purchasing assistance, multimedia, molecular biology as well as many others. In many of these areas, the data are originally collected at different sites. In order to extract information out of these data, they are brought together and then clustered. In this paper, we propose a different approach. We cluster the data locally and extract suitable representatives out of these clusters. These representatives are sent to a global server site where we restore the complete clustering based on the local representatives. This approach is very efficient, because the local clustering can be carried out quickly and independently from each other. Furthermore, we have low transmission cost, as the number of transmitted representatives is much smaller than the cardinality of the complete data set. Based on this small number of representatives, the global clustering can be done very efficiently. For both the local and the global clustering, we use a density based clustering algorithm. The combination of both the local and the global clustering forms our new DBDC (Density Based Distributed Clustering) algorithm. In our experimental evaluation, we will show that we do not have to sacrifice the clustering quality in order to gain an efficiency advantage if we use distributed clustering. 1.