Efficient parallel implementation of a density peaks clustering algorithm on graphics processing unit

Ke-shi GE; Hua-you SU; Dong-sheng LI; Xi-cheng LU

doi:10.1631/FITEE.1601786

Your Location：

Home >

Browse articles >

Efficient parallel implementation of a density peaks clustering algorithm on graphics processing unit

Regular Papers | Updated：2022-05-19

- Efficient parallel implementation of a density peaks clustering algorithm on graphics processing unit
- 基于GPU的密度峰值并行聚类算法
- Frontiers of Information Technology & Electronic Engineering Vol. 18, Issue 7, Pages: 915-927(2017)
- Affiliations：
  
  National Lab for Parallel and Distributed Processing, College of Computer, National University of Defense Technology, Changsha 410003, China
- Author bio：
  
  [ "Ke-shi GE, E-mail: gekeshi@nudt.edu.cn" ]
  [ "Hua-you SU, E-mail:huayousu@163.com" ]
  Dong-sheng LI, E-mail: dsli@nudt.edu.cn
- Funds：
- DOI：10.1631/FITEE.1601786
  CLC： TP301.6
- Received：17 December 2016，
  
  Revised：2017-;7-14，
  
  Published：2017-07
- Accepted：
Scan QR Code
Ke-shi GE, Hua-you SU, Dong-sheng LI, et al. Efficient parallel implementation of a density peaks clustering algorithm on graphics processing unit[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(7): 915-927.
DOI：

Ke-shi GE, Hua-you SU, Dong-sheng LI, et al. Efficient parallel implementation of a density peaks clustering algorithm on graphics processing unit[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(7): 915-927. DOI： 10.1631/FITEE.1601786.

摘要

基于密度峰值的聚类方法DP（density peak）由于其新颖有效的特点而广泛应用于科学研究。然而，当确定集群中心时，DP会对每对数据点操作多次，从而导致较高的计算复杂度。在本文中，我们提出了一种基于GPU（graphics processing unit）的高效并行密度峰值算法。我们分析密度峰值聚类算法的原理来研究其计算瓶颈，并评估其并行的潜力。根据分析，我们提出了CUDA-DP（compute unified device architecture-DP），一种针对GPU架构的高效并行密度峰值聚类算法，并用CUDA实现了这种并行方法。具体来说，我们使用共享内存减少了全局内存访问量。更进一步，为了利用GPU的合并访问机制，我们将CUDA-DP程序的数据结构从AOS（array of structures）重构为SOA（structure of arrays）。另外，我们分别引入二进制搜索方法和采样方法，以避免对距离矩阵进行排序造成的计算开销。实验结果表明，与基于CPU的密度峰值实现相比，CUDA-DP可以实现超过45倍的加速。

Abstract

The density peak (DP) algorithm has been widely used in scientific research due to its novel and effective peak density-based clustering approach. However

the DP algorithm uses each pair of data points several times when determining cluster centers

yielding high computational complexity. In this paper

we focus on accelerating the time-consuming density peaks algorithm with a graphics processing unit (GPU). We analyze the principle of the algorithm to locate its computational bottlenecks

and evaluate its potential for parallelism. In light of our analysis

we propose an efficient parallel DP algorithm targeting on a GPU architecture and implement this parallel method with compute unified device architecture (CUDA)

called the 'CUDA-DP platform'. Specifically

we use shared memory to improve data locality

which reduces the amount of global memory access. To exploit the coalescing accessing mechanism of GPU

we convert the data structure of the CUDA-DP program from array of structures to structure of arrays. In addition

we introduce a binary search-and-sampling method to avoid sorting a large array. The results of the experiment show that CUDA-DP can achieve a 45-fold acceleration when compared to the central processing unit based density peaks implementation.

关键词

Keywords

references

G. Andrade , , , G. Ramos , , , D. Madeira , , , 等 . . GDBSCAN: a GPU accelerated algorithm for densitybased clustering . . Proc. Comput. Sci. , , 2013 . . 18 369 - - 378 . . DOI: 10.1016/j.procs.2013.05.200 http://doi.org/10.1016/j.procs.2013.05.200 . .

D. Arlia , , , M. Coppola . . Experiments in parallel clustering with DBSCAN . . European Conf. on Parallel Processing , , 2001 . . p.326 - - 331 . . DOI: 10.1007/3-540-44681-8_46 http://doi.org/10.1007/3-540-44681-8_46 . .

N. Begum , , , L. Ulanova , , , J. Wang , , , 等 . . Accelerating dynamic time warping clustering with a novel admissible pruning strategy . . Proc. 21st ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining , , 2015 . . p.49 - - 58 . . DOI: 10.1145/2783258.2783286 http://doi.org/10.1145/2783258.2783286 . .

Y. Cheng . . Mean shift, mode seeking, and clustering . . IEEE Trans. Patt. Anal. Mach. Intell. , , 1995 . . 17 ( ( 8 ): ): 790 - - 799 . . DOI: 10.1109/34.400568 http://doi.org/10.1109/34.400568 . .

K.M. Dean , , , L.M. Davis , , , J.L. Lubbeck , , , 等 . . Highspeed multiparameter photophysical analyses of fluorophore libraries . . Anal. Chem. , , 2015 . . 87 ( ( 10 ): ): 5026 - - 5030 . . DOI: 10.1021/acs.analchem.5b00607 http://doi.org/10.1021/acs.analchem.5b00607 . .

M. Ester , , , H.P. Kriegel , , , J. Sander , , , 等 . . A densitybased algorithm for discovering clusters in large spatial databases with noise . . Proc. Int. Conf. on Knowledge Discovery and Data Mining , , 1996 . . p.226 - - 231 . . . .

P. Franti , , , O. Virmajoki , , , V. Hautamaki . . Fast agglomerative clustering using a k-nearest neighbor graph . . IEEE Trans. Patt. Anal. Mach. Intell. , , 2006 . . 28 ( ( 11 ): ): 1875 - - 1881 . . DOI: 10.1109/TPAMI.2006.227 http://doi.org/10.1109/TPAMI.2006.227 . .

K. Fukunaga , , , L. Hostetler . . The estimation of the gradient of a density function, with applications in pattern recognition . . IEEE Trans. Inform. Theory , , 1975 . . 21 ( ( 1 ): ): 32 - - 40 . . DOI: 10.1109/TIT.1975.1055330 http://doi.org/10.1109/TIT.1975.1055330 . .

A. Garg , , , A. Mangla , , , N. Gupta , , , 等 . . PBIRCH: a scalable parallel clustering algorithm for incremental data . . 10th Int. Database Engineering and Applications Symp. , , 2006 . . p.315 - - 316 . . DOI: 10.1109/IDEAS.2006.36 http://doi.org/10.1109/IDEAS.2006.36 . .

Y. He , , , F. Zhang , , , Y. Li , , , 等 . . Multiple routes recommendation system on massive taxi trajectories . . Tsinghua Sci. Technol. , , 2016 . . 21 ( ( 5 ): ): 510 - - 520 . . DOI: 10.1109/TST.2016.7590320 http://doi.org/10.1109/TST.2016.7590320 . .

T. Kohonen . . The self-organizing map . . Neurocomputing , , 1990 . . 78 ( ( 9 ): ): 1464 - - 1480 . . DOI: 10.1016/S0925-2312(98)00030-7 http://doi.org/10.1016/S0925-2312(98)00030-7 . .

J. Li , , , D. Li , , , Y. Ye , , , 等 . . Efficient multitenant virtual machine allocation in cloud data centers . . Tsinghua Sci. Technol. , , 2015 . . 20 ( ( 1 ): ): 81 - - 89 . . DOI: 10.1109/TST.2015.7040517 http://doi.org/10.1109/TST.2015.7040517 . .

M. Li , , , J. Huang , , , J. Wang . . Paralleled fast search and find of density peaks clustering algorithm on GPUs with CUDA . . 17th IEEE/ACIS Int. Conf. on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing , , 2016 . . p.313 - - 318 . . DOI: 10.1109/SNPD.2016.7515918 http://doi.org/10.1109/SNPD.2016.7515918 . .

J. MacQueen . . Some methods for classification and analysis of multivariate observations . . Proc. 5th Berkeley Symp. on Mathematical Statistics and Probability , , 1967 . . p.281 - - 297 . . . .

X. Meng , , , J. Bradley , , , B. Yavuz , , , 等 . . MLlib: machine learning in Apache Spark . . arXiv:1505.06807v1 , , 2016 . . https://arxiv.org/abs/1505.06807 https://arxiv.org/abs/1505.06807 , , . .

NVIDIA . . . . CUDA C Best Practices Guide v8.0 [Accessed on Nov. 22, 2016] , , 2016 . . 2016 http://developer.nvidia.com. http://developer.nvidia.com. , , . .

H.S. Park , , , C.H. Jun . . A simple and fast algorithm for K-medoids clustering . . Exp. Syst. Appl. , , 2009 . . 36 ( ( 2 ): ): 3336 - - 3341 . . DOI: 10.1016/j.eswa.2008.01.039 http://doi.org/10.1016/j.eswa.2008.01.039 . .

C.E. Rasmussen . . The infinite Gaussian mixture model . . Adv. Neur. Inform. Proc. Syst. , , 2000 . . 12 554 - - 560 . . . .

A. Rodriguez , , , A. Laio . . Clustering by fast search and find of density peaks . . Science , , 2014 . . 344 ( ( 6191 ): ): 1492 - - 1496 . . DOI: 10.1126/science.1242072 http://doi.org/10.1126/science.1242072 . .

T. Sarazin , , , H. Azzag , , , M. Lebbah . . SOM clustering using Spark-MapReduce . . IEEE Int. Parallel and Distributed Processing Symp. Workshops , , 2014 . . p.1727 - - 1734 . . DOI: 10.1109/IPDPSW.2014.192 http://doi.org/10.1109/IPDPSW.2014.192 . .

S.A. Shalom , , , M. Dash , , , M. Tue . . Efficient k-means clustering using accelerated graphics processors . . Int. Conf. on Data Warehousing and Knowledge Discovery , , 2008 . . p.166 - - 175 . . DOI: 10.1007/978-3-540-85836-2_16 http://doi.org/10.1007/978-3-540-85836-2_16 . .

C.J. Veenman , , , M.J.T. Reinders , , , E. Backer . . A maximum variance cluster algorithm . . IEEE Trans. Patt. Anal. Mach. Intell. , , 2002 . . 24 ( ( 9 ): ): 1273 - - 1280 . . DOI: 10.1109/TPAMI.2002.1033218 http://doi.org/10.1109/TPAMI.2002.1033218 . .

R. Xu , , , D. Wunsch . . Survey of clustering algorithms . . IEEE Trans. Neur. Netw. , , 2005 . . 16 ( ( 3 ): ): 645 - - 678 . . DOI: 10.1109/TNN.2005.845141 http://doi.org/10.1109/TNN.2005.845141 . .

X. Xu , , , J. Jäger , , , H.P. Kriegel . . A fast parallel clustering algorithm for large spatial databases . . In : Guo Y., Grossman, R. (Eds.), High Performance Data Mining: Scaling Algorithms, Applications and Systems. Springer US, Boston , , 2002 . . p.263 - - 290 . . DOI: 10.1007/0-306-47011-X_3 http://doi.org/10.1007/0-306-47011-X_3 . .

S. Zamuner , , , A. Rodriguez , , , F. Seno , , , 等 . . An efficient algorithm to perform local concerted movements of a chain molecule . . PLOS ONE , , 2015 . . 10 ( ( 3 ): ): 1 - - 27 . . DOI: 10.1371/journal.pone.0118342 http://doi.org/10.1371/journal.pone.0118342 . .

T. Zhang , , , R. Ramakrishnan , , , M. Livny . . BIRCH: a new data clustering algorithm and its applications . . Data Min. Knowl. Discov. , , 1997 . . 1 ( ( 2 ): ): 141 - - 182 . . DOI: 10.1023/A:1009783824328 http://doi.org/10.1023/A:1009783824328 . .

Y. Zhang , , , S. Chen , , , G. Yu . . Efficient distributed density peaks for clustering large data sets in MapReduce . . IEEE Trans. Knowl. Data Eng. , , 2016 . . 28 ( ( 12 ): ): 3218 - - 3230 . . DOI: 10.1109/TKDE.2016.2609423 http://doi.org/10.1109/TKDE.2016.2609423 . .

W. Zhao , , , H. Ma , , , Q. He . . Parallel k-means clustering based on MapReduce . . IEEE Int. Conf. on Cloud Computing , , 2009 . . p.674 - - 679 . . DOI: 10.1007/978-3-642-10665-1_71 http://doi.org/10.1007/978-3-642-10665-1_71 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰