Dissertação
{pt_PT=Processamento aproximado de grafos} {} EVALUATED
{pt= 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., en=Graphs are used to represent different realities of the current world, and offer particular challenges in terms of its large-scale processing, especially due to their size and continuous changeability. At first, related work in terms of batch and stream processing, techniques for graphs, and approximate processing, is revised, with proper categorization and contextualization. In this context, GraphApprox library, designed to be used with Apache Flink, is presented. Its goal is to use approximate results and deferred computing as a way to optimize the use of computing resources and response times, increasing system scalability. The user defines an initial graph and a stream of updates and queries. When a query is received, the user, through callback functions, can define the type of processing to perform: exact, approximate, or the repetition of the previous answer. For this decision, the current state of the graph, as well as the updates and statistics on them, are provided. The updates to the graph are monitored, in order to efficiently obtain statistics and sets of vertices of interest from the graph. An approximation algorithm for PageRank, based on the summarization of the original graph, has been implemented. Finally, the architecture of the designed solution is presented, with the data structures and algorithms defined, as well as details of implementation. The work concludes with a qualitative and quantitative evaluation of the developed solution.}
novembro 9, 2016, 13:0
Publicação
Obra sujeita a Direitos de Autor
Orientação
ORIENTADOR
Departamento de Engenharia Informática (DEI)
Professor Associado