Abstract
This paper presents a hierarchical clustering method named RACHET (Recursive Agglomeration of Clustering Hierarchies by Encircling Tactic) for analyzing multi-dimensional distributed data. A typical clustering algorithm requires bringing all the data in a centralized warehouse. This results in O(nd) transmission cost, where n is the number of data points and d is the number of dimensions. For large datasets, this is prohibitively expensive. In contrast, RACHET runs with at most O(n) time, space, and communication costs to build a global hierarchy of comparable clustering quality by merging locally generated clustering hierarchies. RACHET employs the encircling tactic in which the merges at each stage are chosen so as to minimize the volume of a covering hypersphere. For each cluster centroid, RACHET maintains descriptive statistics of constant complexity to enable these choices. RACHET's framework is applicable to a wide class of centroid-based hierarchical clustering algorithms, such as centroid, medoid, and Ward.
Original language | English |
---|---|
Pages (from-to) | 157-180 |
Number of pages | 24 |
Journal | Distributed and Parallel Databases |
Volume | 11 |
Issue number | 2 |
State | Published - Mar 2002 |
Funding
∗This work has been supported by the MICS Division of the US Department of Energy. †Oak Ridge National Laboratory is managed by UT-Battelle for the LLC U.S. D.O.E. This research was supported in part by an appointment to the Oak Ridge National Laboratory Postdoctoral Research Associates Program administered jointly by the Oak Ridge Association of Universities and Oak Ridge National Laboratory.
Funders | Funder number |
---|---|
Oak Ridge National Laboratory | |
U.S. Department of Energy | |
Oak Ridge National Laboratory |
Keywords
- Clustering distributed datasets
- Distributed data mining