中文摘要：

随着社交网络分析、生物信息网络分析等新必应用的涌现和计算机技术的飞速发展,图的规模迅速增长,并且频繁更新,使得对大规模动态图数据的处理需求愈加迫切.现有的面向大规模动态图的可达查询研究成果较少,尚存在索引压缩困难以及图结构待优化等问题.本文提出了一种支持大规模动态图的基于改进哈夫曼编码的可达查询处理方法（Huffman-based Label Reachability,HuffLR）.该方法首先对预处理图进行结构上的两次压缩,得到双压缩图;其次,基于双压缩图提出一种前缀label索引,该索引能够有效表达节点问的可达关系;最后,提出双压缩图的演进和可达查询处理及优化算法,主要包括边的插入与删除、节点的插入与删除.实验表明,本文提出的基于改进哈夫曼编码的大规模动态图可达查询处理方法具有良好的可行性和有效性.

英文摘要：

With the emerging of applications such as Social Network Services and biological information network analysis and 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 becomes more pressing.The existing research works focusing on large scale dynamic graph are rare,which have shortcomings such as difficult index compression and needing optimizing graph structure.Therefore,in this paper,we present a reachability query processing method of dynamic large scale graph based on improved Huffman Coding,named Huffman- based Label Reachability,HuffLR.Firstly,the structure of pre- processing graph is compressed twice in order to gain the double compression graph.Secondly,the prefix- label index is constructed based on the double compression graph,which can express the reachability relations between nodes effectively.Lastly,we present the evolution of the double compression graph and reachability query processing and optimized algorithms,including insertion and deletion of edge,insertion and deletion of node.Experimental results demonstrate that the reachability query processing algorithm of dynamic large scale graph based on improved Huffman Coding has good feasibility and effectiveness.