Parallel Processing for Density-based Spatial Clustering Algorithm using Complex Grid Partitioning and Its Performance Evaluation

摘要

Density-based spatial clustering algorithms, which have been well studied in database domains, are based on densities of geospatial data. Recently, the sizes and volumes of spatial databases have been increasing not only because of the popularity of geographical data, but also because of the popularity of geosocial media. Therefore the speedup for the processing of density-based spatial clustering algorithms is one of the most important challenges in many different application domains. In this paper, we propose a new parallelization model on a multi-core CPU using the spatial partition method for DBSCAN, which is one of the most fundamental algorithms for density-based spatial clustering. The new parallelization model utilizes a data replication technique and complex grids for the parallel processing of DBSCAN, in order to improve the speedup performance of parallel processing. The experimental results show that our new model outperforms a conventional data parallelization model.