Feline: um método de indexação para consultas de alcançabilidade em grandes grafos estáticos e dinâmicos

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.