Multi-level grid based clustering and GPU parallel implementations

Quan Qian*, Shuai Zhao, Chao Jie Xiao, Che Lun Hung

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations

Abstract

Clustering algorithm for stream data, as one of stream data mining technologies, has extensive applications on network traffic analysis, telecommunication, planetary remote sensing, web site analysis, etc. Clustering algorithm for stream data has a high demand for real-time processing, but current clustering algorithms for stream data, such as Clustream, Dstream, are all based on sequential algorithms, which are unable to meet the realtime requirement. In this paper, we propose a multi-grid based clustering algorithm for stream data. The algorithm partitions the grid space appropriately on the basis of conventional grid-based DBSCAN clustering algorithm, which can effectively limit the searching scope of grid neighbours to accelerate processing performance. Meanwhile, we utilize CUDA to conduct parallel computing in order to further speed up processing. Through the experiments tested on the KDDCUP-99 open testing dataset, it shows that the processing speed of the algorithm proposed by the paper is 10 times faster than that of the conventional grid-based algorithm and moreover the CUDA based algorithm can achieve an speedup of 3 compared with the algorithm executed on CPU.

Original languageEnglish
Title of host publicationProceedings - 14th International Symposium on Pervasive Systems, Algorithms and Networks, I-SPAN 2017, 11th International Conference on Frontier of Computer Science and Technology, FCST 2017 and 3rd International Symposium of Creative Computing, ISCC 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages397-402
Number of pages6
ISBN (Electronic)9781538608401
DOIs
StatePublished - 27 11 2017
Externally publishedYes
Event14th International Symposium on Pervasive Systems, Algorithms and Networks, I-SPAN 2017, 11th International Conference on Frontier of Computer Science and Technology, FCST 2017 and 3rd International Symposium of Creative Computing, ISCC 2017 - Exeter, Devon, United Kingdom
Duration: 21 06 201723 06 2017

Publication series

NameProceedings - 14th International Symposium on Pervasive Systems, Algorithms and Networks, I-SPAN 2017, 11th International Conference on Frontier of Computer Science and Technology, FCST 2017 and 3rd International Symposium of Creative Computing, ISCC 2017
Volume2017-November

Conference

Conference14th International Symposium on Pervasive Systems, Algorithms and Networks, I-SPAN 2017, 11th International Conference on Frontier of Computer Science and Technology, FCST 2017 and 3rd International Symposium of Creative Computing, ISCC 2017
Country/TerritoryUnited Kingdom
CityExeter, Devon
Period21/06/1723/06/17

Bibliographical note

Publisher Copyright:
© 2017 IEEE.

Keywords

  • Clustering algorithm for stream data
  • GPU parallelization
  • Multi-grid

Fingerprint

Dive into the research topics of 'Multi-level grid based clustering and GPU parallel implementations'. Together they form a unique fingerprint.

Cite this