Density-based clustering using graphics processors

Christian Bohm, Robert Noll, Claudia Plant, Bianca Wackersreuther
University of Munich, Munich, Germany
In CIKM ’09: Proceeding of the 18th ACM conference on Information and knowledge management (2009), pp. 661-670.


   title={Density-based clustering using graphics processors},

   author={B{\”o}hm, C. and Noll, R. and Plant, C. and Wackersreuther, B.},

   booktitle={Proceeding of the 18th ACM conference on Information and knowledge management},





Download Download (PDF)   View View   Source Source   



During the last few years, GPUs have evolved from simple devices for the display signal preparation into powerful coprocessors that do not only support typical computer graphics tasks but can also be used for general numeric and symbolic computation tasks. As major advantage GPUs provide extremely high parallelism combined with a high bandwidth in memory transfer at low cost. We want to exploit these dvantages in density-based clustering, an important paradigm in clustering since typical algorithms of this category are noise and outlier robust and search for clusters of an arbitrary shape in metric and vector spaces. Moreover, with a time complexity ranging from O(n log n) to O(n2) these algorithms are scalable to large data sets in a database system. In this paper, we propose CUDA-DClust, a massively parallel algorithm for density-based clustering for the use of a Graphics Processing Unit (GPU). While the result of this algorithm is guaranteed to be equivalent to that of DBSCAN, we demonstrate a high speed-up, particularly in combination with a novel index structure for use in GPUs.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2020 hgpu.org

All rights belong to the respective authors

Contact us: