检索结果-南通市图书馆

检索条件"主题词=动态图匹配"

共 3 条记录，以下是1-10 订阅

全选清除本页清除全部题录导出标记到"检索档案"

详细简洁

排序：

基于增量的动态图匹配算法研究

基于增量的动态图匹配算法研究

引用

作者：张芳燕山大学

学位级别：硕士

随着大数据时代的到来,在网络分析领域中积攒了大量以图结构存储的数据,且蕴含了丰富的具有实用价值的信息,因此分析和挖掘有用信息的图匹配技术应运而生。当数据规模越来越大,基于快照模式的动态图匹配算法在数据更新频繁时,存在大量... 详细信息

随着大数据时代的到来,在网络分析领域中积攒了大量以图结构存储的数据,且蕴含了丰富的具有实用价值的信息,因此分析和挖掘有用信息的图匹配技术应运而生。当数据规模越来越大,基于快照模式的动态图匹配算法在数据更新频繁时,存在大量的冗余计算,导致算法匹配的时间复杂度过高。针对以上问题,展开了如下研究:首先,针对大规模查询图分解后无法确定多个查询子图优先级,造成匹配时存在冗余计算的问题,根据查询图节点度大小采用核心-森林-叶子分解策略得到多个子图,考虑每个子图之间公共边的数量及平均度的大小,确定查询子图优先级顺序,采用路径搜索的方法,给出了查询图节点的匹配顺序。其次,针对数据图规模较大造成内存消耗高的问题,通过生成查询图宽度优先搜索树,按自顶向下的匹配策略,将数据图节点以嵌入的方式存储到查询节点候选集,为查询图构建压缩路径索引模型。并根据查询图非树边的性质,为查询节点定义两类索引结构。再次,针对在大规模数据图上动态图匹配算法时间复杂度高的问题,利用添加节点及其邻居节点满足的查询节点索引结构的类型,删除索引没有更新的节点。在节点索引更新的区域内进行匹配,将前一次的匹配结果集更新,最终得到新的匹配结果集以及更新后的查询节点索引,并用于后续的增量匹配。最后,在不同规模的数据集上对上述算法的时间效率进行了验证和分析。

关键词：动态图匹配图分解压缩路径索引模型影响区域增量计算

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于增量的动态图模式匹配符号算法研究

基于增量的动态图模式匹配符号算法研究

引用

作者：许昌胜桂林电子科技大学

学位级别：硕士

图作为一种可以描述事物之间关系的数据结构,在现实生活中应用广泛。子图匹配问题是图数据分析研究中的基本课题,有着十分重要的研究价值。但随着数据规模越来越大并且伴随实时变化,基于快照模式的动态图匹配算法无法满足实时响应的要... 详细信息

图作为一种可以描述事物之间关系的数据结构,在现实生活中应用广泛。子图匹配问题是图数据分析研究中的基本课题,有着十分重要的研究价值。但随着数据规模越来越大并且伴随实时变化,基于快照模式的动态图匹配算法无法满足实时响应的要求。基于辅助索引结构的动态图匹配算法能够在数据图发生变化时基于辅助结构的信息进行局部更新,获得比快照模式更快的求解效率。我们从两个方面对现有的动态图匹配技术进行优化,一方面优化辅助结构的候选集存储,通过为辅助结构添加更多的约束来优化辅助结构的存储空间,另一方面引入新的压缩技术,其中代数决策图是一种存储紧凑且易于操作的隐式存储结构,可以在相对较小的存储空间内实现大规模图的运算。本文引入代数决策图技术研究了动态图匹配符号算法以及考虑邻域约束解决现有算法中存在的信息冗余问题。主要研究成果和结论如下:(1)针对现有的动态图匹配算法数据图规模庞大,求解过程产生大量的内存消耗的问题,本文引入了代数决策图(Algebraic decision diagram,ADD)结构作为数据的表示方式,实现数据查询与更新的并行运算以及公共子图的共享存储,有效平衡了算法的空间和时间效率。(2)针对(1)中随着数据规模的快速增长,基于增量的有界模拟图匹配算法在更新过程中存在大量的重复计算,以及通过逐点扩展的方式确认受影响区域时的算法效率低下问题,本文基于ADD提出了一种新的编码方式来构建辅助索引结构ADD Index(AIndex),该辅助结构不仅可以压缩存储节点间的路径信息,同时可以利用ADD并行操作的特性,实现快速查找和维护;其次为了增量维护辅助结构和匹配结果,提出了适用于AIndex的增量更新算法。实验表明,与经典算法相比,优化了存储空间,求解性能有了明显提升。(3)为了降低动态子图匹配候选集空间和提高算法效率,针对目前最先进的增量子图同构匹配算法Symbi中的索引结构动态候选空间(Dynamic Candidate Space,DCS)中存在的信息冗余问题,引入邻域信息约束,提出了一种新的索引结构ZDCS,并提出了ZDCS的更新算法INCZDCS来动态维护ZDCS索引结构和匹配结果,进一步提出了动态图的增量子图匹配算法ZSymbi。最后,在真实数据集上与Symbi算法进行实验对比,结果表明ZSymbi有效缩减了计算空间并提高了算法的求解效率。

关键词：动态图匹配代数决策图符号技术邻域约束 ZSymbi

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于最小连通支配子图的图匹配算法

基于最小连通支配子图的图匹配算法

引用

作者：韩冰大连海事大学

学位级别：硕士

图匹配问题本质上是一个图同构问题。给定一个查询图和数据图,图匹配问题是在数据图中求解所有同构于查询图的数据子图的过程。图匹配问题依据数据图结构是否随时间发生变化,分为静态图匹配和动态图匹配。随着现实世界中图规模不断增大... 详细信息

图匹配问题本质上是一个图同构问题。给定一个查询图和数据图,图匹配问题是在数据图中求解所有同构于查询图的数据子图的过程。图匹配问题依据数据图结构是否随时间发生变化,分为静态图匹配和动态图匹配。随着现实世界中图规模不断增大,图匹配算法的效率愈呈现指数爆炸的增长,因此图匹配优化方法成为当前研究的热点。除此之外,随着这些领域的迅速发展,描述实体对象间关系图的结构会随着其发展而更新,目前已有动态图匹配方法存在存储代价和动态更新代价过高的问题。针对上述问题,本文通过对比当前主流的静态图匹配以及动态图匹配算法的优缺点,经过理论研究与实验论证,提出了适用于大规模查询图的静态图匹配优化方法与动态图匹配方法。本课题研究期间的主要工作如下:首先,本文介绍了当前主流的静态图匹配算法以及动态图匹配算法。通过进行大量实验分析,指出了当前主流方法中存在的缺陷;然后,通过分析查询图的结构与图匹配过程中的空间复杂度,结合最小连通支配集,提出了k查询节点路径,降低查询图中待匹配节点数,减小了图匹配过程迭代次数;提出了代价模型,在图匹配之前,为查询节点构造最优匹配顺序,优先匹配辨别程度高的节点,降低了后续节点候选集大小;根据查询图节点间的支配关系,针对查询图中被支配节点,提出有效剪枝规则,再次过滤假阳性候选集,得到最终结果集;考虑到在数据图发生改变时,传统静态图匹配算法无法满足动态图实时性,通过分析数据图更新部分与更新前后结果集的变化,对数据图节点分类,提出了基于映射-候选集-标签集的索引（MCL）以及层次路径索引（HP）,避免了动态图匹配过程中大量的冗余计算。在数据图更新时,根据查询节点序列,缩小索引更新范围,采用增量式更新方式,仅更新局部索引,降低了重建索引的开销;最后对于动态图匹配过程与最小连通支配子图相结合,提高了动态图匹配效率。

关键词：图静态图匹配动态图匹配最小连通支配子图层次路径索弓

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

全选清除本页清除全部题录导出标记到“检索档案”

共1页 << < 1 > >>

回到顶部

执行限定条件

欢迎您,

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

在线全文

请选择保存的检索档案：

请选择收藏分类：

通借通还

欢迎您,

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

在线全文

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：