| Reachability queries ask whether a vertex can reach another vertex on large directed graphs.It is one of the most fundamental graph operators and has attracted researchers in both academics and industry to study it.The main technical challenge is to support fast reachability queries by efficient managing the three main costs: the index construction time,the index size and the query processing time on large and dense graphs.As real world graphs grow bigger in size,these problems remain open challenges that demand high performance solutions.In this paper,we propose a Multi-Dimensional Graph Labeling approach(called MGTag)to supporting fast reachability queries.Our MGTag approach is novel in three aspects.First,it recursively partitions a graph into multiple subgraphs with disjoint vertex sets,called non-shared graphs,and several inter-partition edges,called cross-edges.Second,we build a four-dimensional label for each vertex,which helps tagging each vertex by its layer,the non-shared graph it belongs to,and the source dimension and destination dimension interval for each vertex.With the layer label and the non-shared graph label,we can determine the topological positions in terms of non-shared graphs for any two vertices in the input graph.With the two dimensional interval label,we can efficiently answer the reachability queries for vertex pairs in the same non-shared graph.Finally,we design the MGTag algorithms to answer reachability queries efficiently and we build two directional labels---up and down labels to quickly filter irrelevant vertices and further speed up the processing of reachability queries.We evaluate MGTag by conducting extensive experiments on 28 large/small and dense/sparse graphs.We show that MGTag can build the multi-dimensional graph label index efficiently with the competitive index size,compared with most of the state-of-the-art approaches,and MGTag is highly scalable and more efficient than the state-of-the-art approaches in answering reachability queries. |
PDF Full Text Request