{en_GB=PK-Graph: Partitioned K²-Tree Graph} {} EVALUATED

Detalhes: {pt=Os grafos estão a tornarem-se cada vez maiores, tendo milhões de vértices e bilhões (ou até trilhões) de arestas em alguns casos. Desta forma, está se a tornar cada vez mais difícil colocar o grafo inteiro na memória principal de uma única máquina. Isto pode causar uma sobrecarga significativa por ter que ler o gráfico de armazenamento secundário. Por sua vez, também pode ter um impacto no desempenho no processamento e nos requisitos de armazenamento do sistema. É relevante tentar minimizar os requisitos de armazenamento dos dados do grafo sem degradar o tempo de acesso e, idealmente, até mesmo melhorá-lo. Os sistemas atuais de armazenamento de grafos armazenam estes num formato descompactado, seja numa arquitetura compartilhada, levando a uma grande sobrecarga de espaço e à incapacidade de armazenar o grafo inteiro em memória principal ou numa arquitetura distribuída, na qual todo o grafo é particionado por um grupo de máquinas e cada máquina armazena apenas parte do grafo total em memória principal. A nossa solução estende um sistema de processamento de grafos distribuído para utilizar uma representação compacta de um grafo, que ao mesmo tempo permita atualizar os seus dados, mantendo o mesmo desempenho de processamento e, idealmente, até melhorando-o., en=Graphs are becoming increasingly larger, having millions of vertices and billions (or even trillions) of edges in some cases. As a result, it's becoming harder and harder to fit the entire graph into the main-memory of a single machine. This may lead to significant overhead by having to read the graph from secondary storage. Thus causing an impact in the performance of queries and the storage requirements of the system. It is relevant to try to minimize the storage requirements of the graph data without degrading access time and, ideally, even improving it. Current graph storage systems store their graphs in an uncompressed format, either in a shared architecture, leading to high space overhead and the inability to store the entire graph in main memory or a distributed architecture, in which the entire graph is partitioned over a cluster of machines and each machine stores only a fragment of the graph in main memory. Our solution extends a distributed graph processing system to utilize a compressed representation of a graph while still allowing to update the graph data, all while maintaining the same processing performance and ideally even improving it.}

Discussão: novembro 16, 2021, 18:0

Publicação

Obra sujeita a Direitos de Autor

Orientação

AUTOR

Bruno Alexandre Coimbra Morais (ist197321)

ORIENTADOR

Luís Manuel Antunes Veiga

Departamento de Engenharia Informática (DEI)

Professor Associado