Processamento de Dados Massivos/Projeto e implementação de aplicações Big Data/Avaliação do algoritmo PageRank: diferenças entre revisões

[edição não verificada][edição não verificada]
Conteúdo apagado Conteúdo adicionado
Sem resumo de edição
Sem resumo de edição
Linha 88:
 
A etapa "map" é executada paralelamente para cada dado. Ela tem como entrada a chave sendo o identificador do nodo e como valor o rank atual do nó. Cada nodo passa no "map" uma vez e tem como saída cada nodo apontado por ele e o valor de rank dividido pelo número de nodos apontados.
 
<syntaxhighlight lang="Java">
public void map(
Text uid,
DoubleWritable data,
OutputCollector<Text, DoubleWritable> output,
Reporter reporter
) throws IOException {
List<Text> followees = followees_list.get(uid);
DoubleWritable dw = new DoubleWritable(data.get() / followees.size() );
Text followee = new Text();
for (Text f : followees ){
followee.set( f );
output.collect(followee, dw);
}
output.collect(uid, new DoubleWritable(0)); //Para manter no grafo
}
</syntaxhighlight>
 
A etapa "reduce" tem como entrada a chave sendo o identificador do nodo e uma lista de valores de rank/número de nodos apontados já calculados na etapa anterior. Essa etapa vai somar os valores dessa lista e retornar o novo valor de rank para o nodo identificado pela chave.
 
<syntaxhighlight lang="Java">
public void reduce(
Text key,
Iterator<DoubleWritable> values,
OutputCollector<Text, DoubleWritable> output,
Reporter reporter
) throws IOException {
double pagerank = 0;
while (values.hasNext()){
DoubleWritable dw = values.next();
pagerank += dw.get();
}
pagerank *= damping_facotr;
pagerank += first_term; // first = (1-damping_facotr)/number_of_nodes
output.collect(key, new DoubleWritable(pagerank));
}
</syntaxhighlight>
 
Como foi falado, essa estratégia não garante balanceamento de carga na etapa "reduce", porque o tempo de execução para nodos com mais apontadores seria mais longo por ter mais valores no iterador para somar.
Linha 95 ⟶ 131:
==== Estratégias de armazenamento ====
 
Ao terminar uma iteração os dados são salvos no sistema de arquivos virtual distribuído do Hadoop (HDFS) para serem lidos no início da próxima iteração. Esse sistema de arquivos é abstraído para o programador.
 
==== Estratégias de comunicação ====
Linha 130 ⟶ 166:
 
A comunicação será feita sempre entre vértices e de forma transparente, devido a utilização do paradigma de programação do GraphLab. É interessante observar que, como a versão do algoritmo PageRank implementada é a não normalizada, não é necessário o compartilhamento de valores globais entre os vértices, como o número totais de vértices, que seria necessário para a versão normalizada.
 
 
== Implementação ==
Fizemos uma implementação em Apache Hadoop 1.0.4, usando linguagem Java, e outra em GraphLab, usando linguagem C++.
 
O Hadoop tem o recurso HDFS (Hadoop Distributes File System) para armazenamento de dados.
 
=== Plataformas e ferramentas ===
Os experimentos foram executados em uma pequena rede de computadores Linux (Ubuntu 12.04) com Hadoop e GraphLab configurados para executar os programas distribuídos.
 
=== Integração de plataformas e ferramentas ===