Research On Graph Data Oriented Reachability Query Based On Interval Labeling

With the further development of Web and related domains, new applications arise and plenty of data with incidence relation have been generated. In order to represent and manage these data efficiently, researchers have proposed that they can be modeled by the graph data model with its abundant expression ability. Graph data model has been studied for a long time, however, until now graph data model has been largely used in lots of new applications for its applicability and given more attention. Different applications correspond to different graph data models and need different process methods, therefore, this phenomenon leads to different algorithms on graph data management. The effective management of graph data has been a hot field. Reachability query on graph data is a fundamental operation in graph data management and is widely used in graph data management.Currently, in allusion to graph data, several index algorithms have been proposed to answer reachability query, however, they can not scale to large graph flexibly for their limitations. In this paper, we firstly introduce existing index algorithms for reachability query on graph data and then analyze their shortages. In order to conquer the shortcomings of existing index methods, a new index algorithm for reachability query on static graph is proposed. The new index method is based on interval labeling and labels each node with four-tuple. The first two elements are interval label encoding reachability information of the spanning tree, the last two elements encode reachability information of non-tree edges. The new index method only needs index when querying and the cost of index construction is little.A number of graph data in practical applications change constantly. In order to process the reachability query on dynamic graph, we extend the newly proposed index algorithm on static graph to dynamic graph and propose a new index method for reachability query on dynamic graph.Finally, a wide range of experiments on real and synthetic datasets are conducted and prove that the newly proposed index algorithm on static graph can efficiently handle reachability query and easily scale to large graph. We also show the effectiveness of the newly proposed index algorithm for reachability query on dynamic graph through experiments.