Shortest-linkage-based parallel hierarchical clustering on main-belt moving objects of the solar system

Cheng Hsien Tang, Meng Feng Tsai, Shan Hao Chuang, Jen Jung Cheng, Wei Jen Wang

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

Data clustering is an important data preparation process in many scientific analysis researches. In astronomy, although the distributed environments and modern observation techniques enable users to collect and access huge amounts of data, the corresponding clustering process may become very costly. One of the challenges is that the sequential clustering algorithms, that can be applied to cluster hundreds of thousand main-belt asteroids to reason about the origins of the main-belt asteroids, may not be used in the distributed environment directly. Therefore, this study focuses on the problem of parallelizing the traditional hierarchical agglomerative clustering algorithm using shortest-linkage. We propose a new parallel hierarchical agglomerative clustering algorithm based on the master-worker model. The master process divides the whole computation into several small tasks, and distributes the tasks to the worker processes for parallel processing. Then, the master process merges the results from the worker processes to form a hierarchical data structure. The proposed algorithm uses a pruning threshold to reduce the execution time and the storage requirement during the computation. It also supports fast incremental update that merges new data items into a constructed hierarchical tree in seconds, given a tree of about 550,000 data items. To evaluate the performance of our algorithm, this study has conducted several experiments using the MPCORB dataset and a dataset from the DVO database. The results confirm the efficiency of our proposed methodology. Compared with prior similar studies, the proposed algorithm is more flexible and practical in the problem of distributed hierarchical agglomerative clustering.

Original languageEnglish
Pages (from-to)26-46
Number of pages21
JournalFuture Generation Computer Systems
Volume34
DOIs
StatePublished - May 2014

Keywords

  • Hierarchical clustering
  • Incremental update
  • Parallel computing

Fingerprint

Dive into the research topics of 'Shortest-linkage-based parallel hierarchical clustering on main-belt moving objects of the solar system'. Together they form a unique fingerprint.

Cite this