Reachability Query Based On Improved Huffman Coding Over Large-scale Dynamic Graph

Graph data can be effectively applied to describe the complicated relations among all kinds of things in our real life. With the emerging applications like social networking services and, route planning, biological information network analysis and intelligent transportation network analysis as well as the rapid development of computer technology, the scale of graph increases quickly and updates frequently, so the demand to deal with large scale dynamic graph data becomes more pressing. As an important problem of graph data management study, the reachability query can be applied in extensive areas. The existing reachability query research works focusing on large-scale dynamic graph are rare and generally achieved by index, which bears shortcomings such as difficult index compression, optimizing graph structure and low efficiency in index and graph structure updating.Therefore, this paper presents a reachability query processing method in support of large-scale dynamic graph based on improved Huffman Coding, that is, Huffman-based Label Reachability--HuffLR. Firstly, the structure of pre-processing graph is compressed twice in structure to gain the double compression graph. Secondly, the prefix-label index is constructed based on the double compression graph, which can express effectively the reachability relations among nodes. Lastly, this paper presents the evolution of the double compression graph and reachability query processing and optimized algorithms, including insertion and deletion of edges, insertion and deletion of nodes. This method is of good feasibility and effectiveness, without allocating multiple label index to nodes, thus using less memory space and push down the complexity of initialization and updating of label index. Besides, graphs and index are greatly compressed by this method with the result of less memory space, less processing complexity and smaller scale of researching and processing graphs. Achievements of this paper are summarized as follows:A. Presenting the double compression graph structure, i.e. compressing graphs by applying DAG (Directed Acyclic Graph) firstly; then compressing the results by single-chain list method to lessen the memory space of graphs and reduce the scale of graphs in query and processing.B. Presenting a prefix-label index based on Huffman Coding and its compression algorithm; thus expressing effectively the reachability relation among nodes and reducing largely the memory space of index.C. In order to support effectively change of nodes and edges in large-scale dynamic graphs, presenting the evolution of double compression graphs and processing algorithm of reachability query, so that simplifying the research complexity in the course of frequent updating of graph data by adjusting part of data.D. A lot of experiments on simulated data sets and real data sets have shown the efficiency and feasibility of HuffLR dealing with reachablility query processing on large-scale dynamic data graphs with great query efficiency and less space of index.