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

NCU Institutional Repository > 資訊電機學院 > 資訊工程學系 > 期刊論文 > Item 987654321/107253

請使用永久網址來引用或連結此文件: https://ir.lib.ncu.edu.tw/handle/987654321/107253

題名:	Shortest-linkage-based parallel hierarchical clustering on main-belt moving objects of the solar system
作者:	王尉任;Tang, Cheng-Hsien;Tsai, Meng-Feng;Chuang, Shan-Hao;Cheng, Jen-Jung;Wang, Wei-Jen
貢獻者:	資訊電機學院資訊工程學系
關鍵詞:	Hierarchical clustering;Incremental update;Parallel computing
日期:	2014-05-01
上傳時間:	2026-04-23 14:02:47 (UTC+8)
出版者:	Elsevier;Elsevier B.V
摘要:	摘要： 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. •We parallelize traditional hierarchical clustering based on shortest linkage.•We use two real datasets, 550,000 and 300,000 objects, for performance evaluations.•The results show that our pruning strategy reduces execution time and storage usage.•Our fast update algorithm adds an object into a tree of 550,000 objects in seconds. 出版者： Elsevier B.V 出版日期： 2014-05 出處： Future generation computer systems, 2014-05, Vol.34, p.26-46 版權： 2013 Elsevier B.V. 識別號： ISSN: 0167-739X 識別號： EISSN: 1872-7115 識別號： DOI: 10.1016/j.future.2013.12.029
顯示於類別:	[資訊工程學系] 期刊論文

文件中的檔案:

檔案	描述	大小	格式	瀏覽次數
index.html		0Kb	HTML	11	檢視/開啟

在NCUIR中所有的資料項目都受到原著作權保護.

社群 sharing

資料載入中.....