Problema de alcançabilidade em grafos muito grandes: Aplicação, complexidade e algoritmos
| Autor: | Rodrigo Ferreira da Silva |
|---|---|
| Přispěvatelé: | Sebastián Alberto Urrutia, Wagner Meira Junior, Loïc Pascal Gilles Cerf, Vinicius Fernandes dos Santos, Flávio Keidi Miyazawa, Uéverton dos Santos Souza |
| Jazyk: | portugalština |
| Rok vydání: | 2019 |
| Předmět: | |
| Zdroj: | Repositório Institucional da UFMG Universidade Federal de Minas Gerais (UFMG) instacron:UFMG |
| Popis: | Dados um grafo direcionado acíclico G=(V,E) e dois vértices quaisquer u, v em V, o problema de alcançabilidade consiste em responder se a partir de u é possível alcançar v percorrendo as arestas do grafo. Para grafos muito grandes, é inviável realizar uma busca no grafo a cada consulta ou armazenar o fecho transitivo completo. Abordagens intermediárias geram índices para efetuar cortes negativos e positivos durante a execução das consultas. Neste trabalho, identificamos algumas oportunidades para melhoria em abordagens atuais para o problema. Propomos uma nova abordagem escalável, chamada LYNX, que pode utilizar um número grande ordenações topológicas do grafo como índice de corte negativo, sem degradar o desempenho. Mostramos através de experimentos computacionais que o LYNX supera a abordagem que é considerada o estado-da-arte para grafos de alto índice de alcançabilidade. Given a directed acyclic graph G=(V,E) and two vertices u, v in V, the reachability problem is to answer if is it possible to reach v from u by transversing the edges of the graph. For very large graphs, with millions of vertices, it is infeasible to search the graph for each query and it is also infeasible to store the transitive closure of the graph since it is squared in terms of space. Then, scalable approaches aim to generate good indexes used to prune the search during its execution in the graph. In this work, we formalize the One-Sided Weak Dominance Drawing Problem which is already used informally in the literature to construct this kind of indexes and we also prove that this problem is NP-Complete. Next, we identify oportunities for improvement on main approaches for the problem. We propose a novel scalable approach called LYNX that uses a large number of topological sorts of the graph as a negative cut index without degrading the query time. A similar strategy is applied regarding the positive cut index. In addition, LYNX proposes a user-defined index size that enables the user to control the ratio between negative and positive cut depending on the expected query pattern. We show by computational experiments that LYNX outperforms the state-of-the-art approach in terms of query-time using the same index-size for graphs with high reachability ratio. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|