积分商城

最新搜索： C语言 经典程序 LED 逆变器资料 C语言算法 gl823k 高频变压器
您现在的位置是：首页 > 技术资料 > 基于改进哈夫曼编码的大规模动态图可达查询方法
推荐星级：
  • 1
  • 2
  • 3
  • 4
  • 5

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

更新时间：2019-12-24 08:33:47 大小：2M 上传用户：zhiyao6查看TA发布的资源 标签：哈夫曼编码 下载积分：1分 评价赚积分 （如何评价?） 打赏 收藏 评论(0) 举报

资料介绍

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


部分文件列表

文件名 大小
基于改进哈夫曼编码的大规模动态图可达查询方法.pdf 2M

【关注公众号立即送20积分】

部分页面预览

（完整内容请下载后查看）
2
Vol． 45 No． 2  
Feb． 2017  
第
期
电
子
学
报
2017  
2
ACTA ELECTRONICA SINICA  
年
月
基于改进哈夫曼编码的大规模动态图可达查询方法  
， ， ，  
丁琳琳 李正道 纪婉婷 宋宝燕  
(
，
辽宁大学信息学院 辽宁沈阳  
110036)  
:
、 ，  
随着社交网络分析 生物信息网络分析等新兴应用的涌现和计算机技术的飞速发展 图的规模迅速增  
摘
要
， ， ．  
长 并且频繁更新 使得对大规模动态图数据的处理需求愈加迫切 现有的面向大规模动态图的可达查询研究成果较  
， ．  
少 尚存在索引压缩困难以及图结构待优化等问题 本文提出了一种支持大规模动态图的基于改进哈夫曼编码的可达  
( Huffman － based Label Reachability，HuffLR) ．  
，
该方法首先对预处理图进行结构上的两次压缩 得到双压  
查询处理方法  
; ，  
缩图 其次 基于双压缩图提出一种前缀  
label  
， ; ，  
索引 该索引能够有效表达节点间的可达关系 最后 提出双压缩图的演  
， 、 ． ，  
进和可达查询处理及优化算法 主要包括边的插入与删除 节点的插入与删除 实验表明 本文提出的基于改进哈夫曼  
．
编码的大规模动态图可达查询处理方法具有良好的可行性和有效性  
:
;
;
;
;
关键词  
中图分类号  
URL: http: / /www． ejournal． org． cn  
可达查询 大规模图 动态图 哈夫曼编码 标签索引  
:
TP311  
:
A
: 0372-2112 ( 2017) 02-0359-09  
DOI: 10． 3969 /j． issn． 0372-2112． 2017． 02． 014  
文献标识码  
文章编号  
电子学报  
Reachability Query of Large Scale Dynamic  
Graph Based on Improved Huffman Coding  
DING Lin-lin，LI Zheng-dao，JI Wan-ting，SONG Bao-yan  
( School of Information，Liaoning University，Shenyang，Liaoning 110036，China)  
Abstract: With the emerging of applications such as Social Network Services and biological information network a-  
nalysis 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 struc-  
ture． Therefore，in this paper，we present a reachability query processing method of dynamic large scale graph based on im-  
proved 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．  
Key words: reachability query; large scale graph; dynamic graph; Huffman coding; label index  
．
理需求愈加迫切 可达查询作为图数据管理中的重要  
1
引言  
，
研究问题获得了广泛的关注 一直是图数据管理领域  
图数据能够有效描述现实生活中各类事物之间的  
． ，  
的重点和热点研究问题 目前 关于大规模动态图可达  
． 、  
复杂关系 随着社交网络分析 生物信息网络分析等新  
，
查询处理的研究成果并不多 往往通过索引实现可达  
，
兴应用的涌现和计算机技术的飞速发展 图的规模迅  
，
查询 但大都存在索引压缩困难以及图结构待优化等  
， ，  
速增长 并且频繁更新 使得对大规模动态图数据的处  
．
问题  
: 2015-09-06  
: 2015-12-22; :  
责任编辑 蓝红杰  
收稿日期  
修回日期  
:
基金项目 国家自然科学基金  
( No． 61472169，No． 61502215，No． 61572119，No． 61303016，No． 61472069，No． 11547235) ;  
辽宁省教育厅优秀人才项目  
( No． LR201017) ;  
( No． L2015193) ;  
辽宁省教育厅科学研究一般项目  
( No．201501127) ;  
辽宁省博士科研启动基金  
( No． LDQN201438)  
辽宁大学青年科研基金  
360  
2017  
年
电
子
学
报
，
针对上述问题 本文提出了支持大规模动态图的  
．
中大规模图的非受限查询动态索引  
HuffLR  
基于改 进 哈 夫 曼 编 码 的 可 达 查 询 处 理 方 法  
( Huffman － based Label Reachability，HuffLR) ．  
支持中小规模图的非受限查询动态索引大致分为  
Incremental  
、
算法 仅支持删除更新  
，
首先 对  
仅支持插入更新的  
Decremental  
Fully Dynamic  
， ;  
预处理的图进行结构上的两次压缩 得到双压缩图 其  
的
算法和全支持的  
算法三  
［13 ～ 15］  
． Fully Dynamic  
类
算法  
能够有效支持点和边的插  
，
次 为双压缩图构建前缀  
label  
，
可达索引 该索引能够有  
， ，  
入与删除更新 处理动态图的可达查询 但是存在索引  
; ，  
效表达节点间的可达关系 最后 为了有效支持大规模  
、
规模大 处理的图数据规模小等不足  
．
，
动态图中的节点与边变化 提出了双压缩图的演进和  
支持中大规模图的非受限查询动态索引目前的相  
，
可达查询处理及优化算法 主要包括边的插入与删除  
、
［16］  
．
关研究工作较少 以  
DAGGER  
，
算法为例 其通过  
Tar-  
．
节点的插入与删除等情况  
HuffLR  
［17］  
jan  
，
算法 来处理初始有向图并分配间隔标签索引 索  
本文提出的  
方法具有良好的可行性和有效  
O( n) ，  
能够支持边  
、
引空间复杂度与更新复杂度都为  
，
性 不必给节点分配多重  
label  
，
索引 既减少了存储空  
． ，  
节点的删除和插入更新操作 然而 此方法需要维持多  
，
间 又降低了  
label  
．
索引的初始化以及更新的复杂度 另  
，
、
，
．
重索引 索引的分配 构建相对复杂 索引更新效率低  
本文提出的支持大规模动态图的可达查询处理算  
HuffLR  
， ，  
外 该算法还对图和索引进行了高度的压缩 大大减少  
、 ．  
了存储空间 处理复杂度和查询处理时图的规模 本文  
，
对图和索引结构都进行了高度的压缩 大大  
法
:
的贡献点归纳如下  
( 1)  
、
减少了存储空间 算法处理复杂度和查询处理时图的  
，
提出双压缩图结构 首先运用  
DAG( Directed A-  
．
规模  
cyclic Graph，DAG)  
;
压缩方法对图进行第一次压缩 然后  
运用单链压缩方法对第一次压缩的结果进行单链压  
3
双压缩图及其索引  
，
缩 进而降低图的存储空间和查询处理时图的规模  
．
3． 1  
双压缩图  
( 2) label  
提出一种基于改进哈夫曼编码的前缀  
索
3． 1． 1 DAG  
压缩  
， ，  
引及其优化 能够有效表达节点间的可达关系 大大减  
i
i
i
1
定义 初始图  
( G = ( V ，E ) )  
即可达查询的原  
．
少了索引的存储空间  
( 3)  
i
i
， V  
始图 其中 表示初始节点集  
，E  
．
表示初始边集  
22  
个节点组成的有向  
为了有效支持大规模动态图中的节点与边的  
i
1 ，  
如图 所示 初始图  
G
是由  
， ，  
变化 提出了双压缩图的演进和可达查询处理算法 使  
，
{ A，B，C} 、{ D，E，F，G} 、{ T，S，N，O，P}  
图 其中节点集  
别形成了一个强连通子图 由于强连通子图内所有节点  
分
，
得在图数据频繁更新的过程中 只需对部分数据进行  
．
，
调整即可 从而降低了查询复杂度  
．
，
之间两两可达 为了避免处理强连通子图内节点间的可  
( 4)  
在模拟数据集和真实数据集上进行了大量实  
HuffLR  
，
达查询 本文运用强连通分量  
( Strongly Connected Compo-  
，
验 验证了  
方法在大规模动态图上实现可达查  
nents，SCC)  
DAG  
．
2
的相关性质对初始图进行  
SCC 1、2、3 G  
分别替代 中的  
压缩 如图  
，
询处理的有效性和可行性 且具有良好的查询效率和  
i
，DAG  
所示  
压缩就是用  
节点  
．
较小的索引空间代价  
{ A，B，C} 、{ D，E，F，G} 、{ T，S，N，O，P} ．  
，
因此 当查  
节点集  
?
2
相关工作  
B
N ( B  
是否可达 即  
N)  
，
时 只查询其分别  
询节点  
到
→  
?
，
关于图的可达查询 可分为针对静态图和动态图  
SCC  
( 1 3) ．  
节点的可达性即可 即  
→  
所属  
． ，  
两种 针对静态图的可达查询 目前已经取得了丰厚的  
．
研究成果 根据所处理的图数据的规模又可以将静态  
:
图的可达查询大致分为两类 一类是支持中小规模静  
［1］  
［2 ～ 5］  
，
态图的可达查询 如  
Optimal － tree 、Hop labeling  
、
［6］  
［7 ～ 10］  
Path － tree 、Interval labeling  
，
等 虽然其查询效率  
，
较高 却存在索引处理花费较大和难以有效处理大规  
．
模动态图等不足 另一类是支持大规模静态图的可达  
［11］  
， PWAH  
查询 如  
，
虽然支持大规模图上的可达查询处  
， ， ，  
理 但其索引压缩率低 不能有效处理动态图数据 查询  
．
效率较低  
，
针对动态图的可达查询的研究成果并不多 大多  
．
基于索引实现可达查询 根据索引的处理类型和图数  
［12］  
:
据规模大致可以分为两类  
支持中小规模图和支持  

相关下载

全部评论(0)

暂无评论
评论赚积分>>

上传资源 上传优质资源有赏金

热门标签

更多>>

最新上传

  • 打赏
  • 30日榜单

热门下载

推荐下载

本站上的所有资源均为源于网上收集或者由用户自行上传，仅供学习和研究使用，无任何商业目的，版权归原作如有侵权，请 来信指出，本站将立即改正。

ICP许可证号：京ICP证070360号     21IC电子网 2000- 版权所有

京ICP备11013301号

京公网安备 11010802024343号