支持查询的大规模图数据无损压缩

发布时间：2017-12-24 04:03

  本文关键词：支持查询的大规模图数据无损压缩　出处：《华东师范大学》2017年博士论文　论文类型：学位论文

  更多相关文章： 图数据 图数据流 无损压缩 图数据查询 三角形列表

【摘要】：图数据模型,简称图数据,是表示实体和实体间联系的数据模型。和结构化的关系模型数据以及非结构化数据相比,图数据表达形式多样、灵活,且易于实现。随着互联网技术和各种数据收集和传输技术的发展,越来越多的数据以图的形式建模,以表示互联网中不同结点、不同用户、不同实体之间的联系。同时,搜索引擎、社交网络服务、科学数据分析、知识图谱分析等应用中所需要管理的图数据规模也越来越大。而目前大部分图数据处理算法往往需要将整个数据集存放在内存进行分析。所以,如何减少图数据处理的所需要存储空间容量是图数据管理的重要问题,而图数据压缩是解决这一问题的主要手段之一。图数据压缩不仅需要考虑压缩率,即压缩后数据与原始数据规模的比值,还需要考虑压缩方法的运行效率。另一方面,在对压缩后的数据进行处理时,如何避免不必要的解压缩操作,支持各类图数据查询,提升图数据处理效率,也至关重要。针对以上问题,本文研究支持查询的大规模图数据的无损压缩方法。具体而言,本文的贡献包括以下三点:·提出了一种基于三角形列表的静态图数据无损压缩方法,bound-tri方法。此方法利用图数据中大量存在的三角形子图,合并这些三角形子图中的公共结点,对图数据进行无损压缩。bound-tri方法在三角形列表的过程中过滤了图数据中度较高的一批结点,使得需要压缩的图数据的规模减少,从而降低图数据的压缩时间。同时,bound-tri方法还确保了在三角形列表的结果中只冗余较少的边,并得到一个压缩率较高的压缩结果。bound-tri方法还允许用户在压缩时设置不同的结点度过滤参数来平衡图数据压缩的压缩率、压缩时间,以及压缩结果对反馈图数据查询的效率。本文所介绍的bound-tri方法可以对大规模图数据,尤其是社交网络图,实现高效率的无损压缩。此方法相较大部分已有的图数据无损压缩方法有着较高的压缩率和较短的压缩时间。·提出了一种针对图数据流形式逐步生成的图数据的无损压缩方法,STT方法。STT方法利用图数据流中在短时间内多次输人的结点以及连接这些结点的边,对图数据流进行无损压缩。STT方法在限定大小的缓存中尽可能地使高热度结点以及包含有这些结点的边或三角形集合存活,并在缓存中利用三角形列表算法尽可能多地将图数据流中的三角形子图组成三角形集合,实现了较高的压缩率以及较高的数据流吞吐量。同时,在图数据流的压缩结果中存在一定数量的三角形集合,这可以满足对图数据查询的无解压快速反馈需求。并使相邻时间段内输入的结点尽可能地被包含在一个或极少数个不同的三角形集合中。STT方法在压缩时无需输入完整的图数据拓扑结构或全部图数据内容信息。同样地,用户可以通过参数调整缓存更新的更新效率,对不同速率的图数据流进行压缩,或是通过降低一部分的图数据的压缩率,提高图数据流压缩的吞吐量。STT方法相较目前的静态图数据压缩方法,可以得到与RVE、Re-Pair和VNM等经典的图数据压缩方法近似压缩率的图数据压缩结果,却可以在图数据逐步到达时即开始压缩操作,极大地提升了压缩效率。·提出了在已压缩图数据结果中执行邻接结点查询、k-距离结点查询、共同邻接结点查询这三类基本查询的处理算法。这些算法都保证了不需要对基于三角形子图进行压缩的图数据进行解压缩即可返回查询结果。经bound-tri方法和STT方法压缩得到的图数据中包含大量的三角形子图,且这些子图可以被直接地提取出来,利用这些三角形子图中相互连接的结点以及结点间的边,能实现无需解压的查询反馈。从而在获得容量较小的图数据压缩结果的同时,避免了昂贵的解压缩操作。基于这些算法,可以实现社交网络数据抽样、用户推荐、谣言传播分析等图数据分析任务。目前,经大部分图数据压缩方法压缩得到的图数据,如SLAHSHBURN、BV框架及κκ2-partitioned等方法,均需要在反馈查询时部分或完全地解压图数据。综上所述,本文从图数据压缩问题出发,在静态图数据及图数据流这两类环境中分别对大规模图数据中进行无损压缩的问题进行了研究分析。本文图数据中大量存在的三角形子图并利用结点合并的方法,实现高效的图数据压缩。在静态图数据环境中,在压缩过程中过滤度较高的结点并对其余结点进行了三角形列表计算,实现了较高的压缩率以及较短的压缩时间。在图数据流的环境中,则在数据流缓存中保持高热度结点的存活时间,从图数据流中列出更多的三角形子图,在图数据存储到本地存储空间前,实现对图数据的压缩。另外,本文还研究了在已压缩的图数据中的查询处理算法,证明了基于三角形子图压缩的图数据,如经bound-tri方法和STT方法压缩的图数据,可以在无需解压缩的情况下对几类常用的图数据查询快速返回查询结果。对多个真实的大规模图数据集的压缩实验以及和同类方法的对比表明,本文所提出的方法在压缩率、压缩效率(压缩时间或数据流压缩吞吐量),查询支持这三个方面,具有整体性优势。
【学位授予单位】：华东师范大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：TP311.13

【相似文献】

相关期刊论文 前10条

1 吴国清;陈虹;;一种科学数据无损压缩方法[J];计算机工程与应用;2006年05期

2 沈兰荪,魏海;图像的无损压缩研究[J];数据采集与处理;1999年04期

3 毋清明;;迎战!无损压缩挑战极限![J];电脑爱好者;2006年11期

4 李平,李伟光;医学图像视觉无损压缩的研究[J];长春理工大学学报;2005年03期

5 黄祥林;杨丽芳;;一种提高图像无损压缩效率的方法[J];电路与系统学报;2007年03期

6 刘方;一种数据无损压缩技术的研究[J];南京航空航天大学学报;1995年06期

7 王军;;基于谱间和帧内差分脉冲编码调制的超光谱图像无损压缩[J];中国光学;2013年06期

8 api;纤尘去尽还本真——无损压缩音频格式巡礼(下)[J];电脑;2004年11期

9 孙自广;古天龙;;一种基于代数决策图的多值图像无损压缩方法[J];桂林电子工业学院学报;2006年02期

10 李龙;周顽;;数字图像无损压缩[J];软件导刊;2007年07期

相关会议论文 前6条

1 陈虹;宋磊;吴国清;;大规模数值模拟数据的无损压缩[A];中国工程物理研究院科技年报（2005）[C];2005年

2 赵国毅;杨晓春;王斌;;面向相似数据的无损压缩技术[A];NDBC2010第27届中国数据库学术会议论文集A辑二[C];2010年

3 陈蕴智;舒忠;;报业网络版数据无损压缩安全传输系统[A];第十三届全国包装工程学术会议论文集[C];2010年

4 王振海;;基于DSP的高速数据流无损压缩方法的研究[A];2007通信理论与技术新发展——第十二届全国青年通信学术会议论文集（下册）[C];2007年

5 颜彦;郭兴明;李立策;王景灿;;基于LZ77压缩算法的ECG信号无损压缩在DSP上的实现[A];中国生物医学工程进展——2007中国生物医学工程联合学术年会论文集（上册）[C];2007年

6 蒋宏;潘登;刘荻;孙志明;刘尔梅;;哈尔滨医科大学第一临床医学院PACC系统一期工程总结[A];首届中国IT与医药卫生高层论坛论文集[C];2004年

相关重要报纸文章 前4条

1 湖南 古铜;无损压缩CD之APE[N];电脑报;2003年

2 李剑峰;影音不分家，无损音频知多少?[N];电脑报;2014年

3 通讯员聂小清;电话线就能当宽带用[N];科技日报;2002年

4 李霞;加快多媒体系统的研究与发展[N];甘肃日报;2003年

相关博士学位论文 前2条

1 张O，

本文编号：1326772