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

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

一种面向图包容搜索的图索引模型

由于图模型的广泛采用,图数据的快速包容搜索在许多不同领域广泛应用。给定一个模型图集D和一个查询图集q,传统的图搜索旨在检索所有包含q的图(qg),与此不同,包容搜索有其自身的索引特性,针对这些特性进行系统地研究,并提出一种基于对比子图的索引模型（csgIndex）：使用一个冗余感知特征选择过程,csgIndex能挑选出一个鲜明的具有区分力的对比子图集,并最大化其索引能力。对实时测试数据的实验结果显示,csgIndex对不同的包容搜索荷载能达到近优化修剪力,相较于传统图搜索方法表现出明显的索引性能优势。     

一种有效的量化交易数据相似性搜索方法

量化交易数据与一般交易数据的不同之处在于它在各个维上的值是数值型而不是二值型的。研究这种数据的有效的相似性搜索方法是一个重要而具有挑战性的课题,提出了一个新的相似性度量函数Hsim(),这个度量函数可以较好地克服Lp等传统的距离函数在高维空间中的缺点,并能将二值型和数值型数据距离的计算整合到一个统一的框架中去。结合量化交易数据的特点,构造了定义在该函数上的相似性索引结构,并对建立在该索引结构上的相似性查询方法进行了阐述。实验表明,这种搜索方法对量化交易数据的相似性搜索有较高的修剪率,能大大地加快搜索的速度。     

一种改进的群搜索优化方法

标准的群搜索优化(GSO)方法是一种适用于解决高维函数优化问题的群智能算法,且简单、高效,易于实现.为了进一步提高其收敛速度和精度,对该方法进行了改进.在保留其“发现者-追随者-游荡者”框架的同时,改进的GSO方法将最大下降方向策略引入发现者行为.在每轮迭代中,发现者不但按照自身方向进行搜索,同时也根据最大下降方向进行搜索.分别通过23个基准测试函数对2种优化方法进行测试,结果表明:改进的GSO方法优于标准群搜索方法.     

时序图上动态子图查询优化算法

挖掘时序图中的特定模式,能够有效地发现有价值的信息,并进行预测与决策支持,因此动态子图的查询及索引优化成为时序图研究的一个热点。研究了聚焦在动态子图的快速查询,着重探讨了索引优化,给出了查询模型的定义及基本查询算法。针对查询算法进行索引优化,提出了两种不同的建立索引的方法,波形索引及二叉树索引。为了验证索引的适用条件,设计了相应的实验,并使用随机数据集对实验程序进行测试,从时间消耗和空间占用的角度对两种索引的运行效率进行了验证分析。波形索引的优势在于存储结构简单,适用于边长度较长边数量不多的情况。二叉树索引的查询速度快,适用于边长度较短边数目较多的情况。     

一种研究图匹配问题的核方法

随着计算机技术与网络技术的高速发展,大量的数据充斥着我们周围的世界。面对这些复杂的海量数据,如何才能准确无误地对它们进行辨别与分析,这对于人们来说是一个非常具有挑战性的问题。在计算机领域,图是一种非常灵活的数据结构,对图等含有结构化信息数据的进行学习,是模式识别和机器学习领域的一种重要问题。该文主要研究了通过核方法来解决这些识别问题,并且实例化了两种特殊的解决图匹配的核方法。在此基础上,分析了其解决这类问题的算法复杂度。实验结果表明,该文所提出的方法是一种解决图匹配的非常有效技术。     

一种基于大数据的有效搜索方法

针对大数据查询效率低下的问题,提出了一种有效的搜索方法.将共享的历史查询结果作为中间结果集,在新的查询请求到达时,首先与历史查询进行匹配,若能实现匹配,则直接将匹配部分的历史查询结果直接作为新查询请求结果的一部分.这减少了大量的对历史查询的重复计算,节省了搜索时间,提高了查询效率.实验对比分析表明,新的基于大数据的查询方法能较好地提高查询效率.     

一种基于数据访问流的数据库索引优化方法

提出了一种基于数据访问流进行索引优化的方法,该方法通过集成业务流程模型与数据模型,抽取了流程活动中包含的数据访问操作和流程的控制结构形成数据访问流,分析了数据访问流中数据访问操作的频度,为频繁数据访问操作所对应的数据项创建索引,达到改善数据访问性能的目的。实验结果表明,该方法提高了数据查询的速度。     

基于非精确图匹配的CAD模型搜索方法

为了弥补现有的三维CAD模型搜索方法难以搜索到不同近似程度的相似模型的缺陷,提出一种基于面属性化邻接图非精确匹配的CAD模型搜索方法.首先提取CAD模型中的B-rep信息将CAD模型转化为面属性化邻接图;然后计算目标模型与被搜索模型的面属性化邻接图之间的顶点相容程度矩阵和边相容程度矩阵,并由此建立2个模型相似程度的度量作为选择不同顶点匹配矩阵M的优化目标函数;在对匹配矩阵M进行连续化松弛后,运用Sinkhorn行列交替规范化方法求解匹配优化问题.实验结果表明,采用该方法能够搜索到不同近似程度的相似模型;并且由于避免了具有NP复杂性的精确图匹配过程,检索效率也能满足实际要求.     

面向大规模图数据的分布式可达性索引与查询策略

针对构建大规模图数据可达性索引时的构建时间长、存储代价高和响应时间长等问题,提出一种分布式可达性索引与查询策略(DRIQ)。在不破坏原图中节点可达性的前提下,将大规模图划分成若干小规模子图,并对每个子图分布式并行地创建可达性索引,从而提高可达性索引创建效率。给出保持图划分后各子图内节点间以及子图间节点可达性的方法,从而保证基于DRIQ进行可达性查询的正确性。实验结果表明,与传统可达性查询方法相比,该策略具有高效性和可扩展性。     

大规模图数据可达性索引技术:现状与展望

随着社交网络、生物信息网、本体等新兴领域的飞速发展,在现实应用中涌现出大量的图数据.可达性查询是有向图上一类最基本的查询.当图的规模非常小时,利用深度优先遍历(depth-first search,DFS)或可达性传递闭包可以很容易处理可达性查询.但是,随着图的规模越变越大,由于DFS方法的查询效率太低而可达性传递闭包方法占用的存储空间太大,这2种方法不再适用.因此,许多可达性索引方法相继被提出.这些方法已经被广泛应用于多个计算机科学领域,如软件工程、编程语言、分布式计算、社交网络分析、生物网络分析、XML和RDF数据库、路由规划等领域.此外,可达性索引还可用于加速其他图算法,如最短路径查询和子图模式匹配.首先介绍了可达性索引的应用背景.接着,依据支持的数据规模、数据类型以及查询类别,将现有可达性索引工作进行了分类,并对代表性工作进行分类比较;最后,讨论了现有的大规模图数据可达性索引方法存在的问题,并指出了未来的研究方向.     

一种新颖的对比子图索引算法

针对当前图索引算法存在的问题,提出一种基于对比子图索引框架,开发冗余感知机制,选择一个小型的具有明显区分力的索引特征集,改善索引性能。实验结果表明,该算法对不同的包容搜索载荷能达到近优化的修剪力,与传统图搜索方法相比,具有明显的索引性能优势。     

支持动态图数据的子图查询方法

近年来,子图查询作为图数据库管理的一项重要课题受到国内外学者的广泛关注。在现实应用中大部分图数据是频繁更新的,而现有方法对图数据的频繁更新的维护代价较高。子图查询本身就是NP完全问题,在动态图数据上子图查询问题就变得更加困难。针对上述问题,提出了支持动态图数据的子图查询方法。该方法首先构造出每张图的拓扑层次序列作为索引,在序列中加入标号以便数据更新后对索引进行维护,再根据序列间的匹配关系过滤出候选集合,最后采用图同构算法验证候选集中的图,最终得到结果集合。该方法的索引构造简单且体积小,并且在图数据库更新后无需重构索引,不仅支持动态图数据上的子图查询,在静态图数据上也表现出良好的性能。     

一种多到一子图同构检测方法

提出一种方法来解决从多个小图到一个大图的子图同构检测问题,其中多个小图是预先给定的,而大图是用户在线提交的.首先,基于DFS 编码提出一种小图集合的压缩组织方法;其次,提出一种带有前向剪枝技术的从多个小图到一个大图的子图同构检测算法.另外,给出一种有效的基于数据挖掘的索引技术.分析和实验结果证实,所提出方法的在线计算代价远小于现有方法,在线执行时间比现有方法快约一个数量级,离线构造时间快一个数量级以上.     

一种UDP报文数据的搜索方法

在分布式数据传输中,UDP协议由于实现机制简单、传输效率高,被大量应用系统所采用。为了数据分析和处理的需要,常常要对录取得到的海量UDP报文数据进行搜索,以得到符合要求的报文。针对以上需求,文章在UDP报文数据的搜索中引入倒排索引机制。从存储、生成两个方面对UDP报文倒排索引进行了详细论述,并介绍了利用UDP报文倒排索引的报文搜索方法。     

基于深度优先搜索的一般图匹配算法

对于一般图的匹配问题,Edmonds算法以Berge定理为基础,采用广度优先搜索增广路,图中可能存在“花”。遇到这种情况,要对它进行缩减“花”处理,再进行搜索。当找到增广路时,要将缩减图恢复,算法显得复杂。Gabow等算法使用先给固的顶点和边编号,并使用了不同数组和虚拟顶点,避免了处理花。算法的复杂性为O（n^3）,但增加了空间复杂性。本文提出的基于深度优先搜索算法,在搜索增广路时不会出现“花”的情况,算法相对简单;同时,算法时间效率为O（n＊degree（n））,degree（n）为顶顶点的平均度数。另外,当图的边动态增减时,使用该算法可以很快调整最大匹配,并且该算法空间复杂性在同一数量级也可以推广到广度优先搜索。     

一种异构海量数据搜索方案

随着海量数据时代的到来,如何在异构海量数据中进行数据搜索成为一个迫切的问题。本文分析搜索技术的基本原理,比较现有的异构数据搜索方案,在此基础上,通过引入元数据技术,提出一种基于统一索引的异构海量数据搜索解决方案,并详叙基于开源技术的实现。     

一种异构数据集成中的动态查询优化方法

查询优化是异构数据集成中需要解决的关键问题之一,但环境的分布性、异构性以及局部数据源的自治性使得异构数据集成中的查询优化变得非常困难。通过对异构数据集成中查询后处理调度的分析,给出了查询后处理的全局查询图表示,并给出了基于全局查询图的查询后处理并发调度方法,最后给出了一种基于统计推理的查询后处理动态优化策略,它可用于基于全局查询图的查询调度中,实现查询后处理的动态优化。     

一种基于遗传算法思想实现的图匹配算法

针对计算机图数据处理难题中的图数据检索匹配问题。相比传统的基于统计分布、模式识别等理论,该文在研究了遗传算法的智能优化过程的基础上,对照图匹配过程中的对应信息元素的查找难题进行求解。将遗传算法的思想理论与图匹配方法相结合,利用智能优化算法对解决基于内容的图匹配问题探索提供新的解决方法,从智能优化的角度来考虑和快速解决图匹配过程中的结构对应检索难点。通过验证参数和对象得出图匹配问题新解。     

一种存储介质优化的大规模图遍历方法研究

大图数据的BFS算法作为一种基础算法,受到工业界和学术界的广泛重视。不同平台涌现出众多大图BFS算法的研究工作,其中多使用固态硬盘来提高算法效率。在BFS算法遍历过程中,存储设备需要连续重复装载会数据以满足遍历需求,而数据重复装载造成大量数据擦写操作,严重影响了固态硬盘的使用寿命。由此可见,减少BFS算法数据擦写操作可以有效延长固态硬盘的使用寿命。结合图结构的特点,提出数据重用模型,用于描述图遍历过程中的数据重用程度;提出了基于图顶点度的启发式优先访问方法,该方法判断图顶点之间的独立性,并根据判断结果选择优先访问的图顶点,增加数据重用的可能性,提高缓存的命中率,减少闪存颗粒磨损。所提优化方法不修改BFS算法和大图数据,适用于各种BFS算法和数据集。最后,实验验证了所提数据重用模型的正确性,以及启发式优先访问方法的有效性。该优化方法应用于BFS-4K,B40C和Gunrock这3种常见的BFS算法上,能有效减少图遍历过程中的数据写入操作,固态硬盘的使用寿命可分别提高12%,15%,22%。