UTILIZAÇÃO DE FERRAMENTAS BIG DATA NA
SOLUÇÃO DO PROBLEMA DE PAGERANK
KEMPER, Wanderson P.¹
UNEMAT, [email protected]
BANHOS FILHO, Francisco S.2
UNEMAT, [email protected]
Resumo: O avanço das tecnologias trouxe consigo a criação de gigantescas massas de dados.
Músicas, fotos, vídeos, conversas em salas de bate-papo, dados de tráfego em uma cidade, tudo
isso é armazenado gerando cerca de, 15 petabytes diariamente (IBM, 2013). A essa grande
concentração de dados dá-se o nome de Big Data. Manipular dados de maneira eficiente não é
uma tarefa simples, para tal, são necessárias ferramentas específicas para conseguir resultados
satisfatórios. Para manipular estas grandes massas de dados tem-se utilizado modelos como o
BSP (Bulk Synchronous Parallel) e o MapReduce. O presente trabalho pretende comparar os
modelos BSP e MapReduce para o problema de PageRank. O PageRank é um algoritmo que
classifica os nós de uma rede através de valores recebidos de ligações de outros nós nessa mesma
rede. Este valor aumenta conforme a quantidade de ligações e por referências de nós, com um
valor alto de PageRank (Brin; Page,1998). Estes algoritmos necessitam de resultados quase em
tempo real, e precisam ser executados em grandes aglomerados.
Palavras chave: BIG DATA, MapReduce, BSP, PageRank.
1. Introdução
Como ferramenta comumente usada na atualidade, o PageRank tornou-se uma
ferramenta de avaliação para vários estudiosos. O PageRank é um algoritmo que classifica os nós
(páginas) de uma rede através de valores recebidos de ligações de outros nós nessa mesma rede.
Este valor aumenta conforme a quantidade de ligações e por referências de nós, com um valor
alto de PageRank (Brin; Page,1998). Este algoritmo foi a fonte de sucesso da Google Inc..
O avanço das tecnologias trouxe consigo a criação de gigantescas massas de dados.
Músicas, fotos, vídeos, conversas em salas de bate-papo, dados de tráfego em uma cidade, tudo
isso é armazenado gerando cerca de, 15 petabytes diariamente (IBM, 2013). A essa grande
concentração de dados dá-se o nome de Big Data. Manipular esses dados de maneira eficiente
não é uma tarefa simples, para tal, são necessárias ferramentas específicas para conseguir
resultados satisfatórios.
Para lidar com as grandes massas de dados que são produzidas atualmente, foi
necessário criar modelos de programação que fossem ágeis em se manipular dados com estas
dimensões. Para isso, foi criado o modelo MapReduce e retomado as pesquisas a cerca do modelo
BSP. Estes modelos são amplamente utilizados para a manipulacão do Big Data. Como
representantes destes modelos temos, dois frameworks da Apache Software Foundation, o
Hadoop, implementado no modelo MapReduce, e o Hama, reprentando o modelo BSP.
Um modelo pode obter melhor desempenho frente ao outro para um determinado
problema. O presente trabalho tem como objetivo testar qual dos dois modelos pode obter o
melhor resultado para o problema de PageRank. O problema de PageRank necessita de resultados
em tempo real, e precisam ser executados em grandes aglomerados de computadores. No entanto,
para que isso seja possível é necesário que haja implementações que valorizem os recursos
disponíveis. No que segue o restante do trabalho é apresentado na seção 2 a metodologia a ser
utilizada. Na seção 3 uma breve fundamentação teórica seguido dos resultados esperados com
este trabalho.
2. Metodologia
Como metodologia será buscado na literatura algoritmos que resolvam o problema de
PageRank utilizando os modelos BSP e MapReduce. Caso não seja possível encontrar tais
algoritmos os autores do trabalho os desenvolverão. Os algoritmos serão executados em um
ambiente de cluster, realizando três tomadas de tempo. Será calculado então média e o desvio
padrão para identificar, desta forma, qual das implementações apresentará um menor tempo de
execução. Para avaliar o desempenho será calculado as medidas de speedup e eficiência. Todas as
informações serão apresentadas como tabelas, gráficos.
3. Fundamentação Teórica
3.1 MapReduce
MapReduce é um modelo de programação criado por Google para processar conjuntos
grandes de dados (Dean & Ghemawat, 2008). O modelo consiste em duas funções, map e reduce,
que combinadas permitem dividir os dados a serem processados entre um conjunto
potencialmente grande de nós de processamento e posteriormente gerar o resultado final a partir
dos resultados parciais de cada nó. A função map recebe um conjunto de pares chave/valor de
entrada e produz um conjunto de pares chave/valor intermediários. A implementação do modelo
MapReduce é então encarregada de agrupar todos os valores intermediários que têm a mesma
chave e entregá-los à função reduce, que produz o conjunto final de pares chave/valor.
3.2 BSP
O modelo Bulk Synchronous Parallel (BSP), proposto por Valient em 1989 (Valiant,
1989), define um computador abstrato que age como uma ponte entre hardware e software. Este
tipo de modelo, conhecido como bridging models, se caracteriza por conter elementos de
arquitetura de computadores e de arquitetura de software. O exemplo mais conhecido deste tipo
de modelo é a máquina de Von Neumann, que teve papel protagônico no desenvolvimento da
computação ao permitir que desenvolvedores de hardware e software pudessem trabalhar de
forma relativamente isolada focando apenas nas características do modelo descrito.
3.2 PageRank
Com a popularização da internet na década de 90, o número de páginas na web tornou-se
incrivelmente grande, com todos os tipos de dados. Classificar o que era realmente relevante na
rede tornou-se um problema ainda maior. Apesar de terem sido criados algoritmos que faziam
essa classificação, o algoritmo que realmente tornou-se eficaz foi o algoritmo desenvolvido por
uma dupla de acadêmicos da Universidade de Stanford, Lary Page e Sergey Brinn, ao qual
batizaram de PageRank (David, 2005).
Figura 1. Estrutura de funcionamento do algoritmo de PageRank.
A figura1, mostra que o algoritmo de PageRank considera as páginas da web como uma
rede de citações, onde cada pagina tem um valor inicial. Quanto maior a importância da pagina,
maior o valor da mesma. Para conseguir um alto valor de PageRank, uma pagina deve possuir
várias referencias de outras páginas. Outra forma de conseguir uma alto PageRank é sendo
referenciado por páginas com um PageRank de valor alto.(Brin; Page,1998).
4. Considerações e Resultados esperados
O presente trabalho apresenta uma proposta para um estudo comparativo entre os modelos
BSP e MapReduce para o problema de PageRank. Para tanto foi apresentado os conceitos
principais sobre os modelos estudados, bem como, uma descrição do problema de PageRank. Foi
apresentado também qual será a metodologia que será utilizada para realizar as comparações.
Costumeiramente é utilizado os conceitos de speedup e eficiência. Com os testes que serão
realizados pretende-se poder inferir qual dos modelos – BSP ou MapReduce – é mais indicado
para o problema de PageRank. Ou se os mesmos são equivalentes.
6. Referências Bibliográficas
Brin, S.; Page, L. The Anatomy of a Large-Scale Hypertextual Web Search Engine.
David, A. Vise; Mark Malseed. The Google Story. Delacorte Press.2005.
Dean, J., & Ghemawat, S. MapReduce: Simplified Data Processing on Large Clusters, 2004.
Disponível em
<https://www.usenix.org/legacy/publications/library/proceedings/osdi04/tech/full_papers/dean/de
an_html/>. Acesso em 16 de outubro de 2013.
IBM. Developerworks Big Data, o novo desafio.- Disponível em <
https://www.ibm.com/developerworks/community/blogs/ethevaldosiqueira/entry/big_data_o_nov
o_desafio?lang=en> Acessado em 15 de outubro de 2013.
Pettey, C., & Goasduff, L. Gartner Says Solving 'Big Data' Challenge Involves More Than
Just Managing Volumes of Data.: Gartner. 2012.
VALIANT, L. G. “Bulk-synchronous parallel computers”, In Parallel Processing and
Artificial Intelligence, Wiley, Chichester, UK. p. 15-22.