MapReduce vs BSP para o cálculo de medidas de centralidade em grafos grandes

• Francisco Banhos Filho FACCAMP
• Eduardo Yero FACCAMP

Resumo

Técnicas de Big Data, como MapReduce, tem sido utilizadas para calcular medidas de centralidade em grafos grandes. O modelo MapReduce, no entanto, não tem produzido resultados satisfatórios em problemas deste tipo. O modelo Bulk Synchronous Parallel (BSP) tem sido considerado na literatura recente como mais apropriado para resolver problemas em grafos. Este trabalho apresenta um algoritmo baseado no modelo BSP para calcular medidas de centralidade em grafos grandes e compara seus resultados com o HEDA (Hadoop-based Exact Diamenter Algorithm) e com o HADI (Hadoopbased DIameter estimator), ambos baseados no modelo MapReduce

Referências

Internet Research Lab. (2013). Fonte: Internet Research Lab: http://irl.cs.ucla.edu/index.html

Bondy, J., & Murty, U. (2008). Graph Theory. Springer.

Dean, J., & Ghemawat, S. (2008). MapReduce: Simplied Data Processing on Large Clusters. ACM Digital Library, 107-113.

Erdos, P., & Renyi, A. (1959). On random graphs I. Publ. Math. Debrecen. v. 6., 290-297.

Kajdanowicz, T., Kazienko, P., & Indyk, W. (2014). Parallel Processing of Large Graphs. Future Generation Computer Systems 32, 324-337.

Kang, U., Tsourakakis, C. E., Appel, A. P., Faloutsos, C., & Leskovec, J. (2011). HADI: Mining Radii of Large Graphs. Journal ACM Transactions on Knowledge Discovery from Data (TKDD), Article 8.

Nascimento, J. P., & Murta, C. (2012). Um algoritmo paralelo em Hadoop para Cálculo de Centralidade em Grafos Grandes. XXX Simpósio Brasileiro de Redes de Computadores e Sistemas Distribuídos. Ouro Preto: SBC.

Pace, M. F. (2012). BSP vs MapReduce. Procedia Computer Science. v. 9, 246-255.

Valiant, L. G., Reeve, M., Zenith, S., & Wiley, E. (1989). Bulk-synchronous parallel computers. In Parallel Processing and Artificial Intelligence, 15-22.