强模拟在带权有向图的扩展及其匹配结果的排序

图模式匹配是互联网海量数据库应用的关键技术。强模拟是现在一种实际应用效果较好的图模式匹配模型,但它无法对匹配结果按照重要程度排序。本文将强模拟推广到了带权有向图中,使用边的权值衡量和比较不同匹配子图或子图内部不同顶点的重要性,对匹配结果进行排序。     

一种基于极大完全子图的最大频繁项集并行挖掘算法

提出一种基于极大完全子图的最大频繁项集并行挖掘算法PMFIM,通过遍历由频繁2-项集构成的用邻-接矩阵表示的图,寻找图的极大完全子图,从而由极大完全子图顶点序列实现对项集的划分,即挖掘子任务的划分.在同类算法中,将找到的最大频繁项划分为局部最大频繁项集LMFI、可能最大频繁项集PMFI和邻接项集的最大频繁项集的超集SMFI,减少了该类算法合并最大频繁项集的开销,并对算法进行了实现和优化.     

频繁子图挖掘研究综述

归纳了频繁子图挖掘方法的处理流程,分析评价了频繁子图挖掘的典型算法:广度优先搜索和深度优先搜索的频繁子图挖掘算法,概述了频繁子图挖掘研究的平台--图模型及其产生器,并对频繁子图挖掘方法未来研究方向进行了展望.     

时态图上图模式匹配研究综述

图数据模型是一种通用且已经得到广泛应用的可以处理数据对象间复杂关系的数据模型.然而,现有的大多数研究只关注静态图数据的结构或者顶点和边上的属性,忽略了现实中数据的一个重要特征即时态信息.忽略了时态信息将导致错过很多的有价值的信息,甚至得到错误的信息.作为图研究领域中重要的研究内容之一,图模式匹配问题的研究也需要考虑时态信息.考虑到图模式匹配研究的重要性以及时态信息对数据的重要性,本文根据时态图的快照模型、边流模型和区间模型以及时态图数据的时序性、持续性和演化性对时态图上图模式匹配问题进行了全面地综述,并总结了现有工作的不足.     

一种用于生物网络数据的频繁模式挖掘算法

 频繁模式挖掘是生物网络数据分析中的一个核心问题,对于研究生物网络的组织结构和功能模块具有重要意义.本文提出了子图环分布的概念并构造了子图搜索算法,提高了搜索效率.其次设计了动态抽样算法计算子图频率,用于提高非穷举搜索的精度.利用4个真实生物网络数据进行仿真实验研究,验证了本文算法在效率和精度上相对于现有算法的优势.     

新体制雷达信号PRI样本子图周期搜索提取方法

针对侦察接收机截获的交错脉冲序列中雷达信号的提取问题,在脉冲重复周期（PRI）样本子图描述技术的基础上,提出一种基于PRI样本子图周期搜索的脉冲提取算法。算法改传统PRI搜索法中的相邻脉冲间隔搜索思想为PRI样本子图周期搜索思想,通过构造由脉冲到达时间和准PRI样本子图周期构成的二维提取函数,将搜索过程中符合某一假定PRI样本子图周期的匹配脉冲数存储于二维提取函数中,然后根据二维提取函数的最大值确定PRI样本子图周期,提取对应的脉冲,实现复杂PRI类型的雷达信号提取。仿真结果验证了该方法的有效性。      

基于信号子空间的广义回归神经网络频率估计

对淹没在噪声中的载波信号的频率估计可以通过对信号协相关矩阵求取特征向量,分离出信号子空间和噪声子空间,并可基于信号子空间找到与之线性相关,或者基于噪声子空间找到与之正交的载波信号。但要使这两个子空间的矢量函数在某个频率点上得到波峰,仅仅利用噪声子空间的算法,如MUSIC往往需要对一段较大频率范围的频域进行细致搜索,既耗费了大量的时间又会因为搜索步长的选取而造成对识别精度的影响。本文提出一种基于信号子空间的广义回归神经网络频率估计算法,利用广义回归神经网络其极强的非线型拟合和并行计算特性在信号子空间矢量与频率点之间建立良好的非线型映射关系,以达不失估计精度而又提高估计速度的目的。     

基于Kalman预测和点模式匹配的多目标跟踪

针对复杂背景下多运动目标的跟踪方法不能有效解决遮挡和高速运动等问题,提出一种Kalman预测与点模式匹配相结合的多目标跟踪方法。利用Kalman滤波预测目标在下一帧图像中的位置,以此位置为中心确定目标搜索区域,然后以点模式匹配进行搜索区域和目标模板进行匹配,有效地解决目标的旋转和轻微的遮挡问题。为了提高匹配速度和实时性,在点模式匹配中利用Kalman滤波对目标旋转角度的预测与修正;同时为了保证跟踪的鲁棒性、连续性及准确性,对目标模板的更新采用置信度二级判决门限。实验表明该方法具有较好的实时性,并能够有效地解决遮挡等问题。     

求二部图的最大匹配图的一种算法

 一个图的最大匹配图是以这个图的最大匹配集作为顶点集,两个顶点相邻当且仅当这两个最大匹配恰有一条边不同.本文首先对Gallai Edmonds结构定理中的三部分顶点在二部图中进行了详细刻画.然后讨论了构造最大匹配图问题的计算复杂性.最后深入研究了二部图最大匹配图的结构性质并给出了构造二部图的最大匹配图的一种算法.     

一种降维空时自适应处理子阵划分方法

针对机载预警雷达降维空时自适应处理的子阵划分问题,提出了一种基于蚁群算法的雷达阵面子阵划分方法。该方法在子阵数给定的情况下,以最大化子阵级空时自适应处理的改善因子为优化准则,利用蚁群算法搜索子阵间的分隔点,从而获取最优的子阵划分方式。子阵划分是一种组合优化问题,蚁群算法非常适合于解决这种问题。仿真结果表明,利用该方法划分子阵并进行子阵级空时自适应处理,其改善因子总体上仅比阵元级的约低2dB,空时自适应方向图无明显的栅瓣,副瓣也较低。     

基于频繁闭图的图包含查询算法

 交通网络可利用图数据进行描述与分析,常用的方法包括挖掘、查询、分类等.提高大规模图集上查询算法效率的问题是当前图数据分析领域中一个重要的研究方向.给定图集,图包含查询返回图集中所有查询图的子图.本文提出一种基于频繁闭图的包含查询算法.算法首先通过选择比消除频繁闭图之间的冗余,然后将具有强选择性的频繁闭图通过树的结构组织起来建立索引,并在此索引基础上实现图包含查询.在文章的最后,给出了理论与实验的分析结果.结果表明,该算法不但能高效的进行索引筛选,而且能显著的减小候选集尺寸,进而大大的降低了查询图与索引模式之间以及与候选集之间的子图同构测试次数,提高了查询效率.     

二分图的无关分解及其在覆盖问题中的应用

为了大容量存贮器制造过程中因缺陷而造成成品率低的问题，或并行阵列中的容错重组问题，一般采用冗余修复的方法，该问题可以归结为对二分图的覆盖，且该问题属于ＮＰ完全问题。     

ERSearch:一种高效的子图查询算法

子图查询是图数据库研究中的一个重要问题,许多方法基于“过滤-验证”策略进行子图查询,算法研究的重点为快速找到有效的特征集.通过对特征模式在数据图集中的嵌入信息进行分析,离线建立基于重叠关系、邻接关系和近邻关系的嵌入关系索引,提出基于嵌入关系的子图查询算法ERSearch.在给定查询图后,利用特征共现关系与特征嵌入关系联合进行过滤操作,并将过滤阶段的嵌入关系比对结果用于验证过程,提高验证效率.在真实及模拟数据上的实验表明,通过与PathIndex等方法的对比,ERSearch算法有效缩减了候选集的规模,能有效提高过滤与验证阶段的执行效率.     

基于相对形状上下文和谱匹配方法的点模式匹配算法

该文提出了一种将不变特征与谱匹配方法相结合的点模式匹配算法。该算法首先提出一种新的基于点集的不变特征相对形状上下文,然后利用点集间相对形状上下文的统计检验匹配测度来定义新的相容性度量,并以此为基础构造分配图及其亲近矩阵。最后利用分配图亲近矩阵的主特征向量以及匹配约束条件来实现点模式匹配问题的求解。模拟仿真与真实数据实验验证了该文算法的有效性和鲁棒性。     

SCBT-index:基于谱编码的子图索引算法

随着图模型规模的扩大,单机算法难以适应大规模数据集下的子图查询.而现有的分布式算法基于无索引的简单遍历,join过程容易出现内存溢出,而且查询图分布异常时易出现负载不均衡.提出了一种基于谱编码的二叉索引树（SCBT-index）,首先对数据图中的顶点谱编码,根据编码信息构建二叉索引树.然后对查询图使用最小查询计划进行分解,最后join过程使用3个剪枝策略：基于拓扑结构的预剪枝、序列化join和基于分布式下的join优化.实验结果表明,SCBT-index在图集下的综合性能优于现有主流算法,单图下的查询时间为现有算法的1/2到1/4.     

基于子图同构的Hive数据操作合规分析方法

Hive现有的审计功能不能对数据操作目的进行合规判断。针对以上问题,该文提出一种基于子图同构的Hive数据操作合规分析方法。首先,提出基于图的Hive数据操作和合规规则的建模方法,形成数据溯源图和合规规则图;然后,将数据操作合规判断建模为溯源图和合规图的匹配问题,并提出基于子图同构的求解算法。最后,在数据治理平台Apache Atlas及Hive中进行了实验验证,实验结果表明,相比于基于集合、VF2以及Ullmann的合规验证,该文方法具有更高的合规验证效率。     

基于局部相对形状上下文与Q-谱的点模式匹配算法

本文提出了一种基于局部相对形状上下文与Q-谱的点模式匹配算法,对每个点构造相应的线图,并对线图的无符号Laplacian矩阵进行谱分解;利用谱分解所获得的特征值(Q-谱)作为点的特征,进而计算点的初始匹配概率;通过定义局部相对形状上下文计算点的相似性距离;将Q-谱方法与局部相对形状上下文结合进行概率松弛迭代获得匹配结果.实验结果表明了本文算法的可行性与有效性.     

非树型网络模体发现算法

 现有的大多数网络模体发现算法发现网络中的确切模体,但是由于生物数据是不完整的,有噪声的,而且生命过程具有动态性,概率网络模体具有更实际的意义.本文提出了非树型网络模体发现算法,寻找由一组相似子图组成的概率网络模体.在该算法中,首先提出子图挖掘算法ESN挖掘网络中所有给定规模的非树型子图,然后进行多图比对,最后基于统计模型和对应的得分函数,用模拟退火算法求得网络模体.对E.coli和Yeast的基因调控网络的仿真实验表明,该算法能够高效地发现生物网络中的概率模体.