MultiDBSCAN: Exploração Paralela de Múltiplos Raios em GPU
Resumo
O DBSCAN identifica agrupamentos de formatos arbitrários com base na densidade dos pontos. Entretanto, seus resultados são sensíveis ao raio de vizinhança ε, o que, na prática, exige avaliar uma faixa de valores e comparar as partições resultantes. Implementações em GPU geralmente processam um único ε por execução e, portanto, repetem o cálculo das distâncias para cada raio testado. Este trabalho apresenta o MultiDBSCAN, que avalia vários valores de ε em uma única execução, mantendo minPts fixo. As distâncias são obtidas em ladrilhos da matriz de produtos escalares e compartilhadas entre os raios, enquanto estruturas Union-Find independentes constroem os agrupamentos de cada configuração. Em seis conjuntos de dados e cinco raios, o método alcançou aceleração média geométrica de 5,09× sobre a soma de cinco execuções independentes do NVIDIA cuML e de 32,78× sobre a soma de cinco execuções do CUDA-DClust+, mantendo ARI médio acima de 0,98 em relação ao cuML.
Referências
Abdulhameed, T. Z., Yousif, S. A., Samawi, V. W., and Al-Shaikhli, H. I. (2024). Ssdbscan: semi-supervised density-based spatial clustering of applications with noise for meaningful clustering in diverse density data. IEEE Access, 12:131507–131520.
Andrade, G., Ramos, G., Madeira, D., Sachetto, R., Ferreira, R., and Rocha, L. (2013). G-dbscan: A gpu accelerated algorithm for density-based clustering. Procedia Computer Science, 18:369–378.
Ankerst, M., Breunig, M. M., Kriegel, H.-P., and Sander, J. (1999). Optics: Ordering points to identify the clustering structure. ACM Sigmod record, 28(2):49–60.
Barros, O., Freitas, I., Pereira, P. H., Neto, W. d. B., Alcolea, A., Villarroya-Gaudó, M., Resano, J., Nacif, J. A. M., and Ferreira, R. (2026). Rethinking per-thread computation for machine learning design exploration: A work-efficient gpu strategy for k-means and xgboost. Concurrency and Computation: Practice and Experience, 38(11):e70744.
Bueno, W., Silva, O., Nacif, J. A., and Ferreira, R. (2024). Implementação paralela de múltiplos k-means em gpu. In Simpósio em Sistemas Computacionais de Alto Desempenho (SSCAD), pages 37–48. SBC.
Bushra, A. A. and Yi, G. (2021). Comparative analysis review of pioneering dbscan and successive density-based clustering algorithms. IEEE Access, 9:87918–87935.
Böhm, C., Noll, R., Plant, C., and Wackersreuther, B. (2009). Density-based clustering using graphics processors. pages 661–670.
Çelik, M., Dadaşer-Çelik, F., and Dokuz, A. Ş. (2011). Anomaly detection in temperature data using dbscan algorithm. In 2011 international symposium on innovations in intelligent systems and applications, pages 91–95. IEEE.
Ester, M., Kriegel, H.-P., Sander, J., and Xu, X. (1996). A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, KDD’96, page 226–231. AAAI Press.
Fahim, A. (2023). Adaptive density-based spatial clustering of applications with noise (adbscan) for clusters of different densities. Computers, Materials and Continua, 75(2):3695–3712.
Goulart, J. L. d. J. et al. (2024). Árvore de decisão por agrupamento com dbscan aproximativo.
Gupta, M., Mishra, A., Mishra, A., and Gangrade, J. (2024). Accelerated gpu-based clustering, classification and regression using rapids: A comparative study. In International Conference on Computation of Artificial Intelligence & Machine Learning, pages 239–253. Springer.
Kiran, B. V. S., Kowshik, M. A., Manohar, A. L., Siddardha, D. R., Kavitha, M., and Kavitha, S. (2024). Enhancing accident prediction through integrated knn and dbscan algorithms for superior accuracy. In 2024 8th International Conference on Inventive Systems and Control (ICISC), pages 423–428. IEEE.
Kuo, F.-Y., Wen, T.-H., and Sabel, C. E. (2018). Characterizing diffusion dynamics of disease clustering: a modified space–time dbscan (mst-dbscan) algorithm. Annals of the American Association of Geographers, 108(4):1168–1186.
Poudel, M. and Gowanlock, M. (2021a). Conjuntos de dados do CUDA-DClust+ para o HiPC 2021. [link]. Acesso em: 15 ago. 2026.
Poudel, M. and Gowanlock, M. (2021b). Cuda-dclust+: Revisiting early gpu-accelerated dbscan clustering designs. In 2021 IEEE 28th International Conference on High Performance Computing, Data, and Analytics (HiPC), pages 354–363. IEEE.
Sarkar, T. (2022). Gpu-based data science for high productivity. In Productive and Efficient Data Science with Python: With Modularizing, Memory profiles, and Parallel/GPU Processing, pages 299–326. Springer.
Thapa, R. J., Trefftz, C., and Wolffe, G. (2010). Memory-efficient implementation of a graphics processor-based cluster detection algorithm for large spatial databases. In 2010 IEEE International Conference on Electro/Information Technology, pages 1–5. IEEE.
Zhang, X., Lauber, L., Liu, H., Shi, J., Wu, J., and Pan, Y. (2021). Research on the method of travel area clustering of urban public transport based on sage-husa adaptive filter and improved dbscan algorithm. PLoS one, 16(12):e0259472.
Zhou, S., Xu, H., Zheng, Z., Chen, J., Li, Z., Bu, J., Wu, J., Wang, X., Zhu, W., and Ester, M. (2024). A comprehensive survey on deep clustering: Taxonomy, challenges, and future directions. ACM Computing Surveys, 57(3):1–38.
Andrade, G., Ramos, G., Madeira, D., Sachetto, R., Ferreira, R., and Rocha, L. (2013). G-dbscan: A gpu accelerated algorithm for density-based clustering. Procedia Computer Science, 18:369–378.
Ankerst, M., Breunig, M. M., Kriegel, H.-P., and Sander, J. (1999). Optics: Ordering points to identify the clustering structure. ACM Sigmod record, 28(2):49–60.
Barros, O., Freitas, I., Pereira, P. H., Neto, W. d. B., Alcolea, A., Villarroya-Gaudó, M., Resano, J., Nacif, J. A. M., and Ferreira, R. (2026). Rethinking per-thread computation for machine learning design exploration: A work-efficient gpu strategy for k-means and xgboost. Concurrency and Computation: Practice and Experience, 38(11):e70744.
Bueno, W., Silva, O., Nacif, J. A., and Ferreira, R. (2024). Implementação paralela de múltiplos k-means em gpu. In Simpósio em Sistemas Computacionais de Alto Desempenho (SSCAD), pages 37–48. SBC.
Bushra, A. A. and Yi, G. (2021). Comparative analysis review of pioneering dbscan and successive density-based clustering algorithms. IEEE Access, 9:87918–87935.
Böhm, C., Noll, R., Plant, C., and Wackersreuther, B. (2009). Density-based clustering using graphics processors. pages 661–670.
Çelik, M., Dadaşer-Çelik, F., and Dokuz, A. Ş. (2011). Anomaly detection in temperature data using dbscan algorithm. In 2011 international symposium on innovations in intelligent systems and applications, pages 91–95. IEEE.
Ester, M., Kriegel, H.-P., Sander, J., and Xu, X. (1996). A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, KDD’96, page 226–231. AAAI Press.
Fahim, A. (2023). Adaptive density-based spatial clustering of applications with noise (adbscan) for clusters of different densities. Computers, Materials and Continua, 75(2):3695–3712.
Goulart, J. L. d. J. et al. (2024). Árvore de decisão por agrupamento com dbscan aproximativo.
Gupta, M., Mishra, A., Mishra, A., and Gangrade, J. (2024). Accelerated gpu-based clustering, classification and regression using rapids: A comparative study. In International Conference on Computation of Artificial Intelligence & Machine Learning, pages 239–253. Springer.
Kiran, B. V. S., Kowshik, M. A., Manohar, A. L., Siddardha, D. R., Kavitha, M., and Kavitha, S. (2024). Enhancing accident prediction through integrated knn and dbscan algorithms for superior accuracy. In 2024 8th International Conference on Inventive Systems and Control (ICISC), pages 423–428. IEEE.
Kuo, F.-Y., Wen, T.-H., and Sabel, C. E. (2018). Characterizing diffusion dynamics of disease clustering: a modified space–time dbscan (mst-dbscan) algorithm. Annals of the American Association of Geographers, 108(4):1168–1186.
Poudel, M. and Gowanlock, M. (2021a). Conjuntos de dados do CUDA-DClust+ para o HiPC 2021. [link]. Acesso em: 15 ago. 2026.
Poudel, M. and Gowanlock, M. (2021b). Cuda-dclust+: Revisiting early gpu-accelerated dbscan clustering designs. In 2021 IEEE 28th International Conference on High Performance Computing, Data, and Analytics (HiPC), pages 354–363. IEEE.
Sarkar, T. (2022). Gpu-based data science for high productivity. In Productive and Efficient Data Science with Python: With Modularizing, Memory profiles, and Parallel/GPU Processing, pages 299–326. Springer.
Thapa, R. J., Trefftz, C., and Wolffe, G. (2010). Memory-efficient implementation of a graphics processor-based cluster detection algorithm for large spatial databases. In 2010 IEEE International Conference on Electro/Information Technology, pages 1–5. IEEE.
Zhang, X., Lauber, L., Liu, H., Shi, J., Wu, J., and Pan, Y. (2021). Research on the method of travel area clustering of urban public transport based on sage-husa adaptive filter and improved dbscan algorithm. PLoS one, 16(12):e0259472.
Zhou, S., Xu, H., Zheng, Z., Chen, J., Li, Z., Bu, J., Wu, J., Wang, X., Zhu, W., and Ester, M. (2024). A comprehensive survey on deep clustering: Taxonomy, challenges, and future directions. ACM Computing Surveys, 57(3):1–38.
Publicado
03/11/2026
Como Citar
BUENO, Walter; PEREIRA, Matheus; BARROS, Olavo; NACIF, José; FERREIRA, Ricardo.
MultiDBSCAN: Exploração Paralela de Múltiplos Raios em GPU. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 27. , 2026, Natal/RN.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 315-328.
DOI: https://doi.org/10.5753/sscad.2026.34937.
