Efficient dynamic data structures for reachability queries on large temporal graphs

Abstract

Grafos temporais são ferramentas usadas para representar fenômenos que ocorrem ao longo do tempo. Ao incluir o tempo nos estudos sobre grafos, pode-se descrever sistemas como processos que evoluem continuamente e, assim, descobrir novas soluções em problemas relacionados. Existem várias consultas de alto nível que podem nos ajudar na análise de grafos temporais como a verificação do alcance entre vértices por meio de caminhos temporais e a reconstrução desses caminhos quando possível. Entretanto, tarefas como essas são computacionalmente intensivas e, ademais, nota-se atualmente um aumento substancial do volume de novos dados produzidos. Neste cenário, a hierarquia de memória, incluindo memórias secundárias e caches, deve ser levada em consideração durante o desenvolvimento de aplicações para grafos temporais. Neste trabalho, serão apresentadas estruturas de dados dinâmicas implementadas em memórias primária e secundária que respondem consultas de alcance em grandes grafos temporais. Dentre nossos resultados, destacamos um novo objeto matemático chamado Fecho Transitivo Temporal, uma generalização do Fecho Transitivo comumente estudado em grafos não-temporais. Usando esse novo conceito, propomos três novas estruturas de dados dinâmicas. A primeira estrutura mantém um Fecho Transitivo Temporal em memória primária usando espaço O(n2τ), responde consultas de alcance em tempo O(log τ) e insere novos contatos em O(n2 log τ), onde τ é a quantidade de etiquetas de tempo e n é o número de vértices em um grafo temporal. A segunda estrutura usa uma representação compacta, também em memória primária, que reduz o espaço utilizado pela estrutura em varios cenários e possui desempenho similar na execução das operações. Finalmente, a terceira estrutura persiste os dados em memória secundária usando espaço O(n2τ) e usa algoritmos para responder consultas de alcance e fazer atualizações que acessam, respectivamente, O(1) e O(n2τ/B) páginas em disco, ond B é o tamanho de uma página em memória secundária.