检索结果-内蒙古大学图书馆

软件学报 2014年第9期25卷 1937-1952页

作者：张宇刘燕兵熊刚贾焰刘萍郭莉中国科学院信息工程研究所北京100093 中国科学院大学北京100049 国防科学技术大学计算机学院湖南长沙410073

对包含亿万个节点和边的图数据进行高效、紧凑的表示和压缩,是大规模图数据分析处理的基础.图数据压缩技术可以有效地降低图数据的存储空间,同时支持在压缩形式的图数据上进行快速访问.通过深入分析该技术的发展现状,将该技术分为基于... 详细信息

对包含亿万个节点和边的图数据进行高效、紧凑的表示和压缩,是大规模图数据分析处理的基础.图数据压缩技术可以有效地降低图数据的存储空间,同时支持在压缩形式的图数据上进行快速访问.通过深入分析该技术的发展现状,将该技术分为基于传统存储结构的压缩技术、网页图压缩技术、社交网络图压缩技术、面向特定查询的图压缩技术4类.分别对每类技术详细分析了其代表方法并比较了它们之间的性能差异.最后对该技术进行了总结和展望.

关键词：图数据管理空间缩减图数据压缩网页图社交网络

来源：评论

学校读者我要写书评

暂无评论

大规模图数据的压缩和查询研究

大规模图数据的压缩和查询研究

引用

作者：杨恩乙桂林电子科技大学

学位级别：硕士

对大规模图数据的紧凑存储,能够有效的解决图数据的增长速度快导致的数据量过大问题。随着互联网络的发展和图数据在各个领域的应用,传统的图数据存储方式已经不能支持大规模图数据的存储和操作。如何有效紧凑的表示大规模图数据并且在... 详细信息

对大规模图数据的紧凑存储,能够有效的解决图数据的增长速度快导致的数据量过大问题。随着互联网络的发展和图数据在各个领域的应用,传统的图数据存储方式已经不能支持大规模图数据的存储和操作。如何有效紧凑的表示大规模图数据并且在表示的基础上支持图的基本操作,不论是对大规模图数据的管理而言,还是基于大规模图数据做数据分析和知识推理,都是一项值得研究的工作。k2-tree和k2-BDC能够对大规模图数据的邻接矩阵进行紧凑的表示,但仍然不能充分的压缩邻接矩阵中的0单元。为此,本文在k2-tree和k2-BDC的研究基础上,将聚类技术引入到大规模图数据的紧凑表示中,较好的达到了空间/时间均衡,本文的主要内容和研究成果如下:（1）综述了目前大规模图数据紧凑表示的相关经典算法,包括基于邻接矩阵的大规模图数据压缩技术,基于邻接表的大规模图数据压缩技术,基于符号计算的大规模图数据压缩技术,分析了三类算法的核心思想和适用领域。（2）针对k2-tree和k2-BDC存在的问题,提出了一种新的基于聚类和k2-tree的大规模图数据紧凑表示方法——k2-tree-cluster,该方法在k2-tree和k2-BDC的基础上进行优化和改进,利用网页图和社交网络图的邻接矩阵的分布规律,使用聚类算法来充分的发现该矩阵中的稠密块,然后用k2-tree紧凑表示稠密块,来实现更加紧凑的目的。在真实数据集上Enron,EU-2005,CNR-2000进行实验,实验结果表明k2-tree-cluster的压缩效果优于k2-tree和k2-BDC。（3）在k2-tree-cluster紧凑表示大规模图数据的基础上,给出了k2-tree-cluster的顶点邻居查询算法,包括顶点的直接邻居查询算法和顶点的反向邻居查询算法。并且对该算法进行了实验验证。在真实数据集上Enron,EU-2005,CNR-2000进行实验,实验结果表明k2-tree-cluster的顶点邻居查询时间优于k2-tree和k2-BDC。

关键词： k2-tree 聚类图数据压缩 k2-tree-cluster

来源：评论

学校读者我要写书评

暂无评论

基于符号计算的最大公共子图匹配的研究

基于符号计算的最大公共子图匹配的研究

引用

作者：冷贝贝桂林电子科技大学

学位级别：硕士

在实际应用中，外部噪音数据的存在导致子图精确匹配不能令用户的模糊查找得到满意的结果。当在目标图中查询不到匹配图时，用户就会考虑寻找目标图和匹配图之间的最大公共子图。随着图数据规模的日益增大，使得大图的匹配查询问题面临... 详细信息

在实际应用中，外部噪音数据的存在导致子图精确匹配不能令用户的模糊查找得到满意的结果。当在目标图中查询不到匹配图时，用户就会考虑寻找目标图和匹配图之间的最大公共子图。随着图数据规模的日益增大，使得大图的匹配查询问题面临挑战。为了提高最大公共子图匹配的查询效率，本文基于图数据压缩的思想，引入多值决策图(Multi-valued Decision Diagram，MDD)对最大公共子图匹配查询问题进行研究。本文的主要贡献如下:　　（1）针对无标签无向图的最大公共连通子图匹配问题，提出一种新的算法 k2-MDD-MCCIS，并给出该算法的构造过程，即分别对目标图T和匹配图P的顶点进行二进制编码，根据顶点的编码对边进行编码，通过边的编码集合构建k2-MDDT和k2-MDDP，结合k2-MDD的邻边查询操作求出目标图与匹配图中每个顶点的度，选取度最大的顶点进行匹配，将匹配过的顶点的度置0，并把与之相邻的顶点的度减1，每匹配一对顶点后，都需要更新顶点的度，依次进行上述操作，即可实现最大公共连通子图匹配的求解问题。在构造k2-MDDT和k2-MDDP的过程中，根据MDD的化简规则将k2-tree中的同构子树进行合并,用k2-MDD结构存储图数据，使图数据的存储更加紧凑。　　（2）选取IJCAI2017公开数据集mcsplain instances进行实验，实验结果表明， k2-MDD-MCCIS 算法在储存性能上，所需存储的总顶点数仅为采用邻接矩阵方法的0.065%，为邻接表的55.7%;在查询时间上，随着顶点数量的增加，其查询时间始终维持在一个常数级别，并且在查询时间上优于McsPlit算法。　　（3）针对带标签有向图的最大公共子图匹配问题，分析现有的基于带标签有向图的最大公共子图匹配方法，将原始的最大公共子图匹配问题转化为多值决策图的布尔逻辑运算，提出一种新的匹配查询算法：L-k2-MDD-MCS，该算法将原始的目标图T用k2-MDDT结构表示，对匹配图P中顶点的标签进行筛选，选出匹配图P中顶点的标签值与目标图 T 中顶点的标签值相等的顶点，并将匹配图中这些顶点的标号改成其在目标图中与之对应的顶点的标号;对新的匹配图Q构建k2-MDDQ，将k2-MDDT和新的 k2-MDDQ进行逻辑“交”操作即可求得最大公共子图。最后以公开数据集mcs33ved instances为例进行实验，证明该算法的正确性。

关键词：最大公共子图图数据压缩多值决策图符号计算邻接矩阵

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：