Approximate Distributed K-Means Clustering over a Peer-to-Peer Network

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 d...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on knowledge and data engineering 2009-10, Vol.21 (10), p.1372-1388
Main Authors: Datta, S., Giannella, C.R., Kargupta, H.
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Algorithms
Applied sciences
Approximation
Approximation algorithms
Cluster analysis
Clustering
Clustering algorithms
Computer networks
Computer science
control theory
systems
Computer systems and distributed systems. User interface
Costs
Data mining
Data processing. List processing. Character string processing
Distributed computing
distributed K-means clustering
Exact sciences and technology
History
Large-scale systems
Mathematical analysis
Memory organisation. Data processing
Networks
Peer to peer computing
Peer-to-peer data mining
Software
Studies
Synchronism
Synchronization
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 clusterings by ldquolocalrdquo 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 the modest communication cost.
ISSN:1041-4347
1558-2191
DOI:10.1109/TKDE.2008.222