Uma Estratégia Eficiente para Balanceamento de Carga em Algoritmos de Mineração de Conjuntos Freqüentes

• Fernando Mourão UFMG
• Luciano Lanna UFMG
• Adriano Veloso UFMG
• Wagner Meira Jr. UFMG
• Renato Ferreira UFMG
• Dorgival Guedes UFMG

DOI: https://doi.org/10.5753/wscad.2006.18947

Resumo

Mineração de dados compreende um conjunto de técnicas para extração automática de informações a partir de grandes bases de dados, atividade cada vez mais fundamental tendo em visto o acúmulo contínuo e crescente de dados e uma carência crescente de extrair informações úteis a partir desses dados. Uma estratégia comum para atender essa demanda é a paralelização dos algoritmos, os quais, tendo em vista a natureza irregular de muitas das técnicas de mineração de dados, tendem a apresentar significativo desbalanceamento de carga. Neste artigo avaliamos algumas estratégias de balanceamento de carga para algoritmos paralelos de mineração de dados e discutimos os compromissos entre balanceamento estático e dinâmico. Também propomos e avaliamos uma nova técnica de balanceamento de carga que leva em consideração as peculiaridades da classe de algoritmos e que se mostrou mais eficiente que as outras técnicas discutidas, a despeito das características das bases de dados sendo mineradas.

Referências

R. Agrawal, T. Imielinski, and A. Swami. Mining association rules between sets of items in large databases. In Proc. of the Int. Conf. on Management of Data, SIGMOD, pages 207–216, Washington, USA, May 1993. ACM.

R. Agrawal and J. Shafer. Parallel mining of association rules. Transactions on Knowledge and Data Engineering, 8(6):962–969, 1996.

R. Agrawal and R. Srikant. Fast algorithms for mining association rules. In Proc. of the Int. Conf. on Very Large Databases, VLDB, pages 487–499, SanTiago, Chile, June 1994. VLDB.

D. Cheung and Y. Xiao. Effect of data distribution in parallel mining of associations. Data Mining and Knowledge Discovery, 3(3):291–314, 1999.

M. Cierniak, M. Zaki, and W. Li. Compile-time scheduling algorithms for a heterogeneous network of workstations. The Computer Journal, 40(6):356–372, December 1997.

R. Ferreira, W. M. Jr., D. Guedes, L. Drummond, B. Coutinho, G. Teodoro, T. T. and R. Araújo, and G. Ferreira. Anthill: A scalable run-time environment for data mining applications. In Proc. SBAC-PAD, pages 159–167, Rio de Janeiro, Brazil, October 2005. IEEE.

E. Han, G. Karypis, and V. Kumar. Scalable parallel data mining for association rules. Transactions on Knowledge and Data Engineering, 12(3):728–737, 2000.

M. Zaki and S. Parthasarathy. A localized algorithm for parallel association mining. In Proc. Symp. on Parallel Algorithms and Applications, SPAA, pages 120–128. ACM, Aug 1997.

M. Zaki, S. Parthasarathy, M. Ogihara, and W. Li. New algorithms for fast discovery of association rules. In Proc. of the Int. Conf. on Knowledge Discovery and Data Mining, SIGKDD, pages 283–290. ACM, August 1997.

M. Zaki, S. Parthasarathy, M. Ogihara, and W. Li. New parallel algorithms for fast discovery of association rules. Data Mining and Knowledge Discovery, 4(1):343–373, December 1997.