Mineração Assíncrona de Regras de Associação em Sistemas de Memória Compartilhada-Distribuída

  • A. Veloso UFMG
  • B. Coutinho UFMG
  • B. Pôssas UFMG
  • G. Menezes UFMG
  • W. Meira Jr. UFMG
  • M. Carvalho UFMG
  • C. Amorim UFRJ

Resumo


Encontrar as regras de associação presentes em grandes bases de dados é um importante problema em Mineração de Dados. Existe uma grande necessidade de desenvolver algoritmos paralelos para esse problema, uma vez que ele corresponde a um processo computacional muito custoso. No entanto, a maioria dos algoritmos propostos para minerar tais regras seguem uma busca iterativa, que impõe a necessidade de sincronização ao final de cada iteração, degradando o desempenho. Outra deficiência desses algoritmos é proveniente da contenção que ocorre no barramento de entrada e saída, uma vez que todos os processadores devem acessar simultaneamente suas respectivas porções da base de dados. Mais ainda, esses algoritmos usam somente esquemas de balanceamento de carga estático, baseados na decomposição inicial dos dados, e depois disso eles assumem uma carga homogênea, o que eslá longe da realidade, já que a carga pode variar a cada iteração do algoritmo. Nesse artigo nós apresentamos um eficiente algoritmo paralelo para minerar regras de associação em sistemas de memória Distribuída-Compartilhada. Cada processador realiza sua tarefa de mineração sem efetuar nenhuma sincronização, e a carga é continuamente balanceada entre os processadores. Mais importante, nosso algoritmo realiza apenas um acesso à base de dados, evitando o problema de contenção no sistema de entrada e saída. Os experimentos mostram que nosso algoritmo paralelo proporciona ganhos significativos quando comparado com sua parte sequencial.

Palavras-chave: Regras de Associação, Mineração de Dados, Balanceamento de Carga, Escalabilidade, Computação Paralela

Referências

AGRAWAL. R. IMIELINSKI, T. and SWAMI. A. Mining association rules between sets of items in large databases. In Proc. of 1993 ACM-SIGMOD lnt. Conf. on Management of Data. Washington, D.C., 1993.

AGRAWAL, R. and SWAMI. A. Fast Algorithms for Mining Association Rules. In Proc. of the 20th lnt. Conf. on Very Large Databases, Santiago. Chile. 1994.

CHEUNG, O. W., HU, K. and XIAO. Y. et al. Asynchronous Parallel Algorithm for Mining Association Rules on a Shared-Memory Multi-processors. In 10th ACM Symp. Parallel Algorithms and Architectures, 1998.

CHEUNG, O. W. and XIAO, Y. et al. Effect of Data Distribution in Parallel Mining of Associations. In the 12nd Pacific-Asia Conference on Knowledge Discovery and Data Mi­ning. New York, 1998.

ZAKI, M., PARTHASARATHY. S. and LI, W. et al. A Localized Algorithm for Parallel Association Mining. In 9th ACM Symp. Parallel Algorithms and Architectures, 1998.

ZAKI, M., PARTHASARATHY, S. and LI, W. et al. Parallel Data Mining for Association Rules on Shared-Memory Systems. In Supercomputing'96, Pittsburg, PA, Nov 1996.

PARTHASARATHY, S., ZAKI, M. and LI. W. et al. Memory Placement Techniques for Parallel Association Mining. In 4th lntl. Conf. Knowledge Discovery and Data Mining, 1998.

PARK, J., CHEN, M. and YU, P. et al. Efficient Parallel Data Mining for Association Rules. In Proc. of 1995 lnt. Conf. on lnformation and Knowledge Management, Baltimore. MO, Nov 1995.

HAN, E., KARYPIS. G., and KUMAR, V. et al. Scalable Paralell Data Mining for Association Rules. In Proc. of 1997 ACM-SIGMOD lnt. Conf. on Management of Data, Tucson, Arizona, 1997.

JOSHI, M., HAN, E., KARYPIS, G., and KUMAR, V. et al. Efficient Parallel Algorithms for Mining Associations. In M. J. Zaki and C.-T. Ho, editors, Lecture Notes in Computer Science: Lecture Notes in Artificial lnteligence. volume 1759. Spring-Verlag, To appear.
Publicado
10/09/2001
VELOSO, A.; COUTINHO, B.; PÔSSAS, B.; MENEZES, G.; MEIRA JR., W.; CARVALHO, M.; AMORIM, C.. Mineração Assíncrona de Regras de Associação em Sistemas de Memória Compartilhada-Distribuída. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 2. , 2001, Pirenópolis. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2001 . p. 9-16. DOI: https://doi.org/10.5753/wscad.2001.19117.