Dissertação

Processamento aproximado de grafos EVALUATED

Os grafos são utilizados para representar variadas realidades do mundo atual, e apresentam desafios específicos em termos do seu processamento em grande escala, sobretudo devido à sua dimensão e contínua mutabilidade. Começa por examinar-se o trabalho relacionado em termos de sistemas de processamento em bloco e de streams, técnicas especializadas para grafos e processamento aproximado, com a adequada categorização e contextualização. Nesse contexto, apresenta-se a biblioteca GraphApprox, concebida para ser utilizada em conjunto com o Apache Flink. O seu objetivo consiste em utilizar resultados aproximados e computação diferida como meio de otimizar o uso dos recursos computacionais e os tempos de resposta, aumentando a escalabilidade do sistema. O utilizador define um grafo inicial e uma stream de atualizações e consultas. Quando uma consulta é recebida, o utilizador, por meio de funções callback, pode definir o tipo de processamento a efetuar, exato, aproximado, ou a repetição da resposta anterior. Para essa decisão, tem acesso ao estado atual do grafo, bem como às atualizações entretanto recebidas e a estatísticas sobre as mesmas. As atualizações ao grafo são monitorizadas, a fim de poderem eficientemente obter-se estatísticas e conjuntos de vértices de interesse do grafo. Foi ainda implementado um algoritmo de aproximação ao PageRank, baseado na sumarização do grafo original. Por fim, é apresentada a arquitetura da solução implementada, as estruturas de dados e algoritmos definidos, bem como pormenores de implementação, concluindo-se com uma avaliação qualitativa e quantitativa da solução desenvolvida.
Grafo, PageRank, Processamento aproximado, Apache Flink

Novembro 9, 2016, 13:0

Publicação

Obra sujeita a Direitos de Autor

Orientação

ORIENTADOR

Luís Manuel Antunes Veiga

Departamento de Engenharia Informática (DEI)

Professor Associado