Processamento de Dados Massivos/Projeto e implementação de aplicações Big Data/Identificação de ciclos em grafos: diferenças entre revisões
| [edição não verificada] | [edição não verificada] |
Conteúdo apagado Conteúdo adicionado
Criou nova página com ' Um método eficiênte para detectar ciclos em grafos direcionados é por meio do algoritmo de busca em profundidade. [descrever o algoritmo de detecção de ciclos usan...' Etiqueta: página grande sem wikificação |
Sem resumo de edição |
||
Linha 1:
== Introdução ==
=== Detecção de Ciclos por Busca em Profundidade ===
Um método eficiênte para detectar ciclos em grafos direcionados é por meio do algoritmo de busca em profundidade.
[[Ficheiro:GraphDFS.png|commoldura|Detecção de Ciclos por Busca em Profundidade]]
=== Detecção de Ciclos no Contexto de Dados Massivos ===
No contexto de dados massivos, o grafo possivelmente terá bilhões ou até trilhões de vértices. Dessa maneira, a estrutura do grafo pode ser grande o suficiente para saturar o poder de processamento ou a capacidade de memória de uma única máquina, surgindo a necessidade de paralelizar o algoritmo de detecção de ciclos. Entretanto, principalmente devido à sua característica recursiva, uma desvantagem do algoritmo de busca em profundidade é o fato de ser dificilmente paralelizável, embora o algoritmo seja assintoticamente ótimo.
Linha 8 ⟶ 12:
Portanto, é necessário um algoritmo que divida o problema de detecção de ciclos em subproblemas entre nós de computação, de modo que os nós busquem por cíclos de maneira paralela, garantindo que todos os ciclos serão encontrados. Propõe-se então, um algoritmo para detecção de ciclos de grafo por passagem de mensagens entre os vértices, baseado no modelo Pregel de processamento de grafos da Google. Esse modelo apresenta uma abordagem centrada nos vértices em que os vértices do grafo trabalham juntos para detectar ciclos.
== Descrição ==
O modelo do Pregel consiste basicamente em uma sequência de iterações
| |||