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

As primeiras propostas de paralelização do algoritmo PageRank foram desenvolvidas implementando a versão matricial do algoritmo em resolvedores de sistema linear paralelos<ref name="cite1">Atish Das Sarma, Anisur Rahaman Molla, Gopal Pandurangan, Eli Upfal, "Fast Distributed PageRank Computation", CoRR, 2012</ref>.

Outra estratégia utilizada é o esquema "URL Host", que aproveita a estrutura hierárquica da WEB para fazer a parelização. Basicamente o que ele faz é agrupar os vértices de página de um mesmo domínio (host) e fazer a computação distribuída. Apesar de eficiente, essa estratégia fica limitada a grafos que representem páginas de internet, sendo inadequada para uma abordagem mais genérica<ref name="cite2"></ref>.

Existem algumas versões de PageRank que fornecem valores aproximados, que na maioria das vezes é justificado pela eficiência no tempo de execução, e uma vertente desses algoritmos faz uma abordagem paralela. Uma dessas abordagens utiliza um esquema MapReduce que utiliza um modelo probabilístico e utiliza o método de Monte Carlo para calcular os valores. <ref name="cite1cite3">AtishBahman Das SarmaBahmani, AnisurKaushik Rahaman MollaChakrabarti, GopalDong Pandurangan, Eli UpfalXin, "Fast DistributedPersonalized PageRank Computationon MapReduce", CoRR, 2012</ref>.

Há ainda tentativas de implementação do algoritmo em placas gráficas (GPUs), que são arquiteturas fortemente paralelas e com enorme poder de processamento<ref name="cite2cite4">WU, T. et al., "Efficient pagerank and spmv computation on amd gpus". ICPP, 2010</ref>. Apesar de eficientes, a maioria dessas abordagens fica limitada pela memória local limitada, então para aplicações práticas de alto porte, é necessária uma estratégia auxiliar.