Accelerating k-Shape Time Series Clustering Algorithm Using GPU

doi:10.1109/TPDS.2023.3298148

	Accelerating k-Shape Time Series Clustering Algorithm Using GPU
	Wang, Xun 1,2; Song, Ruibao 1; Xiao, Junmin 2; Li, Tong ; Li, Xueqi 3
	2023-10-01
发表期刊	IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
ISSN	1045-9219
卷号	34 期号:10 页码:2718-2734
摘要	In the data space, time-series analysis has emerged in many fields, including biology, healthcare, and numerous large-scale scientific facilities like astronomy, climate science, particle physics, and genomics. Clustering is one of the most critical methods in time-series analysis. So far, the state-of-art time series clustering algorithm k-Shape has been widely used not only because of its high accuracy, but also because of its relatively low computation cost. However, due to the high heterogeneity of time series data, it can not be simply regarded as a high-dimensional vector. Two time series often need some alignment method in similarity comparison. The alignment between sequences is often a time-consuming process. For example, when using dynamic time warping as a sequence alignment algorithm and if the length of time series is greater than 1,000, a single iteration in the clustering process may take hundreds to tens of thousands of seconds, while the entire clustering cycle often requires dozens of iterations. In this article, we propose a set of novel parallel strategies suitable for GPU's computation model, called Times-C, which is an abbreviation for Time Series Clustering. We define three stages in the analysis process: aggregation, centroid, and class assignment. Times-C includes efficient parallel algorithms and corresponding implementations for these three stages. Overall, the experimental results show that the Times-C algorithm exhibits a performance improvement of one to two orders of magnitude compared to the multi-core CPU version of k-Shape. Furthermore, compared to the GPU version of the k-Shape algorithm, the Times-C algorithm achieves a maximum acceleration of up to 345 times.
关键词	Data space time series analysis time series clustering GPU architecture k-shape algorithm
DOI	10.1109/TPDS.2023.3298148
收录类别	SCI
语种	英语
资助项目	National Key Ramp;D Program of China[2022YFB4500403] ; National Key Ramp;D Program of China[2021YFA1000103] ; National Key Ramp;D Program of China[2021YFA1000100] ; NSF of China[61972416] ; NSF of China[62202454] ; NSF of China[62272479] ; NSF of China[62202498] ; Taishan Scholarship[tsqn201812029] ; Foundation of Science and Technology Development of Jinan[201907116] ; Shandong Provincial Natural Science Foundation[ZR2021QF023] ; Fundamental Research Funds for the Central Universities[21CX06018A] ; Spanish project[PID2019-106960GB-I00] ; Juan de la Cierva[IJC2018-038539-I] ; China National Postdoctoral Program for Innovative Talents[BX2021320] ; Chinese Academy of Engineering Strategic Research and Consulting Program[2023-XBZD-16]
WOS研究方向	Computer Science ; Engineering
WOS类目	Computer Science, Theory & Methods ; Engineering, Electrical & Electronic
WOS记录号	WOS:001047237100004
出版者	IEEE COMPUTER SOC
引用统计	被引频次：2[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/21368
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Li, Xueqi
作者单位	1.China Univ Petr East China, Dept Comp Sci & Technol, Qingdao 266580, Peoples R China 2.Chinese Acad Sci, Inst Comp Technol, High Performance Comp Res Ctr, Beijing 100190, Peoples R China 3.Chinese Acad Sci, Inst Comp Technol, State Key Lab Processors, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Wang, Xun,Song, Ruibao,Xiao, Junmin,et al. Accelerating k-Shape Time Series Clustering Algorithm Using GPU[J]. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,2023,34(10):2718-2734.
APA	Wang, Xun,Song, Ruibao,Xiao, Junmin,Li, Tong,&Li, Xueqi.(2023).Accelerating k-Shape Time Series Clustering Algorithm Using GPU.IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,34(10),2718-2734.
MLA	Wang, Xun,et al."Accelerating k-Shape Time Series Clustering Algorithm Using GPU".IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 34.10(2023):2718-2734.