Fast LCA - Algoritmo baseado em MapReduce para solução do Menor Ancestral Comum
Resumo
Nos tempos atuais, onde a quantidade de informações está crescendo rapidamente, a análise de problemas que podem ser representados por grafos emerge como uma abordagem intrigante. Um desses problemas é o Menor Ancestral Comum, amplamente utilizado na filogenética e em diversas outras áreas de pesquisa. Neste estudo, apresentamos um algoritmo que aborda o problema do Menor Ancestral Comum, empregando o paradigma MapReduce e implementado com o auxílio do Framework Apache Hadoop. Executamos o algoritmo em um cluster de computadores e avaliamos seu desempenho por meio de medidas de speedup e eficiência.
Palavras-chave:
MapReduce, Hadoop, Cluster, Menor Ancestral Comum, Computação Paralela
Referências
Aho, A. V., Hopcroft, J. E., and Ullman, J. D. (1973). On finding lowest common ancestors in trees. In Proceedings of the fifth annual ACM symposium on Theory of computing, pages 253–265.
Banhos Filho, F. and Yero, E. (2014). Mapreduce vs bsp para o cálculo de medidas de centralidade em grafos grandes. In Anais do XIII Workshop em Desempenho de Sistemas Computacionais e de Comunicação, pages 183–187. SBC.
Banhos Filho, F. S. and Yero, E. J. H. (2016). Exact vs. approximated diameter calculation in large graphs. In 2016 24th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP), pages 256–263. IEEE.
Dean, J. and Ghemawat, S. (2008). Mapreduce: simplified data processing on large clusters. Communications of the ACM, 51(1):107–113.
Foundation, T. A. S. (2017). Hdfs high availability. [link]. Acessado em: 24 de julho de 2022.
Hortonworks (2016). Cluster planning guide. [link]. Acessado em: 22 de julho de 2021.
Kumar, V., Grama, A., Gupta, A., and Karypis, G. (1994). Introduction to parallel computing, volume 110. Benjamin/Cummings Redwood City, CA.
Masur, R. G. and Mcintosh, S. K. (2017). Preliminary performance analysis of hadoop 3.0. 0-alpha3. In 2017 New York Scientific Data Summit (NYSDS), pages 1–3. IEEE.
Networks, J. (2013). Ex2200-24t-4g switch hardware guide. [link]. Acessado em: 24 de abril de 2022.
Systems, C. (2011). Big data in the enterprise network design considerations white paper. Technical report, Cisco Systems.
White, T. (2015). Hadoop: The definitive guide, storage and analysis at internet scale. White–London: O’Reilly Media.
Zhao, G., Bu, D., Liu, C., Li, J., Yang, J., Liu, Z., Zhao, Y., and Chen, R. (2012). Cloudlca: finding the lowest common ancestor in metagenome analysis using cloud computing. Protein & cell, 3(2):148–152.
Banhos Filho, F. and Yero, E. (2014). Mapreduce vs bsp para o cálculo de medidas de centralidade em grafos grandes. In Anais do XIII Workshop em Desempenho de Sistemas Computacionais e de Comunicação, pages 183–187. SBC.
Banhos Filho, F. S. and Yero, E. J. H. (2016). Exact vs. approximated diameter calculation in large graphs. In 2016 24th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP), pages 256–263. IEEE.
Dean, J. and Ghemawat, S. (2008). Mapreduce: simplified data processing on large clusters. Communications of the ACM, 51(1):107–113.
Foundation, T. A. S. (2017). Hdfs high availability. [link]. Acessado em: 24 de julho de 2022.
Hortonworks (2016). Cluster planning guide. [link]. Acessado em: 22 de julho de 2021.
Kumar, V., Grama, A., Gupta, A., and Karypis, G. (1994). Introduction to parallel computing, volume 110. Benjamin/Cummings Redwood City, CA.
Masur, R. G. and Mcintosh, S. K. (2017). Preliminary performance analysis of hadoop 3.0. 0-alpha3. In 2017 New York Scientific Data Summit (NYSDS), pages 1–3. IEEE.
Networks, J. (2013). Ex2200-24t-4g switch hardware guide. [link]. Acessado em: 24 de abril de 2022.
Systems, C. (2011). Big data in the enterprise network design considerations white paper. Technical report, Cisco Systems.
White, T. (2015). Hadoop: The definitive guide, storage and analysis at internet scale. White–London: O’Reilly Media.
Zhao, G., Bu, D., Liu, C., Li, J., Yang, J., Liu, Z., Zhao, Y., and Chen, R. (2012). Cloudlca: finding the lowest common ancestor in metagenome analysis using cloud computing. Protein & cell, 3(2):148–152.
Publicado
28/11/2023
Como Citar
DIAS, Jorgi Luiz Bolonhezi; BANHOS FILHO, Francisco Sanches.
Fast LCA - Algoritmo baseado em MapReduce para solução do Menor Ancestral Comum. In: ESCOLA REGIONAL DE INFORMÁTICA DE MATO GROSSO (ERI-MT), 12. , 2023, Cuiabá/MT.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 50-57.
ISSN 2447-5386.
DOI: https://doi.org/10.5753/eri-mt.2023.236337.
