图数据压缩技术综述

应用合适的压缩技术对包含上亿个节点和边的图数据进行紧凑准确的表示和存储是对大规模图数据进行分析和操作的前提。紧凑的图数据表示不仅可以降低图数据的存储空间,而且还可以支持在图数据上的高效操作。从图数据的存储角度出发对图数据管理中关于图数据压缩技术的研究进展进行综述,将重点介绍以下3种压缩技术:基于邻接矩阵的图数据压缩技术、基于邻接表的图数据压缩技术和基于形式化方法的图数据压缩技术,以及相关的代表性算法、适用范围和优缺点。最后对图数据压缩技术的现状和面临的问题进行了总结,并给出了未来图数据压缩技术的发展趋势。     

大规模图数据匹配技术综述

在大数据时代海量的多源异构数据间存在着紧密的关联性,图作为表示数据之间关系的基本结构在社交网络分析、社会安全分析、生物数据分析等领域有着广泛应用.在大规模图数据上进行高效地查询、匹配是大数据分析处理的基础问题.从应用角度对用于图查询的图数据匹配技术的研究进展进行综述,根据图数据的不同特征以及应用的不同需求对图匹配问题分类进行介绍.同时,将重点介绍精确图匹配,包括无索引的匹配和基于索引的匹配,以及相关的关键技术、主要算法、性能评价等进行了介绍、测试和分析.最后对图匹配技术的应用现状和面临的问题进行了总结,并对该技术的未来发展趋势进行了展望.     

基于包含度的子图匹配方法

子图匹配是图论中最基本的操作.研究子图匹配的一个变种,即：在一个节点拥有若干元素的大图数据库中,找到与给定查询图结构同构并且对应节点元素的加权集合包含度大于给定值的所有子图,称作基于包含度的子图匹配（subgraph matching with inclusion degree,简称SMID）.该查询能够应用于多种场景,包括论文检索、社区发现、企业招聘等.为高效实现SMID,设计了同时包含节点元素和图结构信息的数据签名与查询签名,在离线处理阶段,利用数据签名为数据图建立动态签名树（DS-Tree）,以加快在线处理时图节点的匹配过程.为解决DS-Tree占用空间大的问题,设计了一种DS-Tree压缩方法,在对查询效率影响不大的情况下减小了索引空间.为进一步加快查询效率,还提出了支配子图查询算法.在真实数据和人工数据上的实验结果表明,所提出的方法在效率和扩展性方面优于现有其他方法.     

GCPR:一种在MapReduce平台上基于图划分的PageRank加速方法

随着应用的扩展,大规模图数据不断涌现,如何对拥有大量结点的图进行分析成为研究者关注的焦点问题之一.结点的海量性与分析的复杂性使得图分析任务需要借助MapReduce平台多机并行完成.在该平台上,现有的PageRank算法每轮迭代都须扫描、传输所有网页的完整状态,I/O和网络传输的开销严重影响了计算效率.为此,本文提出一种在MapReduce平台上基于图划分的PageRank加速方法:GCPR(Graph-clustering PageRank).GCPR利用图划分、数据两层压缩技术在MapReduce平台上进行PageRank迭代计算,不仅减少了Map到Reduce中间阶段I/O和网络传输的开销(MapReduce运算的主要瓶颈之一),而且平衡了计算资源.实验证明GCPR能极大提升MapReduce平台上的PageRank计算效率.     

基于最小描述长度原则的属性图概要方法

图概要技术是管理、分析和可视化大规模图的关键技术之一。如何综合结构和属性信息进行图概要是一个挑战。大部分现有的图概要方法或者只考虑结构或属性某一方面的信息,或者要求属性的表现形式是一致的。结合信息论中最小描述长度原则,对属性图概要问题建模,将其转化为求解最小表示代价问题,以实现图压缩和图概要的双重目标。提出了一种计算节点属性相似性的方法,该属性度量方法对节点属性的限制较小,并且将节点间的相似性统一为存储代价,实现了节点结构相似和属性相似的协同考虑。提出了两种求解最小代价表示的图概要算法。在真实和合成的数据集上实验,验证了提出算法的有效性。     

基于K-sup稠密子图的大规模复杂网络概要算法及可视化

现实社会存在大量复杂网络,随着大数据时代的来临,复杂网络数据规模不断扩大,难以进行算法分析和可视化展示.针对复杂网络小世界、无标度特性,提出基于K-sup稠密子图的复杂网络概要算法,利用三角形在网络中的同质性和传递性发现复杂网络中的稠密子图,结合模块度最大化,将子图中相似的节点归并为超点;运用分层结构存储概要图,并进行可视化显示.该算法能对大规模复杂网络进行有效压缩,保持原网络的性质.在5个真实数据集上进行对比实验,显示出该算法在压缩率、幂率性和平均聚类系数的保持等指标优于已有算法,同时在大规模数据下具有保持网络拓扑结构且支持概要图分层可视化的优点.     

一种新的高效图聚集算法

图聚集是将一个大规模的图用简洁的并能有效反映原始图的结构和属性信息的小规模图来表示的技术.图聚集在图数据管理、分析和可视化中发挥着重要作用.图聚集方面现有研究结果还很少,也很不系统.其主要不足之处是:1)算法依赖于具体应用;2)算法仅考虑了图的某方面信息,如结构信息或属性信息;3)算法对用户提供的交互和反馈信息的约束很强.针对现有图聚集算法存在的主要不足,提出一种有向图新型图聚集算法,该算法采用一种新的聚集图质量函数,全面刻画了聚集图多样性、覆盖性、简洁性和实用性.该算法使用LSH(locality sensitive Hashing)技术和基于熵的划分技术,保证了聚集图的质量.在真实数据集上进行了大量的实验,验证了算法的有效性.     

基于节点相似性分组与图压缩的图摘要算法

方法压缩率较高，图压缩算法无法直接被用于下游任务分析的问题，提出一种图摘要与图压缩的融合算法，即基于节点相似性分组与图压缩的图摘要算法（GSNSC）。首先，初始化节点为超节点，并根据相似度对超节点分组；其次，将每个组的超节点合并，直到达到指定次数或指定节点数；再次，在超节点之间添加超边和校正边以恢复原始图；最后，对于图压缩部分，判断对每个超节点的邻接边压缩和摘要的代价，并选择二者中代价较小的执行。在Web-NotreDame、Web-Google和Web-Berkstan等6个数据集上进行了图压缩率和图查询实验。实验结果表明，在6个数据集上，与SLUGGER(Scalable Lossless sUmmarization of Graphs with HiERarchy)算法相比，所提算法的压缩率至少降低了23个百分点；与SWeG(Summarization of Web-scale Graphs)算法相比，所提算法的压缩率至少降低了13个百分点；在Web-NotreDame数据集上，所提算法的度误差比SWeG降低了41.6%。以上验证了所提算法具有更好的图压缩率和图查询准确度。     

基于深度学习的图异常检测技术综述

图异常检测旨在大图或海量图数据库中寻找"陌生"或"不寻常"模式,具有广泛的应用场景.深度学习可以从数据中学习隐含的规律,在提取数据中潜在复杂模式方面表现出优越的性能.近年来随着基于深度神经网络的图表示学习取得显著进展,如何利用深度学习方法进行图异常检测引起了学术界和产业界的广泛关注.尽管最近一系列研究从图的角度对异常检测技术进行了调研,但是缺少对深度学习技术下的图异常检测技术的关注.首先给出了静态图和动态图上各类常见的异常定义,然后调研了基于深度神经网络的图表示学习方法,接着从静态图和动态图的角度出发,梳理了基于深度学习的图异常检测的研究现状,并总结了图异常检测的应用场景和相关数据集,最后讨论了图异常检测技术目前面临的挑战和未来的研究方向.     

柔性制造系统中生产调度问题的零压缩二叉决策图算法

针对赋时有界Petri网模型下柔性制造系统的生产调度问题,给出了有界Petri网的零压缩二叉决策图表示方法,进而建立了此类生产调度问题求解的符号零压缩二叉决策图算法.该算法在求解过程中对状态空间及其搜索过程中的相关数据,采用零压缩二叉决策图表示,避免了状态和搜索的显式枚举,实现了隐式高效操作,有效地改善了算法的计算性能.实验结果表明了算法的有效性.     

Linux下高效存储优化的研究

随着数据的指数性增长,存储技术成为信息产业发展的核心动力,存储系统在一定程度上比计算系统和通信系统更加重要。如何高效地存储和优化存储空间,是存储系统急需解决的问题。本文介绍高效存储技术中的RAID技术、重复数据删除技术、数据压缩技术等,并在Linux环境下设计与实现具有高效存储优化特点的应用程序。试验表明该应用程序实现了软件RAID,删除了重复性数据,提高了存储空间利用率,降低了存储能耗。     

煤矿安全监控系统历史数据存储压缩算法研究

通过深入分析煤矿安全监控系统中历史数据对象及监测参数的特点,提出了基于误差带的历史数据存储压缩算法,详细分析了该算法的性能,并通过Matlab进行了仿真,结果令人满意。     

基于三层存储模型的RFID数据压缩存储方法

针对物联网技术中亟待解决的海量数据存储问题,提出了一种基于射频识别(RFID)的三层数据存储压缩模型。该模型将数据分为当前数据层、临时数据层和历史数据层,利用每一层中数据的特点分别设计了相应的数据汇总算法,最终实现RFID数据的压缩存储。在该模型的基础之上,提出了针对路径的编码算法,用于对路径进行压缩存储。实验结果表明,该三层存储模型可以有效地压缩存储RFID数据,同时数据汇总算法具有较低的时间复杂度与较高的数据压缩比。     

基于大数据时代的数据可视化应用分析

如今随着数据采集、存储和数据分析技术飞速发展,大幅度降低了数据储存和处理的成本,我们即将步入一个大数据时代。大数据时代的改革将海量数据处理变为可能,而且大幅降低了处理成本,促使越来越多跨专业学科的人才投入到大数据的开发应用中来。如何才能让大型数据集变得简单和易于理解,可视化无疑是最有效的途径。对大数据背景下的数据可视化应用展开研究,将有助于我们发展和创新数据可视化技术。     

查询感知的关系-图数据库自适应存储技术研究

在大数据时代,针对不同场景下如何保持数据高效查询受到持续关注,但是对通过改进数据的存储管理技术来提高查询效率还有待进一步研究。因此,结合图数据结构类型多变、应用场景丰富、数据集价值高等优势,提出了一种利用关系-图数据模型协同存储数据的模式,并设计了用户查询感知的自适应存储优化技术来解决多数据模型的数据存储冗余优化问题。通过分析不同引擎处理不同的查询得出每种引擎对应的不同查询性能和多数据模型存储存在的数据冗余问题,提出用户查询感知的自适应存储技术。再结合用户历史查询及查询特点,利用基于启发式规则的优化算法完成多数据模型的数据存储优化。     

多种存储环境下压缩数据库的缓存优化

近年来,各行业数据量增速提升,对承担数据存储任务的数据库系统进行性能优化的需求也越来越强烈。利用关系型数据库I/O密集型、服务器CPU相对空闲的特点,在数据库中引入数据压缩技术,节省了数据存储空间和I/O传输带宽。但当今主流数据库系统的压缩技术都是针对传统的存储和运行环境设计,并未考虑固态硬盘（SSD）等新型存储设备和云数据库等虚拟化运行环境对系统性能的影响,因此,以数据库压缩系统在不同存储环境的缓存优化作为切入点,对系统整体性能的影响进行分析,给出了数据库压缩系统性能的分析模型,并以MySQL为例进行具体分析,给出了对应的缓存优化措施。在内核虚拟机（KVM）和MySQL数据库测试平台上的性能评估结果表明,所提出的优化方法使得系统性能最高有超过40%的提升,在某些配置下获得了优于物理机的性能。     

历史数据实时压缩方法研究

在开发实时数据库中,对历史数据的存储和管理非常重要,由于大量的数据存储,需要高效的历史数据压缩算法。文章基于均方误差的设计思想,提出了一种新的历史数据压缩算法、给出其详细步骤,并和OSI软件公司开发的旋转门算法进行比较。仿真结果表明,该文提出的新压缩算法具有更高的数据压缩率,降低了测量误差对数据压缩影响。     

多算法融合比较的图像文件索引压缩

近年来由于科技的发展和互联网的兴起,图像资料已被广泛地应用在网络上,而图像压缩不但可以节省图像资料占用的内存空间,并且可以加速其传输速度,因此图像压缩技术目前被广泛应用于医学、手机、数据传输、多媒体影音、互联网络等。这里主要是针对无失真的图像压缩技术,先将原始图像转成256色的GIF格式,然后再建立一个索引矩阵,矩阵中元素是由原色RGB信息对应所组成,利用索引矩阵排序法并配合编码簿,再加上配合LZW、CALIC、JPEG2000、JPEG-LS等不同压缩算法,来比较压缩的效果。     

基于HDFS的数据备份系统的设计与实现

文章将云存储技术应用于数据备份,设计并实现了基于分布式文件系统HDFS的数据备份系统。该系统利用云存储技术,构建廉价、可扩展的分布式集群,解决了用户数据备份／恢复的需求,通过合并压缩、加密等技术进一步提高了系统性能和安全。实验表明,该系统在安全性、可扩展性、经济性上有一定的优势。