Mineração Assíncrona de Regras de Associação em Sistemas de Memória Compartilhada-Distribuída
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.
Referências
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 Mining. 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.
