Paralelização da Indexação de Dados no OPTICS via GPU
Resumo
Organizar o grande volume de dados que vem sendo gerado recentemente tornou-se um dos grandes problemas na computação. Dentre as estratégias que se propõem a lidar com esse problema, destacam-se os de agrupamento baseado em densidade, tais como DBSCAN e OPTICS. Essas técnicas permitem agrupamento de dados em formato arbitrário lidando com ruídos de forma robusta. Nesse trabalho apresentamos uma nova abordagem do OPTICS baseada em uma estratégia de indexação de dados por meio de grafos, reduzindo consideravelmente a complexidade do algoritmo. Explorando algumas oportunidades de paralelização utilizando GPUs, mostramos que a nossa proposta é até 200x mais rápida do que sua versão sequencial usando CPU.
Referências
Aggarwal, C. C. and Reddy, C. K. (2013). Data Clustering: Algorithms and Applications. Chapman & Hall/CRC, 1st edition.
Agrawal, R., Gehrke, J., Gunopulos, D., and Raghavan, P. (1998). Automatic subspace clustering of high dimensional data for data mining applications. In ACM SIGMOD.
Andrade, G., Ramos, G., Madeira, D., Sachetto, R., Ferreira, R., and Rocha, L. (2013). G-dbscan: A gpu accelerated algorithm for density-based clustering. ICCS.
Ankerst, M., Breunig, M. M., Kriegel, H.-P., and Sander, J. (1999). Optics: Ordering points to identify the clustering structure. In ACM SIGMOD.
Blelloch, G. E. (1990). Prefix sums and their applications. Technical Report CMU-CS-90-190, School of Computer Science, Carnegie Mellon University.
B¨ohm, C., Noll, R., Plant, C., and Wackersreuther, B. (2009). Density-based clustering using graphics processors. In ACM CIKM.
Christen, P. (2012). A survey of indexing techniques for scalable record linkage and deduplication. IEEE Transactions on Knowledge and Data Engineering.
Ester, M., peter Kriegel, H., S, J., and Xu, X. (1996). A density-based algorithm for discovering clusters in large spatial databases with noise. pages 226–231. AAAI Press.
Jain, A. K., Murty, M. N., and Flynn, P. J. (1999). Data clustering: a review. ACM Comput. Surv., 31(3):264–323.
Karypis, G. and Kumar, V. (1998). A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput., 20(1):359–392.
Patwary, M. A., Palsetia, D., Agrawal, A., Liao, W.-k., Manne, F., and Choudhary, A. (2013). Scalable parallel optics data clustering using graph algorithmic techniques. In Proc. of ACM SC.
Agrawal, R., Gehrke, J., Gunopulos, D., and Raghavan, P. (1998). Automatic subspace clustering of high dimensional data for data mining applications. In ACM SIGMOD.
Andrade, G., Ramos, G., Madeira, D., Sachetto, R., Ferreira, R., and Rocha, L. (2013). G-dbscan: A gpu accelerated algorithm for density-based clustering. ICCS.
Ankerst, M., Breunig, M. M., Kriegel, H.-P., and Sander, J. (1999). Optics: Ordering points to identify the clustering structure. In ACM SIGMOD.
Blelloch, G. E. (1990). Prefix sums and their applications. Technical Report CMU-CS-90-190, School of Computer Science, Carnegie Mellon University.
B¨ohm, C., Noll, R., Plant, C., and Wackersreuther, B. (2009). Density-based clustering using graphics processors. In ACM CIKM.
Christen, P. (2012). A survey of indexing techniques for scalable record linkage and deduplication. IEEE Transactions on Knowledge and Data Engineering.
Ester, M., peter Kriegel, H., S, J., and Xu, X. (1996). A density-based algorithm for discovering clusters in large spatial databases with noise. pages 226–231. AAAI Press.
Jain, A. K., Murty, M. N., and Flynn, P. J. (1999). Data clustering: a review. ACM Comput. Surv., 31(3):264–323.
Karypis, G. and Kumar, V. (1998). A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput., 20(1):359–392.
Patwary, M. A., Palsetia, D., Agrawal, A., Liao, W.-k., Manne, F., and Choudhary, A. (2013). Scalable parallel optics data clustering using graph algorithmic techniques. In Proc. of ACM SC.
Publicado
04/07/2016
Como Citar
TOLEDO, Sávyo; MELO, Danilo; ANDRADE, Guilherme; MOURÃO, Fernando; ROCHA, Leonardo.
Paralelização da Indexação de Dados no OPTICS via GPU. In: CONCURSO DE TRABALHOS DE INICIAÇÃO CIENTÍFICA DA SBC (CTIC-SBC), 35. , 2016, Porto Alegre.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2016
.
p. 91-100.
