RACHET: An efficient cover-based merging of clustering hierarchies from distributed datasets

Nagiza F. Samatova, George Ostrouchov, Al Geist, Anatoli V. Melechko

Research output: Contribution to journalArticlepeer-review

51 Scopus citations

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 languageEnglish
Pages (from-to)157-180
Number of pages24
JournalDistributed and Parallel Databases
Volume11
Issue number2
StatePublished - 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.

FundersFunder number
Oak Ridge National Laboratory
U.S. Department of Energy
Oak Ridge National Laboratory

    Keywords

    • Clustering distributed datasets
    • Distributed data mining

    Fingerprint

    Dive into the research topics of 'RACHET: An efficient cover-based merging of clustering hierarchies from distributed datasets'. Together they form a unique fingerprint.

    Cite this