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

• 作者: 丁琳琳 宋宝燕 李正道 纪婉婷
• 来源期刊: 电子学报
• 学科: 工学
• 关键词: 可达查询 大规模图 动态图 哈夫曼编码 标签索引
• 年，卷（期）: 2017,（2）
• 所属期刊栏目: 学术论文
• 页码范围: 359-367
• 页数: 9页
• 分类号: TP311
• 字数: 6832字
• 语种: 中文
• DOI: 10.3969/j.issn.0372-2112.2017.02.014

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	宋宝燕	辽宁大学信息学院	87	360	11.0	15.0
2	丁琳琳	辽宁大学信息学院	16	19	3.0	3.0
3	纪婉婷	辽宁大学信息学院	3	8	2.0	2.0
4	李正道	辽宁大学信息学院	1	5	1.0	1.0