基于改进哈夫曼编码的大规模动态图可达查询方法

发布时间：2018-02-12 23:44

本文关键词： 可达查询大规模图动态图哈夫曼编码标签索引　出处：《电子学报》2017年02期 　论文类型：期刊论文

【摘要】：随着社交网络分析、生物信息网络分析等新必应用的涌现和计算机技术的飞速发展,图的规模迅速增长,并且频繁更新,使得对大规模动态图数据的处理需求愈加迫切.现有的面向大规模动态图的可达查询研究成果较少,尚存在索引压缩困难以及图结构待优化等问题.本文提出了一种支持大规模动态图的基于改进哈夫曼编码的可达查询处理方法(Huffman-based Label Reachability,HuffLR).该方法首先对预处理图进行结构上的两次压缩,得到双压缩图;其次,基于双压缩图提出一种前缀label索引,该索引能够有效表达节点问的可达关系;最后,提出双压缩图的演进和可达查询处理及优化算法,主要包括边的插入与删除、节点的插入与删除.实验表明,本文提出的基于改进哈夫曼编码的大规模动态图可达查询处理方法具有良好的可行性和有效性.
[Abstract]:With the emergence of new applications such as social network analysis, biological information network analysis, and the rapid development of computer technology, the scale of maps has grown rapidly and updated frequently. It makes the processing of large-scale dynamic graph data more urgent. There are still some problems in index compression and graph structure optimization. In this paper, an improved Huffman-based Label rehabilitation algorithm based on improved Huffman-based Label rehabilitation is proposed to support large-scale dynamic graphs. Two compressions on the structure, Secondly, a prefix label index based on the double compression graph is proposed, which can effectively express the reachability relationship between nodes. Finally, the evolution and reachability query processing and optimization algorithm of the double compression graph are proposed. The experiments show that the proposed method based on improved Huffman coding is feasible and effective for large scale dynamic graph reachable query processing.
【作者单位】：辽宁大学信息学院;
【基金】：国家自然科学基金(No.61472169,No.61502215,No.61572119,No.61303016,No.61472069,No.11547235) 辽宁省教育厅优秀人才项目(No.LR201017);辽宁省教育厅科学研究一般项目(No.L2015193) 辽宁省博士科研启动基金(No.201501127) 辽宁大学青年科研基金(No.LDQN201438)
【分类号】：O157.5

【相似文献】