FenixEdu™

Dissertação

PK-Graph: Partitioned K²-Tree Graph EVALUATED

Detalhes: 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.
Keywords: base de dados de grafos, sistema de processamento de grafos, representação de grafos, optimizações, compressão

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