Fast density-based clustering through dataset partition using graphics processing units

作     者：Loh, Woong-Kee Yu, Hwanjo 

作者机构：Gachon Univ Dept Software Songnam South Korea POSTECH Dept Comp Sci & Engn Pohang Si Gyeongsangbuk D South Korea 

出 版 物：《INFORMATION SCIENCES》 (信息科学)

年 卷 期：2015年第308卷

页      面：94-112页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Basic Science Research Program through the National Research Foundation (NRF) - Ministry of Education, Science and Technology (MEST) [2010-0025001] Mid-career Researcher Program through NRF Grant - MEST [NRF-2013R1A2A2A01067425] 

主　　题：Density-based clustering Graphics processing unit Massively parallel algorithm Dataset partition On-chip shared memory 

摘      要：Graphics processing units (GPUs) have been utilized to improve the processing speed of many conventional data mining algorithms. DBSCAN, a popular clustering algorithm that has been often used in practice, was extended to execute on a GPU. However, existing GPU-based DBSCAN extensions still have impediments in that the distances from all objects need to be repeatedly computed to find the neighbor objects and the objects and intermediate clustering results are stored in costly off-chip memory of the GPU. This paper proposes CudaSCAN, a novel algorithm that improves the efficiency of DBSCAN by making better use of the GPU. CudaSCAN consists of three phases: (1) partitioning the entire dataset into sub-regions of size of an integer multiple of the on-chip shared memory size in the GPU;(2) local clustering within sub-regions in parallel;and (3) merging the local clustering results. CudaSCAN allows an overlap between sub-regions to ensure independent, parallel local clustering in each sub-region, which in turn enables for objects and/or intermediate results to be stored in on-chip shared memory that has an access cost a few hundred times cheaper than that of off-chip global memory. The independence also enables for merging to be parallelized. This paper proves the correctness of CudaSCAN, and according to our extensive experiments, CudaSCAN outperforms CUDA-DClust, a previous GPU-based DBSCAN extension, by up to 163.6 times. (C) 2014 Elsevier Inc. All rights reserved.