Approximate K-means Clustering in Peer-to-Peer Networks

Data intensive peer-to-peer (P2P) networks are finding increasing number of applications. Data mining in such P2P environments is a natural extension. However, common monolithic data mining architectures do not fit well in such environments since they typically require centralizing the distributed data which is usually not practical in a large P2P network. Distributed data mining algorithms that avoid large-scale synchronization or data centralization offer an alternate choice. This paper considers the distributed K-means clustering problem where the data and computing resources are distributed over a large P2P network. It offers two algorithms which produce an approximation of the result produced by the standard centralized K-means clustering algorithm. The first is designed to operate in a dynamic P2P network that can produce clustering by "local" synchronization only. The second algorithm uses uniformly sampled peers and provides analytical guarantees regarding the accuracy of clustering on a P2P network. Empirical results show that both the algorithms demonstrate good performance compared to their centralized counterparts at little communication cost.
Date: October 18, 2008
Book Title: IEEE Transactions on Knowledge and Data Engineering.
Type: InProceedings


  author = "Souptik Datta and Chris Giannella and Hillol Kargupta",
  title = "{Approximate K-means Clustering in Peer-to-Peer Networks}",
  month = "October",
  year = "2008",
  booktitle = "IEEE Transactions on Knowledge and Data Engineering.",