Algoritmos de Particionamento e Banco de Dados Orientado a Grafos.

Abstract

Esta dissertação apresenta uma arquitetura de software que permite aos seus usuários implementar algoritmos de particionamento de grafos, possibilitando o reaproveitamento das implementações dos algoritmos em estruturas de armazenamento do grafo em memória ou no banco de dados orientado a grafos Neo4J. Considerando o aumento do volume de informações geradas atualmente, o uso da memória principal se torna um problema, impondo o uso de meios persistentes para o armazenamento das informações através de um banco de dados. Porém, o usuário não deve se preocupar com a forma de armazenamento do grafo, mas sim com a lógica do algoritmo em si, utilizando uma estrutura genérica padronizada. Para dar suporte à elaboração da arquitetura, são apresentados, além dos conceitos de grafos, os aspectos envolvidos no particionamento, que são utilizados pelos algoritmos apresentados, as principais características do banco de dados Neo4J, os diferentes tipos de heurísticas utilizadas, desde o conhecimento local até o uso de técnicas globais de particionamento, com o uso da teoria espectral dos grafos. A arquitetura é validada com a implementação e execução de quatro algoritmos clássicos de particionamento, utilizando grafos sintéticos com corte de arestas conhecidos. Também é mostrado a comparação de desempenho destes algoritmos manipulando grafos maiores disponibilizados pela comunidade.