您现在的位置是：首页 > 技术资料 > 基于改进哈夫曼编码的大规模动态图可达查询方法

推荐星级：

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

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

资料介绍

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

部分文件列表

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

立即下载

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

部分页面预览

（完整内容请下载后查看）

Vol． 45 No． 2

Feb． 2017

第

期

电

子

学

报

2017

ACTA ELECTRONICA SINICA

年

月

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

，，，

丁琳琳李正道纪婉婷宋宝燕

(

，

辽宁大学信息学院辽宁沈阳

110036)

、，

随着社交网络分析生物信息网络分析等新兴应用的涌现和计算机技术的飞速发展图的规模迅速增

摘

要

，，．

长并且频繁更新使得对大规模动态图数据的处理需求愈加迫切现有的面向大规模动态图的可达查询研究成果较

，．

少尚存在索引压缩困难以及图结构待优化等问题本文提出了一种支持大规模动态图的基于改进哈夫曼编码的可达

( Huffman － based Label Reachability，HuffLR) ．

，

该方法首先对预处理图进行结构上的两次压缩得到双压

查询处理方法

; ，

缩图其次基于双压缩图提出一种前缀

label

， ; ，

索引该索引能够有效表达节点间的可达关系最后提出双压缩图的演

，、．，

进和可达查询处理及优化算法主要包括边的插入与删除节点的插入与删除实验表明本文提出的基于改进哈夫曼

．

编码的大规模动态图可达查询处理方法具有良好的可行性和有效性

;

关键词

中图分类号

URL: http: / /www． ejournal． org． cn

可达查询大规模图动态图哈夫曼编码标签索引

TP311

: 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

．

理需求愈加迫切可达查询作为图数据管理中的重要

引言

，

研究问题获得了广泛的关注一直是图数据管理领域

图数据能够有效描述现实生活中各类事物之间的

．，

的重点和热点研究问题目前关于大规模动态图可达

．、

复杂关系随着社交网络分析生物信息网络分析等新

，

查询处理的研究成果并不多往往通过索引实现可达

，

兴应用的涌现和计算机技术的飞速发展图的规模迅

，

查询但大都存在索引压缩困难以及图结构待优化等

，，

速增长并且频繁更新使得对大规模动态图数据的处

．

问题

: 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． 1

双压缩图

( 2) label

提出一种基于改进哈夫曼编码的前缀

索

3． 1． 1 DAG

压缩

，，

引及其优化能够有效表达节点间的可达关系大大减

定义初始图

( G = ( V ，E ) )

即可达查询的原

．

少了索引的存储空间

( 3)

， V

始图其中表示初始节点集

，E

．

表示初始边集

个节点组成的有向

为了有效支持大规模动态图中的节点与边的

1 ，

如图所示初始图

是由

，，

变化提出了双压缩图的演进和可达查询处理算法使

，

{ A，B，C} 、{ D，E，F，G} 、{ T，S，N，O，P}

图其中节点集

别形成了一个强连通子图由于强连通子图内所有节点

分

，

得在图数据频繁更新的过程中只需对部分数据进行

．

，

调整即可从而降低了查询复杂度

．

，

之间两两可达为了避免处理强连通子图内节点间的可

( 4)

在模拟数据集和真实数据集上进行了大量实

HuffLR

，

达查询本文运用强连通分量

( Strongly Connected Compo-

，

验验证了

方法在大规模动态图上实现可达查

nents，SCC)

DAG

．

的相关性质对初始图进行

SCC 1、2、3 G

分别替代中的

压缩如图

，

询处理的有效性和可行性且具有良好的查询效率和

，DAG

所示

压缩就是用

节点

．

较小的索引空间代价

{ A，B，C} 、{ D，E，F，G} 、{ T，S，N，O，P} ．

，

因此当查

节点集

全部评论(0)

暂无评论

评论赚积分>>

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

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

资料介绍

部分文件列表

部分页面预览

相关下载

全部评论(0)

热门标签

最新上传

热门下载

推荐下载

专栏首页