RACHET
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.
Keywords for this software
References in zbMATH (referenced in 10 articles , 1 standard article )
Showing results 1 to 10 of 10.
Sorted by year (- Mashayekhi, Hoda; Habibi, Jafar; Voulgaris, Spyros; van Steen, Maarten: GoSCAN: decentralized scalable data clustering (2013)
- Kinderlehrer, David; Kowalczyk, Michał: The Janossy effect and hybrid variational principles (2009)
- Bandyopadhyay, Sanghamitra; Giannella, Chris; Maulik, Ujjwal; Kargupta, Hillol; Liu, Kun; Datta, Souptik: Clustering distributed data streams in peer-to-peer environments (2006)
- Jin, Ruoming; Goswami, Anjan; Agrawal, Gagan: Fast and exact out-of-core and distributed $k$-means clustering (2006)
- Jin, Ruoming; Goswami, Anjan; Agrawal, Gagan: Fast and exact out-of-core and distributed $k$-means clustering (2006)
- Hastings, S.; Kinderlehrer, D.: Remarks about diffusion mediated transport: thinking about motion in small systems (2005)
- Dolbeault, Jean; Kinderlehrer, David; Kowalczyk, Michał: Remarks about the flashing rachet (2004)
- Monnai, Takaaki: Fluctuation theorem in rachet system. (2004)
- Sakaguchi, Hidetsugu; Malomed, Boris A.: Stable solitons in coupled Ginzburg-Landau equations describing Bose-Einstein condensates and nonlinear optical waveguides and cavities (2003)
- Samatova, Nagiza F.; Ostrouchov, George; Geist, Al; Melechko, Anatoli V.: RACHET: An efficient cover-based merging of clustering hierarchies from distributed datasets (2002)