Use este identificador para citar ou linkar para este item:
http://hdl.handle.net/1843/ESBF-A33NE5
Tipo: | Tese de Doutorado |
Título: | Feline: um método de indexação para consultas de alcançabilidade em grandes grafos estáticos e dinâmicos |
Autor(es): | Renê Rodrigues Veloso |
Primeiro Orientador: | Wagner Meira Junior |
Primeiro Coorientador: | Loïc Pascal Gilles Cerf |
Primeiro membro da banca : | Loïc Pascal Gilles Cerf |
Segundo membro da banca: | Caetano Traina Júnior |
Terceiro membro da banca: | Jayme Luiz Szwarcfiter |
Quarto membro da banca: | Nivio Ziviani |
Quinto membro da banca: | Sebastián Alberto Urrutia |
Resumo: | Um problema-chave em diversas aplicações baseadas em grafos direcionados é a necessidade de responder rapidamente se existe um caminho entre dois vértices u e v, isto é, se u alcança v, o que é denominado consulta de alcançabilidade. Esse problema é particularmente desafiador no caso de grafos muito grandes.Uma abordagem comumente aplicada é o pré-processamento dos grafos, de forma a produzir uma estrutura de índice eficiente e que permita o rápido acesso às informações de alcançabilidade entre os vértices. No entanto, a maioria dos métodos de indexação existentes não são escaláveis. Dessa forma, a necessidade de métodos eficientes e escaláveis tem ganhado destaque nos últimos anos. Pode ser necessário indexar tanto grafos estáticos quanto dinâmicos. A indexação de grafos estáticos, i.e., grafos que não se alteram com o decorrer do tempo, deve ser tal que os tempos para construir o índice de alcançabilidade e para responder às consultas sejam os menores possíveis. A indexação em grafos dinâmicos, i.e., grafos que podem sofrer alterações ao longo do tempo, é um desafio maior. Neles, além do tempo de construção, o tempo de atualização do índice frente a inserções e remoções de vértices e arestas deve ser o menor possível (e muito menor do que reconstruir todo o índice em cada atualização do grafo), sem que o tempo para responder às consultas aumente. Há ainda a necessidade de gerenciar a ocorrência de ciclos, lidando com os componentes fortemente conectados. É proposto, então, neste trabalho, um novo método de indexação denominado Feline (Fast rEfined onLINE search). Esse método constrói um índice a partir da representação do grafo em um plano bidimensional, da qual são extraídas as informações de alcançabilidade em tempo constante para uma porção significativa de consultas. Experimentos demonstram a eficiência do método em relação às abordagens estado da arte. Como extensão do Feline, propomos também um método para a manipulação de índices para grafos dinâmicos. Essa extensão tem como base um algoritmo de Ordenação Topológica Dinâmica (DTO), o qual realiza atualizações no índice a cada modificação do respectivo grafo. Estudos comparativos são realizados e um estudo preliminar para o suporte à inserção em lotes de arestas é apresentado. Em seguida, as conclusões e oportunidades de trabalhos futuros finalizam esta tese. |
Abstract: | A key problem in many applications based on directed graphs is the need to quickly know if there is a path between two given vertices u and v, i.e., if u reaches v, which is termed reachability query. This problem is particularly challenging in the case of very large graphs. One commonly applied approach is the preprocessing of the graphs in order to produce an ecient index structure allowing quick access to the reachability information between all the vertices. However, most existing indexing strategies are not scalable. Thus, the need for new ecient and scalable strategies have gained prominence in recent years. It may be necessary to index both static and dynamic graphs. The indexing of static graphs , i.e., graphs that do not change with the passage of time, should be such that the time to build the reachability index and to answer the queries are kept to a minimum. Indexing in dynamic graphs, i.e., graphs which may change over time, is a bigger challenge. In them, besides the construction time, the time to update the index (due to the insertions and deletions of vertices and edges) should be as small as possible and much less than rebuilding the whole index on each update, without increasing the time to answer the queries. Also, there is the need to manage the occurrence of cycles, dealing with the strongly connected components. It is proposed, then, in this research, a new indexing strategy termed Feline (Fast Rened onLINE search). This approach constructs an index from the representation of the graph in a two-dimensional plane, from which are extracted reachability informations in constant time for a signicant portion of queries. Experiments demonstrate the eciency of the Feline compared to state of the art approaches. As an extension of Feline, we also propose a method for handling indexes for dynamic graphs. This extension is based on a Dynamic Topological Ordering algorithm (DTO), which updates the index in every modication of the respective graph. Comparative studies are conducted and a preliminary study to support the batch insertion of edges is also presented. Then the conclusions and future work opportunities finalize this work. |
Assunto: | Algoritmos Teoria dos grafos Computação Indexação |
Idioma: | Português |
Editor: | Universidade Federal de Minas Gerais |
Sigla da Instituição: | UFMG |
Tipo de Acesso: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/ESBF-A33NE5 |
Data do documento: | 17-Jul-2015 |
Aparece nas coleções: | Teses de Doutorado |
Arquivos associados a este item:
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
reneveloso.pdf | 8.2 MB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.