ARMAZENAMENTO E PROCESSAMENTO DE CONSULTAS DE BANCO DE DADOS EM GRAFOS EM MEMÓRIA DE ESTADO SÓLIDO

Resumo

O ciclo de vida das Memorias de estado solido ;e determinado pela quantidade operações de escritas sobre o espaço de armazenamento. Portanto, reduzir a quantidade escritas em tais meios de armazenamento é fundamental para aumentar o tempo de uso. Diante disso surge a necessidade de se criar algoritmos que melhor aproveitem os SSDs. O problema abordado nbesta pesquisa foi a busca de match em grafos rotulados. Foi desenvolvido um algoritmo que dados dois grafos é possível encontrar ocorrências de um grafo dentro de outro, de forma a otimizar a quantidade de escritas em SSD. Além do algoritmo tornasse necessário a escolha de uma estrutura de dados adequadas para armazenar os grafos, foram feitas análises de diversas estruturas e constatousse que a utilização de Bitmap para realizar consulta do algoritmo é a mais indicada tanto pela performance quanto pela quantidade de memória gasta. De modo a demonstrar a eficiência do algoritmo e a utilização da estrutura escolhida, foram feitas análises de desempenho com bases de dados públicos de grafos de interações de proteínas e grafo de interação dos usuários do Twitter. O grafo de proteínas possui 2361 vértices e 7182 arestas. Ao buscar neste grafo um grafo composto de um caminho de 16 vértices e alternando as estruturas de dados utilizadas, foi percebido uma redução de 48% no tempo de execução. A base do Twitter possui mais de 41 milhões de vértices e 1,4 bilhão de arestas o confere 25GB, também foram obtidos matches rapidamente. A solução apresentada torna mais eficiente encontrar subgrafos além de diminuir a necessidade de escritas no SSD. Agradeço a CNPQ pelo investimento e amparo na pesquisa.